Quick Sort - Computerphile

Quick Sort is a popular sorting algorithm, but how does it work? Alex continues our exploration of sorting algorithms with a quick look at quick sort.
Original 'get sorted' film: • Getting Sorted & Big O...
Cookies: • Follow the Cookie Trai...
Alex's code that generated the data for the tests on the original 'get sorted' video:
github.com/apinkney97/Sorts
Alex's graph of all the results from his tests on the original 'get sorted' video: eprg.org/allplots.pdf
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at:periodicvideos.blogspot.co.uk/...

[@aboriad15]

You made it so simple compared to my professor !

[@PirateFunk]

Quicksort explained quickly.

[@premd1940]

God he's an angel. Why do professors make everything so needlessly complex. Thank u very much

[@joshuasansom_software]

OMG! Finally someone that simplifies this algorithm. THANK YOU!

[@6BuSh]

3 minutes and it fixed me... you're awesome

[@micfoley8]

gotta love the beauty of recursion

[@EclecticSceptic]

Loving this new channel. Thank you Brady (and all those involved)!

[@gulllars]

Quicksort is also a beautiful recursive algorithm :) While you can understand bubblesort after finishing intro to programming, not even necessarily object oriented programming, you need something like algorithms and data structures plus a lot of thinking to understand the beauty of the quicksort algorithm. Bubblesort is also beautiful in it's simplicity, and can still be nice with simple optimizations :) This video explains quicksort very well and simply at a top level.

[@ErichCervantez]

Best explanation of the recursive nature behind the quicksort algorithm that I've found so far on KZbin. Thx well done.

[@CoolAsFreya]

So I'm doing a uni project on sorting algorithms and asymptomatic notation, and I've been looking at code so long I was starting to forget what quicksort actually does, only that my recursive code worked. This video helped refresh me on quicksort so thank you!

[@sahairadams2536]

This is just brilliant. Thank you guys for that, I was having a hard time with it before I check your video.

[@akmalmaulanaazzam6815]

this video explanation is so simple and has clear visualization than any other quicksort algorithm video i have ever watch

[@1MinuteGaming]

This is why I love this channel. Thank you!

[@KyleYonan]

Fantastic fast, clear, visual explanation. I feel like so many overcomplicate these concepts. Thank you so much.

[@otter-pro]

This is one of the best tutorial on quick sort. Thank you.

[@Kneedragon1962]

This does go some way to explaining how quick sort works, but doesn't really show why it's quick. At uni, what they did, was put together a little graphical demonstration, with roughly a hundred items, and had them bubble sort, and a couple of other sorts, then quick sort. Or rather, they ran it once with about ten items per list, and there was no real difference, in fact, quick sort wasn't all that quick. But once the number of items became non trivial, quick sort very quickly demonstrated it was orders of magnitude faster. It was quite striking how much faster it was than anything else.

[@legendary_chicken]

This is the best explanation on quick sort that I've found so far in the internet

[@HERPDEDERP49]

i feel like this is the most logical and well mannered argument on youtube. well done, honestly. youtube could use more of this.

[@sstevanuss]

been looking for quick sort tutorial for my mid test, and this is what I definitely need!

[@cdsteer94]

Thank you so much, this was a great help for my CS revision :)

[@Drigger95]

BEST quick sort video EVER. FInally understand it 100% and MY MIND HAS BEEN BLOWN.

[@k42p3r]

Brilliant illustrated!

[@TheDoubleBee]

You should always choose the center-most element as the pivot for the off-chance the list is already (somewhat) sorted, and if the list is random then the center element is still as good of a choice as any other.

[@aamike82aa]

Best quicksort explanation I've seen.

[@OldieBugger]

Once, when I was young and designing sorting for a biology professor, to sort out his research data (ant populations) I took the most acclaimed sorting algorithm, quicksort at the time and wrote it into the program. And it promptly crashed due to stack overflow. Ok, it was back in the days of PC XT:s when both memory and stack were available in very limited supply. I switched to an non-recursive algorithm shellsort, which was quite sufficient. Problem solved. Anyway, even later when the computer memory and stack were available in much larger chunks, I found out that the theoretically superior (recursive! Ooh how sexy) algorithm is not necessarily the fastest one in real world situations. I clocked both algorithms on real data. I was writing programs for real people doing real work, not for a theoretical situation. So I mostly shunned quicksort and used shellsort or mergesort instead. Yes, the real-life situations are often like this: you have tens or hundreds of thousands of records (or millions) that are already sorted, and you want to add some additional elements (in the order of tens or hundreds) to these.

[@Solitus0924]

Best explanation of quicksort I have found.

[@markostuban]

This helped me out. Thanks!

[@HiAdrian]

Computerphile? :) Cool! I just discovered this channel. I think it's right down my alley.

[@anhduc4932]

The best explanation on KZbin, thanks a alot !!

[@god8831]

that was an awesome tutorial so easy to understand and so simple damn!

[@cachorito01]

Such a simple explanation! Thanks!

[@ashwith]

Once again, excellent work with the animations! Please do the spanning tree algorithm! :-)

[@adrianmatteo]

I know how to code it, what I mean is: this channel is called computerphile, the really interesting part about the sorting is how the computer does it (for the people that does not know how it's done).

[@Nixitur]

The way I learned Quicksort, you choose the center element or (if the number of elements is even) the one to the left of the center as the pivot element. Sure, in the worst case, that is always the highest element in the list, but that is much more unlikely than being fed a sorted list in which case choosing the center element gives you the best results.

[@limbridk]

This Alex guy is really good at this. Well done Alex!

[@TechyBen]

Well, YT less so. Most TV, defiantly. This channel, and it's relatives, actually take us step by step. Which is nice. As all levels can enjoy, just moving in and starting from the step they are happy with and progressing from there. :)

[@CloudCrusader438]

really nice and simple explanation! :D thanks

[@VechtMalthos]

Another optimization (for very large lists) is to use quicksort first to some depth (usually log(n)), and then use another sort such as merge sort, or one (that hasn't been talked about yet) such as heap sort or insertion sort (this one bad on big unsorted lists but is really good on partially sorted lists).

[@Caldera510]

Beautiful explanation.

[@nirgn]

Great video! Can you do more algorithms?

[@AlexanderEmashev]

Thank you, that was precisely what I looking for!

[@JanCRefsgaard]

they did, there is a plot in the video description, the two quick sort algorithms are fastest, then comes merge sort, then heap sort and then all the other algorithms

[@Tupster]

Computers generally are built so you have to know the address of the memory you need to access before you can find out what it contains. It is like having to go to a person's address before you know who they are. Memory that can be accessed based on what it contains is more expensive, but it is used in some parts of the computer that need to be very fast (like the cache or virtual memory tables)

[@Poponfu1]

The best Brady channel besides sixtysymbols !

[@sbartsa]

Your answer covered me completely. ;)

[@Ostsol]

I haven't had to write many sorting algorithms lately, though I have been doing plenty of hand-sorting. For that I use a variation on a merge-sort.

[@VechtMalthos]

Bubblesort and selection sort can be done in place, with a constant amount of memory used to keep up with the parameters of the algorithm. They are O(1) in space complexity. Merge sort uses O(n) memory. You would think it would be more, but you can free up memory you aren't using as you go along. Quick sort is also O(n) in space complexity, but there are some in-place implementations that reduce this to O(log n) (you still have to keep up with information about partitions).

[@Brotcrunsher]

Is there any video planed about the Bit Coin? I would love to hear about that.

[@BGBTech]

in cases where I have implemented quicksort, typically I have used the value from the middle of the list, mostly because it tends to behave better in cases where the list is already (or is nearly) sorted. picking the first or last item will tend to result in the worst-case with nearly sorted lists (and/or trigger falling back to a slower sorting algorithm). IIRC, once looking at a C library qsort, it grabbed the first/last/middle values, and picked the middle value of these.

[@PsychoticusRex]

The "List" exists in memory, it is computationally impossible using standard computers to do comparisons on things in memory, they have to be in a "register" or using some special port to something like a MathCoProcessor/GPU to do "direct" (as far as progam is concerned) comparisons. So, reason they do one-and-one compares is due to need to load data into TWO separate registers of appropriate type and then compare them. Some advanced architectures allow for memory pointer+size comparisons.

[@Tupster]

These videos have been about comparison based sort in memory that is accessed by address instead of by content. If you can access by content or you do something other than compare numbers then it is a different kind of sort and you get different algorithms.

[@curiousMe1000]

mind blowned. Best explanation

[@ghelyar]

If you modify your algorithm to find the lowest element (rather than just blindly using 0, 1, 2, 3 etc), put that at the start, then find the next lowest, put that after it, etc until you get to the end of the list, you have a selection sort which runs in n^2.

[@petros_adamopoulos]

Of course it is. If you're sorting a big database or anything that doesn't fit in 8gb. But what he meant is that it's interesting to know if an algorithm needs a separate list to move things to or is able to sort things in-place. If I remember correctly merge sort requires a second list of keys when quick sort sorts in-place with only the program stack as extra memory used. When sorting big loads of data you want no extra memory used. The less data the less important the extra memory usage is.

[@robinkuipers93]

And now onto Randomized Quicksort! You choose the pivot at random, which, in practical uses gives better results than the one on the start or the end, or even the approximate middle.

[@akbaer60]

Thank you! Now I can sort my books more easily

[@blenderpanzi]

Memory consumption (IIRC): Merge Sort: O(n) Quick Sort: O(1) Quick sort can be implemented "in place". This means you don't even need to allocate a second array to copy the values to.

[@Lttlemoi]

you have n operations for each level of the pyramid.Thus, the height of the pyramid is very important, ranging from log(n) to n. This gives a best case of n.log(n) and a worst case of n². The calculation of the average case is a lot more complex, but it also results in n.log(n)

[@xway2]

I'm really liking these videos so far. I'm hoping we'll get videos on all sorts of different types of algorithms in the future.

[@kasuha]

Randomizing doesn't completely avoid o(n^2), just makes it less likely and prevents sabotage. But there are ways to avoid it altogether by smart selection of the pivot.

[@mlemos91]

So does that mean one can use bubble sort until a certain number n, before switching over to merge sort? For an algorithm that accounts for both case advantages?

[@popionlyone]

The best quicksort tutorial

[@fllthdcrb]

(...continued) Granted, modern processors do do more things in parallel. Pipelines, superscalar architecture, etc., are tools they use to parallelize what is written in a non-parallel way. But none of it changes the algorithms themselves, which are still written essentially in the sequential paradigm. Even programs with parallelism have mostly sequential parts; otherwise it becomes difficult to make them work correctly. Not to mention parallel processing facilities are usually quite limited.

[@aikimark1955]

Pick three random items from the and sort them. The middle one becomes the pivot item. This produces a 14% improvement over the first/last/single-random performance for Quicksort because of balancing. If you detect a duplicate in your three items, you can change the normal comparison operation for the next pass to optimize for three partitions (lt, =, gt) rather than the normal two partitions. This way, your duplicates will be in the same (middle) partition and not need any further sorting.

[@Salabar_]

It's not the only reason. You can easily use your own stack-like heap allocator, which will work for O(1), no problem. The bottleneck of modern computers is memory access. For better performance, you should use CPU-cache effeciently. Each recursive call of Quick Sort is a single pass through linear array of data, which is good. Merge sort is similiar, yet you will get much more cache-misses and your CPU will have to wait data from slow RAM.

[@petros_adamopoulos]

If you only slightly alter his "idea", you get what's called a radix sort or counting sort. The fastest possible sorting algorithm, O(n) in every case. It's widely used in computer graphics and physics simulations, as we speak. The drawback is that it works only with plain numbers of reasonable size. You can't sort say strings of text with it.

[@TheSpinTensor]

thanks for the clear explanation.

[@JanCRefsgaard]

everytime you transvert the list in quicksort the pivot is saved on the stack (stack alocation are fast), where mergesort have to allocate memory on the heap for the temporary lists... even though they are both O(n log(n)), you should think of them more like k1 * n * log(k2 * n)) where k1 and k2 are constants related to the computations done each step, k1 and k2 are simply smaller for quick sort...

[@doug65536]

In computer science, log(n) typically means the base 2 logarithm of n, which would be computed as log(n) / log(2) on a typical calculator. When an algorithm is log(n), it means that to make a linear increase in running time, you need an exponential increase in problem size. A simple way of understanding it is, the more items there are, the more effective the algorithm becomes.

[@FreshStartPlox]

I remember this from my Decision 1 exam. Good times.

[@KN100]

I literally sat a computing exam a week ago. This video would have been SO USEFUL then.

[@Schindlabua]

That wildly varies. It mostly depends on which structure you use to represent data (arrays are often sorted with quicksort, linked lists with mergesort, heaps with heapsort etc..). Lots of programming languages also use hybrid approaches. For example, Java and Python use an algortihm called timsort for sorting arrays, which is a mix between merge- and insertionsort, and also checks for already sorted sublists in your list to save time. tl;dr a lot of them.

[@xway2]

Basically: Just google "[language] beginner tutorial". You have to choose what language to start with, of course. I feel like a lot of people will disagree with me, but I'd recommend vb.net, because it doesn't have a ton brackets and stuff to worry about, so I feel like it's more similar to a human language than others, making it easier to learn for a beginner. Another advantage is that you only have to download one (1) program to get started.

[@crzybggr]

O(n) for shuffling a list doesn't matter overall, as the shuffle + quicksort would be O(n + n * log n), which works out to be just O(n * log n). And Quicksort is generally faster than other algorithms on average. Picking a random pivot is better or equal to shuffling in any case. If you're working with something like a linked list, it's equivalent. With actual arrays it's O(1). I can't think of a reason why it would be preferable to shuffle a list as opposed to just picking a random pivot.

[@ianfoote]

Big O notation hides the difference between (e.g.) 2n*log(n) and 6n*log(n). The second algorithm would be 3 times slower than the first, but both would be O(n*log(n)). Also, in the case of Quick Sort the worst case is very rare, especially if the pivot isn't chosen as naively as in the video.

[@nofacee94]

Oh great you could have put this video up before our computing exam.

[@IsYitzach]

I've written a quick sort, so I know how it is implemented. I recall it took a couple hundred lines to do it. But that was many years ago. I might write a shorter one now. I'm sure there are examples on the web. Once you've sorted a list, it makes it a lot easier to search it. I tried to use one to make it easier to find a cutoff in an integration. You can sort tasks based on priority and then do them in a meaningful order w/out a searching for the next one. I'm sure others will have more uses.

[@BGBTech]

yes. the cost of a few comparisons is probably small relative to the cost of picking a bad pivot. it doesn't actually necessarily often cost that much, as often in these sorts of cases, the need for a (potentially expensive) conditional jump can be optimized away.

[@VechtMalthos]

Quick sort's worst case can be mitigated by choosing a better pivot. Instead of just picking the left or right-most items, you can randomly sample x items from the list, and take the median of all sampled values. Obviously if you sample too much you might as well do a different sort, but 3-5 values is almost always enough. Also, you can check to see if the list is sorted before beginning. This adds (+ n) to the complexity, which is insignificant for large n.

[@JanCRefsgaard]

+1, superb explanation, I am no sorting expert so I tried to guess why to the best of my ability, your explanation makes perfect sense, thanks :)... I am a python programmer so I rarely think about efficiency :D

[@Salabar_]

Quick Sort is usually... quicker on real data. In practice, we Quick Sort array, until recursion depth is less then log(n) and then shift to something more consistent, like Heap Sort or Merge Sort. This bring us the speed of QS in average and help to avoid worst case scenario. It's calles Timsort, afaik.

[@Salabar_]

Check Wikipedia. I think, you will find there precise number of comparisions and memory operations. For Quick Sort, you will see something like 3nlogn + 4n comparisions and 2nlogn copies. In Merge Sort, you will need, like 6nlog + 3n copies and nlogn + 2n comparisions. Even though these algorithms are the same in Big O notation, Quick Sort still requires 2 times less work to perform. I hope, this will make things clearer.

[@IsYitzach]

You have it right. What is making it appear faster is the fact that you have fewer unique things than actual things. If you have m unique things and n things to sort, you have worst case of m*n. If m=n, then your back to n^2. In this case, I could beat both by taking a census and reproducing the list sorted. But both of these algorthims would only work if you knew what might be in the list or if finding that out was not too costly.

[@MrCOPYPASTE]

Yes it is, you still need to transverse it to perform a task and that has costs involved. One good software design principal is to find balance in resource usage, on consoles for example you can't just throw more memory in the system you must do the "best" with what you got.

[@S050683]

I may be imagining things, but I'm sure a while ago Numberphile or some similar channel did a video on it and showed why the previous one will get full.

[@georgiysrbsk]

Video on Heap Sort would be great!

[@Niosus]

Well in this case, as far as I know it's pretty accurate, only the pivot is placed in the first position and swapped with the middle position right before the next recursion call? What else is there to talk about except the micro managing of values so you don't need an extra array? How the values are juggled is quite smart. It is a neat trick to optimize it a little bit, but has very little to do with the idea behind quicksort. All that info at once will confuse most non-CS people ;)

[@chsxtian]

Shuffling isn't the way to go. You can just switch 1 random element with the last one before doing a partition. The asymptotic time doesn't change, but it's much more likely that you try to sort a list that's already (partly) sorted, than that all random pivots are the highest element.

[@MalfunctioningVideos]

That depends on the system you want to use to sort, and on the data you expect to get as input. Are you expecting totally random input? Will your input be ridiculously large, or will it be a rather small data set? Does your system have lots of memory and computing power? Do you have the opportunity to create some extra hardware, which will handle the sorting? Do you have access to a network that you could use for distributed sorting algorithms? >There is no "one size fits all" sorting in reality

[@Niosus]

Quicksort works in-place, which means you don't need extra memory. It also rarely ends up in the worst case. Most of the time it is as fast or faster than mergesort. Mergesort guarantees a certain time, quicksort doesn't but it saves you memory and is 99.9999% of the time at least as fast. Every algorithm has their advantages and disadvantages :)

[@fuzzyBSc]

@dkraid - it means the opposite of exponential. Exponential gets very big very quickly: 2, 4, 8, 16, 32, 64, 128, 512, 1024, 2048 etc. log gets big very slowly: 1, 1.58, 2, 2.32, 2.58, 2.80, 3, 3.16, 3.23, 3.46 etc. In big O notation the actual base of the log isn't important because the log of all bases are a constant multiplier to each other.

[@tonysopranio]

I have no idea what you mean by "stop when the index of the itemFromLeft > index of itemFromRight". if we're using the index of the items after they are swapped as in the second swap wouldnt we stop after the first swap?

[@BGBTech]

yes. for most apps which get much past "dead trivial" memory use starts getting a lot more important. even for fairly trivial apps, newbie programmers will often do something seemingly trivial and then wonder where all the memory has gone. a few arrays here, a few strings there, and suddenly the app is out of memory...

[@kardashevr]

in what scenario would one prefer quicksort to merge sort? What is the purpose of quicksort if merge sort exists?

[@tjshmeed]

can you do a video on heap sort and sorts used in parallel computing?

[@balderdash707]

Well, it entirely depends on what m is relative to n. If the number of possible values (2^m) is roughly log(n), then the non-comparison sort he described is just as good as quicksort. If 2^m is even smaller it would be silly to stick with a traditional sorting algorithm.

[@anarchyofthet1tans]

reminds me of the days of decision maths, the different types of quick sort, boubble sort and bin packing

[@forevatrolling]

It would work for smaller lists of numbers but say you had a large list(lets say 100 or so) the time it took would have a significant impact as with most sorting algorithms. But if you want to use a sorting algorithm you obviously use the one thats going to be the most efficient to sort your list of numbers.

[@BillAnt]

Is the pivot value always the right most digit in the initial and sub arrays? Or can it be chosen as the left most digit or any other initially?

[@MrC0MPUT3R]

Learned this in Data Structures at university :D