Redpill me on heapsort vs quicksort.

>>59886923
botnet

>>59886923
just call your library's sort

https://www.toptal.com/developers/sorting-algorithms

visualized

>>59887011
Thanks.

>>59887028
What if I have access to both?

>>59886923
quicksort has the worst-case performance of O(n^2) versus heapsort's consistent O(n log n).
From what I've understood quicksort can be faster than heapsort in some cases

>>59887072
Why does it matter? The difference will be negligible in almost all situations

>>59887131
So not in all of them then?

>>59887155
Usually the main difference between the O(n log n) sorts is either time guarantees or memory usage. Heap sort is in-place, meaning it doesn't use any extra memory, and it's worst-case complexity is better than quicksort.

>>59888776
Quicksort can also be implemented in place

Are sorting algorithms a big thing for many? I hear about them in theory all the time, but I have never seen them being mentioned in actual use, and I can imagine that nobody but a select elite ever needs to know what goes on behind the scenes.

noob here, redpill me on why insertion sort is the fastest

>>59889467
It's the slowest

>>59889475

fek i read the graph wrong, i'll just read the wiki of quicksort i guess

>>59889467
because most data is likely already sorted to some degree.

>>59886923
Introsort is the best faggot

>>59889690
you mean bogosort

>>59886923
>x-axis and y-axis aren't labelled

Shit graph

>>59889736
this

>>59889736
Y seems to be generic units of time and X is units of work.

>>59889475
This is how you spot a guy who is still studying and haven't written any worthwhile code in his life, insertion sort is the fastest algorithm in most real world scenarios.

>>59889825
Ye ofc if you're sorting tine little lists, but in that case any sorting algorithm will do.

>>59889376
>nobody but a select elite
Not at all.
They're usually really simple, so algorithms classes have been using them to teach how to analyze an algorithm's correctness and complexity, and how to compare algorithms that solve the same problem. Every CS student has to take an algorithms class, that's why they're so well known.
You're right though. In practice you probably won't even need to implement quicksort again because someone has already done it and you can use that code. And also in practice you usually want to do more than just sorting the data.

Use radix sort

>>59889306
How do you even implement quicksort that is not in place?

its now the year 2017 and you will not find a computer that doesn't have access to threads so the parallelizable mergesort is now the fastest sorting algorithm for larger datasets

most of us are just calling some variation of "list.sort()" from numpy, "list.orderby(x => x.id)" from LINQ or whatever

I dont know which algorithms are implemented behind the curtain in any library except in oracle's SQL (sorry), there, the computer chooses to use hashtables for small sets, and mergesort for larger sets when you call "order by ID" but if you do "select distinct ID" I think its just hashed, the same may not go for "group by ID", not sure what's done in that case

>>59892688
or use an instance of SortedSet

>>59891334
this, best sort

>>59886923
You want the one with the smallest slope

>>59892406
Quicksort for lists in any functional language will almost surely not be in place. The partition always creates a tuple of 2 new lists, one for the smaller and one for the larger elements.
You don't have any control over memory in those languages.