This is a sorting algorithm I made. It finds the min & max of your list (based on your comparison function), and then it appends the mins to the start, the maxs to the end, and recursively cores out the list.
Oh, that’s interesting. It’s basically selection sort, except that you select two values in parallel. (The fact that they go on opposite ends of the result isn’t, I think, as important as it looks; you could do one scan through the data to find the smallest and next-smallest number instead, and it’d be the same principle.)
This is the block, modified with just the min:
I found out about the worst sorting algorithm ever called ‘bogo sort’. It just shuffles the data until the list is sorted.
This already took 3 seconds to return a value.
I laughed when I saw sleep sort
Yeah, sleep sort is hilarious!
Maybe we should revive the Topic of the Month with a “terrible sort algorithm” competition. Here’s mine:
(Obligatory teacherish comment: Bucket sort is actually the preferred technique if the number of data is much larger than the range of possible values, so there are lots of duplicates. My favorite example is sorting a list of Berkeley residents by zip code. Even with more ordinary data, it’s linear time, which is terrific, but at the cost of requiring allocating an array as big as the largest value even if the data are sparse in the range of values, e.g., an array of size 2^64 to sort a bunch of arbitrary integers.)
I haven’t heard that name in years!
I found an interesting video on horrible sorting algorithms.
Oof, this sorting algorithm sucks:
It’s called “Bozo Sort”, and it randomly swaps items until the list is sorted.
takes 839.9 seconds (~14 minutes)!
:O
I tried bubble sort, From Wikipedia’s pseudo code. It didn’t work.
It should work. Want to share your code?
I accidentally closed the tab. I’m going to recreate it again…
Snap! lists are indexed starting at 1, not 0 as in the Wikipedia pseudocode. When I change the two FOR blocks in your script by adding 1 to both starting and ending values, your script works.
And this is quick sort
Never mind. It’s called “Partition Sort”
And this is quick sort
Your partition sort (that’s what that’s called) isn’t a modern quicksort because it leaves out certain optimizations. One is that quicksort does the partition in place in the original array, rather than allocating two new lists for the partitions. Another is that when the size of a partition is less than some small number (five, if I remember correctly), the program switches to insertion sort, because for tiny lists the constant overhead of setting up a partition outweighs the fact that insertion sort is O(n^2) rather than O(n \log n). (Actually, when the partition is small, quicksort just leaves it unsorted! Then it does one big insertion sort of the entire data, because insertion sort, which is O(n^2) in general, turns out to be O(n) if the data are almost in order.) Also, instead of taking the last item as the pivot, as you do, quicksort takes the median of the first, middle, and last items, to guard against O(n^2) behavior if the input data are already close to sorted. (This can happen more often than random chance predicts if, for example, you collected 20 new names and addresses today and want to add them to your (sorted) directory, by just sticking them at the end and then sorting the whole thing.)
Robert Sedgewick got his Ph.D. from Stanford in 1975 for doing a careful analysis of the running time of Quicksort and of the effect of these improvements: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf.
(Sorry, they made me read this when I was a CS grad student at Stanford. :~) )
OK, so real quick sort uses partition sort if the elements' length is \ge 5 : Otherwise, it uses insertion sort?
Yes, when the partitions get that small it just leaves them alone and then does one big insertion sort at the end.