Рет қаралды 756,247
!IMPORTANT NOTE!
"Bounce Sort" is actually called "Cocktail Shaker Sort". If anyone is calling it Bounce Sort these days, it's probably my fault. Sorry for that! If you go around calling it Bounce Sort, your professor's gonna be like "wtf is that? F!" and that ain't gonna be fun!
Ditto for Banshee Sort, it's probably a type of Bucket Sort!
As for Insertion Sort, it's been brought to my attention that it might actually be something called Gnome Sort. Reading about the two at a glance, I think I need to read more. Until then, perhaps you should, too, if it interests you?
-------
Sorting Algorithms used (some were misnamed in the video):
00:00 [1] Bubble sort
00:21 [2] Cocktail Shaker Sort
01:16 [3] Insertion Sort
01:53 [4] Quick Sort
03:07 [5] Bucket Sort, 2 buckets
06:03 [6] Bucket Sort, 10 buckets
08:10 [7] Binary Radix Sort, Least Significant Digit
09:24 [8] Decimal Radix Sort, Least Significant Digit
10:07 [9] Base 121 Radix Sort, Least Significant Digit
10:39 [10] Dynamic Range Random Sort
12:14 [11] Bucket Sort, 192 Buckets
13:09 [12] Racing all together with same data set
13:43 [13] Decimal Radix Sort, Least Significant Digit, finishes
13:51 [14] Quick Sort, finishes
15:08 [15] Bucket Sort, 10 buckets, finishes
15:11 [16] Insertion Sort, finishes
16:19 [17] Cocktail Shaker Sort, finishes
16:50 [18] Dynamic Range Random Sort, finishes
17:07 [19] Bubble Sort, finishes
9000:01 [lol] BOGO sort, still not done
- - - - - - - -
Dynamic Range Random Sort has 2 phases and a 'Tries counter'.
Phase 1:
It randomly selects two elements in the list, a left element and right element. If right has a smaller value than left, they are swapped, and reset Tries to 0. Else, no swap, and we increment Tries by 1. If Tries becomes larger than some number (say 30 for example), it enters phase 2.
Phase 2:
Randomly select one element in the list, then randomly select either the element to the left or the right of that. If the two elements are in descending order, swap them and reset Tries to 0. Else, increment Tries by 1. If Tries ever becomes larger than some number, (such as 30 for example), verify that the list is sorted. If it is, we're done! If not, reset Tries to 0 and resume phase 2.
This sorting algorithm can take a very disorganized list and quickly get it to an almost solved state; each element is very close to where it should be if the list were sorted. But the closer it gets to being solved, the slower it works (each element takes longer to get closer to its correct position)