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.
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!
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.
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.
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.
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).
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).
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).
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.
I've never seen someone explain in the most efficient and effective manner. British - the most intelligent people in this universe. Teaching everyone in the world in a common language that most can understand.
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.
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
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.
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. :)
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)
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
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.
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.
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.
(...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.
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.
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.
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.
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.
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.
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.
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.
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.
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)
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.
My teacher tasked me to sort 1000000 random points of data using various sort algorithms. It took over 20 minutes to do it with selection sort. It's a matter of seconds with quick sort.
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.
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 :)
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.
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.
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.
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.
I think the best way to understand how computers do calculations is basically to look at how a mechanical computer works, because digital computers work, in principle, the same way just that they use electric currents instead of physical objects.
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...
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 ;)
but keep in mind that the software is getting more and more complex and does stuff you couldn't think about 20 years ago. I'm not saying all that performance goes into "quality - tasks" that enhance the experience (probably mostly programming inefficiencies), but the overall result of the power is performance where it counts (scientifically at least)
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.
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.
Interesting. I guess the thing that's hardest to wrap my head around is how computers handle numbers. It's easy to understand a computer's mindlessness in relation to real-world concepts. It's much tougher to recognize that that carries over to numbers as well, since numbers are viewed as cold, concrete, and divested from reality, much like the computers that use them.
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.
The one thing I think this video didn't mention was that while quicksort's asymptotic complexity is similar to merge and bubble sort. Its worst case is far less likely to occur than in merge or bubble. So average case runtime will generally be faster for quicksort than merge or bubble.
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.
@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.
in the other video, he talks about how the complexity of these algorithms is polynomial. Quicksort is n*log(n) just like Mergesort, but the other factors are very small, which makes it very fast. If you want to read about algorithms which have nice complexity classes look at Smoothsort and Timsort =)
That's the great thing about quicksort. It's quite easy to do it "in-place" (with only constant memory other than the input). While there are solutions to do mergesort in-place, they're rather complicated and don't give you O(n*log(n)) time. Bubblesort is of course in-place. Wikipedia has a great list at Sorting_algorithm#Comparison_of_algorithms
You're considering only moving a card as an operation, but reading the rank of the card is an operation too. You still need to read all the value of each card for each level of the pyramid: more levels => more reads.
though your counter argument is a valid point, you gotta remember that we're only gonna get more populous, and as we start to live longer and prosper (had to say it), then we're gonna just build higher up, and eventually we'll hit the roof
I recently learned to my astonishment that finding the median can be done in O(n). Search term is "median of medians algorithm". I doubt that it's done very often though, since just randomizing the pivot is much easier and should almost always be faster. Plus, you need to select a pivot for that selection algorithm, too, so maybe you'd just delegate the problem.
Although Eugene has a point in that integers are an easy but bad example. Integer sorting (including string sorting) can in principle be done in O(n*k) where k is the number of digits in the largest number. So if the goal of these videos is to hammer in the point that you can't do better than O(n log n) in sorting, integers aren't ideal to prove your point ;) So Brady please do a video on radix sort (and bucket and counting sort) and then explain why it's rarely used and O(n log n) still holds.
2) No, he described selection sort. Merge sort is a bit more involved and was covered in the previous video. Insertion sort is where you proceed through the list, look at each item, go find what location in the earlier part of the list it should go in, move everything in between over one, and drop the item in its place. It's basically the "opposite" idea to selection sort, where you go out and look for each item that should go in the next place.
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.
Also, the algorithm you described is well known. It's called selection sort. It's not generally any faster than other algorithms. You have to realize that the searching itself takes time, and because the algorithm can only look at one number at a time, it will have to search over the same numbers multiple times, so that in the worst case, it takes O(n^2) comparisons. It's also O(n^2) on average. Not necessarily bad, though, for small lists.
It's all about memory and what's being processed. A program only processes one or two numbers at a time. As far as an algorithm is concerned, whatever instruction the computer is executing at the moment, the numbers that instruction are looking at are the only ones it "knows about" directly; the rest are stored away "out of mind", so to speak. Contrast the human brain which processes massive amounts of information simultaneously (and the processor is also the memory, distributed throughout).
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.
Choosing a random pivot does not change the asymptotic running time of the algorithm. (Also, shuffling is going to require twice as much memory bandwidth). No need to completely change algorithms. In production you never know where your code will eventually be used, so it shouldn't be written with unpredictable corner cases. Also, you may not offer a web service to sort arrays, but there are certainly web services that sort as part of their operation. Like that hash function exploit.
Merge sort is also the fastest sorting method in real life (that I'm aware of). Whenever I have a stack of papers in random order that needs to be sorted, I sort small sets of three or more papers, then merge every two sets into one until the entire stack is in order. I'm so nerdy. O_o
Two main problems with that: the range of the numbers could easily be massive compared to the number of elements (also, the range is not usually known at the beginning) and you're talking about going through the entire list R times, where R is the range. Basically, in order to "search for 0s", you need to search through the entire list. Then search again for all the 1s. Then again for the 2s... etc.
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...
Quick sort may often be slower than merge sort, but in some circumstances it uses a lot less memory. Sometimes speed is more important than space, but sometimes it's the other way around.
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.
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.
Yes, but the algorithms from the libraries may be composed of these algorithms. For example, "sort" from C++'s STL is made with a combination of quicksort and heapsort. So, they are somehow used. You don't have to write it, but someone had to.
You made it so simple compared to my professor !
God he's an angel. Why do professors make everything so needlessly complex. Thank u very much
Quicksort explained quickly.
OMG! Finally someone that simplifies this algorithm. THANK YOU!
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.
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!
3 minutes and it fixed me... you're awesome
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.
gotta love the beauty of recursion
Fantastic fast, clear, visual explanation. I feel like so many overcomplicate these concepts. Thank you so much.
BEST quick sort video EVER. FInally understand it 100% and MY MIND HAS BEEN BLOWN.
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.
this video explanation is so simple and has clear visualization than any other quicksort algorithm video i have ever watch
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.
i feel like this is the most logical and well mannered argument on youtube.
well done, honestly.
youtube could use more of this.
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).
This is the best explanation on quick sort that I've found so far in the internet
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).
Best explanation of the recursive nature behind the quicksort algorithm that I've found so far on TH-cam. Thx well done.
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).
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.
I've never seen someone explain in the most efficient and effective manner.
British - the most intelligent people in this universe. Teaching everyone in the world in a common language that most can understand.
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.
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
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.
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. :)
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)
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
Knowing all the different sort algorithms is definitely the key to being a great computer scientist.
Why else would people go on about them so much?
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.
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.
Best explanation of quicksort I have found.
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.
Loving this new channel. Thank you Brady (and all those involved)!
(...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.
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.
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.
This is just brilliant.
Thank you guys for that, I was having a hard time with it before I check your video.
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.
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.
This is why I love this channel. Thank you!
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.
The best Brady channel besides sixtysymbols !
Brilliant illustrated!
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.
This Alex guy is really good at this.
Well done Alex!
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.
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.
Best quicksort explanation I've seen.
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)
This is one of the best tutorial on quick sort. Thank you.
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.
I literally sat a computing exam a week ago. This video would have been SO USEFUL then.
My teacher tasked me to sort 1000000 random points of data using various sort algorithms. It took over 20 minutes to do it with selection sort. It's a matter of seconds with quick sort.
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.
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 :)
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.
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.
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.
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.
I think the best way to understand how computers do calculations is basically to look at how a mechanical computer works, because digital computers work, in principle, the same way just that they use electric currents instead of physical objects.
been looking for quick sort tutorial for my mid test, and this is what I definitely need!
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...
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 ;)
but keep in mind that the software is getting more and more complex and does stuff you couldn't think about 20 years ago.
I'm not saying all that performance goes into "quality - tasks" that enhance the experience (probably mostly programming inefficiencies), but the overall result of the power is performance where it counts (scientifically at least)
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.
The best quicksort tutorial
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.
Interesting. I guess the thing that's hardest to wrap my head around is how computers handle numbers. It's easy to understand a computer's mindlessness in relation to real-world concepts. It's much tougher to recognize that that carries over to numbers as well, since numbers are viewed as cold, concrete, and divested from reality, much like the computers that use them.
Thank you! Now I can sort my books more easily
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.
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.
The one thing I think this video didn't mention was that while quicksort's asymptotic complexity is similar to merge and bubble sort. Its worst case is far less likely to occur than in merge or bubble. So average case runtime will generally be faster for quicksort than merge or bubble.
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.
@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.
in the other video, he talks about how the complexity of these algorithms is polynomial. Quicksort is n*log(n) just like Mergesort, but the other factors are very small, which makes it very fast. If you want to read about algorithms which have nice complexity classes look at Smoothsort and Timsort =)
That's the great thing about quicksort. It's quite easy to do it "in-place" (with only constant memory other than the input). While there are solutions to do mergesort in-place, they're rather complicated and don't give you O(n*log(n)) time. Bubblesort is of course in-place. Wikipedia has a great list at Sorting_algorithm#Comparison_of_algorithms
You're considering only moving a card as an operation, but reading the rank of the card is an operation too. You still need to read all the value of each card for each level of the pyramid: more levels => more reads.
Oh great you could have put this video up before our computing exam.
explained in 3 minutes what my professor couldn't explain in 30 minutes
though your counter argument is a valid point, you gotta remember that we're only gonna get more populous, and as we start to live longer and prosper (had to say it), then we're gonna just build higher up, and eventually we'll hit the roof
I recently learned to my astonishment that finding the median can be done in O(n). Search term is "median of medians algorithm". I doubt that it's done very often though, since just randomizing the pivot is much easier and should almost always be faster. Plus, you need to select a pivot for that selection algorithm, too, so maybe you'd just delegate the problem.
Although Eugene has a point in that integers are an easy but bad example. Integer sorting (including string sorting) can in principle be done in O(n*k) where k is the number of digits in the largest number. So if the goal of these videos is to hammer in the point that you can't do better than O(n log n) in sorting, integers aren't ideal to prove your point ;)
So Brady please do a video on radix sort (and bucket and counting sort) and then explain why it's rarely used and O(n log n) still holds.
2) No, he described selection sort. Merge sort is a bit more involved and was covered in the previous video. Insertion sort is where you proceed through the list, look at each item, go find what location in the earlier part of the list it should go in, move everything in between over one, and drop the item in its place. It's basically the "opposite" idea to selection sort, where you go out and look for each item that should go in the next place.
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.
Computerphile? :) Cool!
I just discovered this channel. I think it's right down my alley.
Also, the algorithm you described is well known. It's called selection sort. It's not generally any faster than other algorithms. You have to realize that the searching itself takes time, and because the algorithm can only look at one number at a time, it will have to search over the same numbers multiple times, so that in the worst case, it takes O(n^2) comparisons. It's also O(n^2) on average. Not necessarily bad, though, for small lists.
It's all about memory and what's being processed. A program only processes one or two numbers at a time. As far as an algorithm is concerned, whatever instruction the computer is executing at the moment, the numbers that instruction are looking at are the only ones it "knows about" directly; the rest are stored away "out of mind", so to speak. Contrast the human brain which processes massive amounts of information simultaneously (and the processor is also the memory, distributed throughout).
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.
Choosing a random pivot does not change the asymptotic running time of the algorithm. (Also, shuffling is going to require twice as much memory bandwidth). No need to completely change algorithms. In production you never know where your code will eventually be used, so it shouldn't be written with unpredictable corner cases. Also, you may not offer a web service to sort arrays, but there are certainly web services that sort as part of their operation. Like that hash function exploit.
Thank you so much, this was a great help for my CS revision :)
Merge sort is also the fastest sorting method in real life (that I'm aware of). Whenever I have a stack of papers in random order that needs to be sorted, I sort small sets of three or more papers, then merge every two sets into one until the entire stack is in order.
I'm so nerdy. O_o
Two main problems with that: the range of the numbers could easily be massive compared to the number of elements (also, the range is not usually known at the beginning) and you're talking about going through the entire list R times, where R is the range.
Basically, in order to "search for 0s", you need to search through the entire list. Then search again for all the 1s. Then again for the 2s... etc.
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...
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.
Quick sort may often be slower than merge sort, but in some circumstances it uses a lot less memory. Sometimes speed is more important than space, but sometimes it's the other way around.
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.
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.
The best explanation on TH-cam, thanks a alot !!
Yes, but the algorithms from the libraries may be composed of these algorithms. For example, "sort" from C++'s STL is made with a combination of quicksort and heapsort. So, they are somehow used. You don't have to write it, but someone had to.