3 ms·
High level description of why it sorts: The inner loop takes an array and an index i in the array, and rearranges the array to put the largest value at index i
by dilap 5y ago
High level description of why it sorts:
The inner loop takes an array and an index i in the array, and rearranges the array to put the largest value at index i. This is done in such a way that if the sub-array up to but not including i is sorted, then afterwords the sort will be extended such that the sub-array up to and including i will be sorted.
The outer loop says, just call in to the inner loop with i from 1 to n. This will result in a sorted array, because the initial array of a single element is trivially sorted, and then we'll have by the sort-extension property of the inner loop that the progressively larger sub-arrays of 2, 3, ... up to N elements become sorted.
You can see that the inner loop has the sort extension property by thinking about two cases.
Case 1: If the i-th element is already larger than all previous elements, it won't touch any of the elements before i, and will only potentially make the i-th element bigger, thus clearly extending the sort though the i-th element.
Case 2: If the i-th element is smaller than one of the previous elements, it won't touch any elements until reaching that smaller element; then it will start a series of swaps until it reaches index i, at which point the the original value of the i-th elment is left inserted in sorted position into the sub-array up to and including i. So at this moment we have the sort extension property. From there, it may increase the value of the i-th element and change later elements, but of both those will preserve the sub-array sort.
- dvogel 5y agoIt is being likened to bubblesort in various places but your description (which I quite like) makes it seem like quicksort with an intentionally bad (worst possible?) bifurcation.
- dilap 5y agoWell, it's not really dividing, sorting, and merging, so I wouldn't say it's too similar to quicksort. It's basically insertion sort, but with the curious property that the last value of the sorted subarray immediately and always has the correct value, and we then "gently" insert new values into the sorted subarray. smusamashah linked to a nice sort visualization. https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... Tap the "Insertion Sort" checkbox on the right, and then the "Start" button below that. You can see how both sorts are slowly constructing a sorted subarray, but this sort has the interesting property that the tail of the sorted subarray immediately obtains its maximum brightness, and new values are gently incorporated into the array, while the insertion sort tail is just the brightest value encountered so far, and the latest value is "abrutly" sifted down into its appropriate place. It feels like this sort might minimize some kind of "sort entropy" metric? I.e., visually it looks very smooth. Each step along the way to sorted is very small.
- 6510 5y ago> https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... That is the most beautiful thing in CS I've ever seen.
- deleted 5y ago[deleted]
- breck 5y agoThis visualization tool is amazing. Is rain just the atmosphere running bubble sort ;) ?