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!
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).
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.
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
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.
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.
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.
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.
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
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)
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.
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)
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.
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).
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.
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.
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).
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.
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.
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.
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.
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.
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.
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.
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.
(...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.
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.
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.
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.
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...
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.
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. :)
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.
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.
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.
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.
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.
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)
@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.
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 :)
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.
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.
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.
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...
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.
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.
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 ;)
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).
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.
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
That appears to be radix sort and is rather efficient, but in the general case of sorting, we don't necessarily sort numbers that we can look at the bits of, but we can compare them.
It is not always the best method to use. Choosing the best sorting algorithm is dependent on your data coming in. If you can make a guess as to how sorted your data is and how much there is, you can determine which sort (there are many) to use. sorting-algorithms website shows examples of various sorts and how well they work with given data spreads.
For many small scale userland applications, it's not very important at all. However, many services, especially online services such as social networking sites and online search engines, deal with no less than petabytes of information. In these types of scenarios, if you can shave off even one byte of memory usage for each entry in a table, there's a potential savings of many terabytes of memory.
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.
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.
To find the average only requires you add up n numbers, so it is O(n), which is much better than sorting, but still bad enough that you really do not want to do it in the middle of your sort, since it will make things run at O(n^2) average case.
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.
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.
Well usually your language will have library functions to do this kind of stuff, so as a programmer, you rarely need to know simple algorithms. However when you get closer to the hardware (for instance assembly) it becomes more important
It only takes 20 bits to hold 1 million and 21 bits for 2 million. So on 32-bit machine, it would only take 11 cycles, as you would start from the largest bit, to compare your two numbers. You can't start from the bottom because you would need to check for the largest bits before producing a result. There might be some steps where a comparison can be done in two or three cycles. One or two cycles to subtract and one more to check the negative bit flag.
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.
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.
Because each check of a card against the pivot is an operation. Best case, you halve the list each time, order log n halvings required and each time you have to check all the remaining cards against the respective pivots, giving order n log n. The worst case he did at the end is genuinely more operations. There are n layers to the pyramid, and in each layer you have to again check all the remaining cards against the pivot to see if they're higher or lower. That's order n^2 operations.
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 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.
well, yes, that as well. I think the issue is that it is easy to use up all the RAM in stupid ways, not necessarily that RAM is a bigger problem than wasting clock cycles (nor somehow negates the value of avoiding wasting clock cycles). for example, while an algorithm with an exponential time complexity will take a long time to execute, one with exponential memory use will run out of memory and crash well before then.
Although both mergesort and quicksort are O(n log n), the amount of work per operation is less for quicksort, so on average, quicksort is faster than mergesort. Also, various "tricks" exist (such as choosing a random element as your pivot) to avoid the worst case scenario.
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
Finding the median each step will cause the algorithm to always run O(n^2), so that is not a good idea. Just choose a random pivot index and on average you will choose a value close to the middle.
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.
You made it so simple compared to my professor !
Quicksort explained quickly.
God he's an angel. Why do professors make everything so needlessly complex. Thank u very much
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.
OMG! Finally someone that simplifies this algorithm. THANK YOU!
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
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).
Fantastic fast, clear, visual explanation. I feel like so many overcomplicate these concepts. Thank you so much.
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.
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
gotta love the beauty of recursion
BEST quick sort video EVER. FInally understand it 100% and MY MIND HAS BEEN BLOWN.
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 feel like this is the most logical and well mannered argument on youtube.
well done, honestly.
youtube could use more of this.
this video explanation is so simple and has clear visualization than any other quicksort algorithm video i have ever watch
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.
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.
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.
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
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)
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.
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)
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.
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).
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.
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.
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).
This is the best explanation on quick sort that I've found so far in the internet
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.
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.
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.
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.
Best explanation of the recursive nature behind the quicksort algorithm that I've found so far on RUclips. Thx well done.
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.
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.
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.
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.
(...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.
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.
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.
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.
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...
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.
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. :)
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.
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.
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.
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.
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.
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)
Best explanation of quicksort I have found.
@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.
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 :)
The best Brady channel besides sixtysymbols !
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.
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.
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.
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...
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.
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.
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 ;)
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).
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.
Loving this new channel. Thank you Brady (and all those involved)!
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
That appears to be radix sort and is rather efficient, but in the general case of sorting, we don't necessarily sort numbers that we can look at the bits of, but we can compare them.
This is one of the best tutorial on quick sort. Thank you.
It is not always the best method to use. Choosing the best sorting algorithm is dependent on your data coming in. If you can make a guess as to how sorted your data is and how much there is, you can determine which sort (there are many) to use. sorting-algorithms website shows examples of various sorts and how well they work with given data spreads.
This is why I love this channel. Thank you!
A trick is to take the first, middle, and last element of the list, and find the median of those values as the pivot.
I literally sat a computing exam a week ago. This video would have been SO USEFUL then.
For many small scale userland applications, it's not very important at all. However, many services, especially online services such as social networking sites and online search engines, deal with no less than petabytes of information. In these types of scenarios, if you can shave off even one byte of memory usage for each entry in a table, there's a potential savings of many terabytes of memory.
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.
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.
a decent method for choosing pivot is to choose 3 random numbers, then pick the median of those. you can always do this in constant time.
To find the average only requires you add up n numbers, so it is O(n), which is much better than sorting, but still bad enough that you really do not want to do it in the middle of your sort, since it will make things run at O(n^2) average case.
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.
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.
Well usually your language will have library functions to do this kind of stuff, so as a programmer, you rarely need to know simple algorithms. However when you get closer to the hardware (for instance assembly) it becomes more important
This Alex guy is really good at this.
Well done Alex!
It only takes 20 bits to hold 1 million and 21 bits for 2 million. So on 32-bit machine, it would only take 11 cycles, as you would start from the largest bit, to compare your two numbers. You can't start from the bottom because you would need to check for the largest bits before producing a result. There might be some steps where a comparison can be done in two or three cycles. One or two cycles to subtract and one more to check the negative bit flag.
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?
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.
If you can split the list into 2 equal parts, you basically get half of input per step instead of reducing it by 1. (n/2)^2 is not equal to 1/2*n^2
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.
Best quicksort explanation I've seen.
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.
Because each check of a card against the pivot is an operation. Best case, you halve the list each time, order log n halvings required and each time you have to check all the remaining cards against the respective pivots, giving order n log n.
The worst case he did at the end is genuinely more operations. There are n layers to the pyramid, and in each layer you have to again check all the remaining cards against the pivot to see if they're higher or lower. That's order n^2 operations.
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.
The best quicksort tutorial
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.
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.
This is just brilliant.
Thank you guys for that, I was having a hard time with it before I check your video.
well, yes, that as well.
I think the issue is that it is easy to use up all the RAM in stupid ways, not necessarily that RAM is a bigger problem than wasting clock cycles (nor somehow negates the value of avoiding wasting clock cycles).
for example, while an algorithm with an exponential time complexity will take a long time to execute, one with exponential memory use will run out of memory and crash well before then.
Although both mergesort and quicksort are O(n log n), the amount of work per operation is less for quicksort, so on average, quicksort is faster than mergesort. Also, various "tricks" exist (such as choosing a random element as your pivot) to avoid the worst case scenario.
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
Finding the median each step will cause the algorithm to always run O(n^2), so that is not a good idea. Just choose a random pivot index and on average you will choose a value close to the middle.
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.