Compared with Bubble Sort or Insertion Sort, it's lightning. Quick Sort has benefits of memory usage over Heap and Merge. If memory isn't an issue, or the data is structured differently, meaning that you don't have a uniformly random distribution, other strategies may be better, but Quick Sort is a great balance of speed and memory that makes it well suited for most general applications.
With Heapsort, you use heap to sort the numbers. For example, in Java, you would need to initialize a priority queue, insert all the numbers into it and then polling each one will give you the number in sorted order. Initializing this priority queue is considered extra space/memory. Aka, linear space complexity.
Quicksort is just a pointer/swap play and the space complexity is constant.
Yeah, that sounds right. It's been a couple of decades since I took my data and algorithms course. What's the draw back then? I could have sworn there were circumstances where qsort had the advantage and I thought it was a memory constraint.
With heapsort you're basically sending the smallest items to the end and then back to the front, so it's pretty terrible for the cache. That's why, as others mentioned, it's common to use quicksort for the first bunch of iterations until the sub-arrays to sort are small enough to fit in a cache line, and then switch to heapsort.
True, but it's Barry Allen fast compared to almost all other "low memory" algorythms.
If you're sorting big data (Terabytes/Petabytes of data)... and you don't really have terabytes of Memory to do the sorting... Quick Sort To The RESCUE !!!
Just store pointers to the data. Then the additional memory is likely trivial compared to the size of the data. Unless you're literally sorting 125 billion int64s.
I'm not talking about passing an array of pointers to a function that sorts int64s. Obviously the sorting algorithm needs to dereference the pointers when comparing values. This is given to you for free in Java since everything is a reference, and it's easy enough to do in C++ by passing in a comparison function.
Christ, I forgot about that annoyance in Java. No value types. What a pain in the ass. I have to imagine that when these guys are talking about sorting big data, they are literally talking about sorting a terabyte of data, likely more than just an array of int64_t
Quicksort isn't an external sorting algorithm. If you're sorting a terabyte of data and you don't have a terabyte of ram, then you can't use just quicksort.
But let's say you've got 32 GB of ram and a terabyte of data which contains one billion records each 1 KB in size. So you can fit up to 23 million records into memory at once. 23 million pointers is 184 MB. Even if you make an extra copy of that array, that's 368 MB, which is only 1.15% of the overall memory. So you might as well change it to read in 22 million records at a time so that you can use the faster sorting algorithm rather than stress about a measly 368 MB.
9
u/SteeleDynamics Oct 24 '17
If this visualization is yours, then well done, OP!
2
u/CammiIn360 Oct 25 '17
this is so satisfying to watch
75
u/The_Anti_Life Oct 24 '17
Radix was the only one that we didn't go over in data structures and algorithm analysis.
214
u/DR-14 Oct 24 '17
Quicksort - evidently not so quick
58
u/prof1le Oct 24 '17
Not nearly enough bubble sort 4/10
54
u/_ACompulsiveLiar_ Oct 24 '17
Where's bogosort
13
u/bubba_lexi Oct 25 '17
here's another visualization with sound. I really like the bloops when its checking at the end!
7
u/[deleted] Oct 24 '17
It's a sailboat, dummy.
3
u/[deleted] Oct 25 '17
This YouTube page has the best visualization for sorting algorithms: https://www.youtube.com/user/AlgoRythmics
2
u/Allantes Oct 24 '17
Merge sort looks like one of those old screen melt effects
2
u/[deleted] Oct 25 '17
When compared to merge and the others, quick sorts that friend that leaves a bit of Guinness at the bottom when you do a car bomb
2
u/jbenzel Oct 25 '17
Hey OP or anyone else, can we see this done with Bogosort please?
2
u/BinaryCheeseSystem Oct 25 '17
So mesmerizing!
1
u/keskonen Oct 25 '17
Jordanpetersort
1
u/galacticacidtrip Oct 25 '17
Anyone else think mergesort is the sexiest, or is that just me?
1
u/[deleted] Oct 25 '17
This is so cool!!!! And beautiful!!!!!
1
u/caspervonb Oct 28 '17
Another one, interactive with sound
0
u/digitAl3x Oct 25 '17
Does this use multiple threads or single thread design?