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

feature: add algorithm.sortPartial (eg quicksort that stops early) #390

Open
timotheecour opened this issue Nov 27, 2020 · 3 comments
Open

feature: add algorithm.sortPartial (eg quicksort that stops early) #390

timotheecour opened this issue Nov 27, 2020 · 3 comments
Labels
algorithms

Comments

@timotheecour
Copy link
Owner

No description provided.

@ringabout ringabout mentioned this issue Nov 28, 2020
Merged
@ringabout
Copy link
Collaborator

If we choose heap based implementation(cpp), heapqueue needs support user-defined cmp function.

@ringabout ringabout mentioned this issue Nov 29, 2020
Open
5 tasks
@timotheecour
Copy link
Owner Author

heapqueue needs support user-defined cmp function.

that's needed no matter what.

If we choose heap based implementation

we may need both, because for top K with an array of size N, if K is small, heap based sort will be fastest whereas for large K (eg N/2) quicksort (or similar) will be fastest.

@ringabout
Copy link
Collaborator

Yeah, nlargest(Python) combines heapq and tim-sort to get the best performance.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
algorithms
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@timotheecour @ringabout