Redpill me on heapsort vs quicksort

Redpill me on heapsort vs quicksort.

Other urls found in this thread:

toptal.com/developers/sorting-algorithms
twitter.com/SFWRedditImages

botnet

just call your library's sort

toptal.com/developers/sorting-algorithms

visualized

Thanks.

What if I have access to both?

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

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

So not in all of them then?

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.

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

It's the slowest

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

because most data is likely already sorted to some degree.

Introsort is the best faggot

you mean bogosort

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

Shit graph

this

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

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.

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

>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

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

or use an instance of SortedSet

this, best sort

You want the one with the smallest slope

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.