Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Refactor the median() method from DataTomeAnalysis to linear complexity #18

Open
AlexandreHiroyuki opened this issue Sep 23, 2024 · 0 comments
Open

Refactor the median() method from DataTomeAnalysis to linear complexity #18

AlexandreHiroyuki opened this issue Sep 23, 2024 · 0 comments
Labels
help wanted Extra attention is needed optimization Improve performance, efficiency, or resource usage

Comments

@AlexandreHiroyuki
Copy link
Owner

Currently, the algorithm sorts the array to select the median element, which consumes n * log n time.

It supposedly could be faster by implementing an algorithm like Introselect to select the median element among an unsorted array.

Other selection algorithms: https://en.wikipedia.org/wiki/Selection_algorithm
@AlexandreHiroyuki AlexandreHiroyuki added enhancement New feature or request optimization Improve performance, efficiency, or resource usage help wanted Extra attention is needed and removed enhancement New feature or request labels Sep 23, 2024
mohammedelgammal added a commit to mohammedelgammal/DataTome that referenced this issue Dec 11, 2024
@mohammedelgammal
refactor[DataTomeAnalysis]!: Optimize Median method from TC O(N log N…
45ac0b2 
…) to O(N) using IntroSort Algorithm

Median now uses introSelect algorithm merging between quickSelect and medianOfMedians Algorithm
feat[DataTomeUtils]: Adding dt_min helper function to get minimum value between two values and swap to swap two values
resolves (AlexandreHiroyuki#18)
AlexandreHiroyuki pushed a commit that referenced this issue Dec 16, 2024
@mohammedelgammal
Optimize Median method from TC O(N log N) to Linear Time Complexity (#23
3f601cb 
)

* refactor[DataTomeAnalysis]!: Optimize Median method from TC O(N log N) to O(N) using IntroSort Algorithm
Median now uses introSelect algorithm merging between quickSelect and medianOfMedians Algorithm
feat[DataTomeUtils]: Adding dt_min helper function to get minimum value between two values and swap to swap two values
resolves (#18)

* fix[DataTomeAnalysis]: renaming min to dt_min to use utility minimum function instead of cpp std lib

* fix:[DataTomeUtils]: Refactoring dt_min utility function
AlexandreHiroyuki pushed a commit that referenced this issue Dec 27, 2024
@mohammedelgammal
Fix sort_ascend utility function to sort decimals (#25)
3092fcb 
* refactor[DataTomeAnalysis]!: Optimize Median method from TC O(N log N) to O(N) using IntroSort Algorithm
Median now uses introSelect algorithm merging between quickSelect and medianOfMedians Algorithm
feat[DataTomeUtils]: Adding dt_min helper function to get minimum value between two values and swap to swap two values
resolves (#18)

* fix[DataTomeAnalysis]: renaming min to dt_min to use utility minimum function instead of cpp std lib

* fix:[DataTomeUtils]: Refactoring dt_min utility function

* fix[DataTomeUtils]: Refactor sort_ascend Utility Function to precisely sort decimal numbers

resolves #24
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
help wanted Extra attention is needed optimization Improve performance, efficiency, or resource usage
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@AlexandreHiroyuki