7 ms·
tl;dr the algorithm (the array is 1-based): for i = 1 to n do for j = 1 to n do if A[i] < A[j] then swap A[i] and A[j]
by maltalex 5y ago
tl;dr the algorithm (the array is 1-based):
for i = 1 to n do
for j = 1 to n do
if A[i] < A[j] then
swap A[i] and A[j]
- smusamashah 5y agoThis is how it looks like https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt71MPW1QA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... It behaves more like insertion sort.
- chubot 5y agoWow this page is very cool! I recommend clicking these four boxes: - quick sort - merge sort - custom sort (this naive algorithm) - bubble sort Then click “start”. And then you can clearly see the difference side by side, including the speed of the sort! Quick sort is quick! Merge sort is better in the worst case but slower on this random data.
- smusamashah 5y agoWhat you are seeing isn't speed but the iterations. If you see the source, I am drawing at certain location in the loop. Sometimes when swap happens, sometimes afterwards. More than speed you are seeing the steps.
- chubot 5y agoI think that is what I mean -- when there are fewer steps in the sort, then the visualization completes faster. So if you visualize two sorts side by side, it's obvious which ones completes faster, and that corresponds to the algorithm's speed, right?
- smusamashah 5y agoEach draw step is one draw call. For example in some algos where there isn't a clear swap operation I draw the whole array in one step, which may or may not reflect all operations that happened before that draw call. https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAbi5wSMMlP6pBABkUxUAHgj7UAajOtOMeGo05+AK137Hx1xatcbqOOtEA2qgAujCGIlQBjsFeNjYgeMAADhRUtKi0jszKcSKJqPwMTKk0MADM6dRZOTYAvt55wAX0jHgltABM2d71NkxNha3tMACM3TD1tUA https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZ... You can change the detail level slider while its running and see how it changes the animation. At level 1 (higher level) this and insertion are same.
- recursive 5y agoThis looks interesting, but I can't get it to do anything. I see a purple gradient square, I see some widgets on the upper right. I see a box of code on the left. None of it seems to visualize a sort or even respond to input. What do I do?
- smusamashah 5y agoClick Start at the bottom of control panel on right.
- SamBam 5y agoIt's a little confusing, but playing around with it I was able to understand it. First of all, there's a Start button at the bottom of the right menu. Hit that and you will see that big color gradient sort itself. However, that massive square is useless for seeing what's going on. So instead change the size to its lowest (8) and the delay to something like 400. Now what you've got is 8 randomly-sorted columns. When you hit Start that algorithm will start sorting them each in parallel. You can just look at a single column and see the colors getting swapped. The darkest color moves to the top very quickly. This is a feature of how this particular algorithm works. What's the point of the big square? Well, for one thing it's an interesting way to compare algorithms. Go back to the settings for a large number, a very low delay, and check off two other sorting algorithms, say Comb Sort and Heap sort. Hit Start and you'll see three very different approaches to sorting the columns.
- edflsafoiewq 5y agoBreak the inner loop into three parts, j < i, j == i, j > i, and you can see it's insertion sort with extra steps. for i = 1 to n do - Inserts A[i] into A[1 to i-1], using the A[i] - spot as a temp variable. for j = 1 to i-1 do if A[i] < A[j] then swap A[i] and A[j] - Does nothing. for j = i do if A[i] < A[j] then swap A[i] and A[j] - Permutes A[i to n], placing the maximum into - A[i]. Since A[i] already has the max after the - first iteration, it won't change, and we don't - care how A[i+1 to n] is permuted since it gets - sorted anyway. for j = i+1 to n do if A[i] < A[j] then swap A[i] and A[j]
- Izkata 5y agoAnd if you start the inner loop at "j=i" and flip the comparison order, it turns into something very similar to a very slow selection sort.
- ColinWright 5y agoIs the "Parallel Merge Sort" working? It doesn't seem to be doing anything ...
- smusamashah 5y agoFixed
- ColinWright 5y agoSuper! Thank you.
- hwers 5y agowhat does 1-based mean?
- calebegg 5y agoThe first element of the array is A[1], rather than A[0] like it would be in nearly all programming languages.
- dredmorbius 5y agoThere is of course the compromise position of 0.5.
- tom_ 5y agoI prefer 9. It makes no less sense than 1, but it is conveniently much closer to the + and - keys.
- notriddle 5y agoMy 0 key is twice as big as the rest of the digits.
- DougBTX 5y agohttps://www.realtimerendering.com/blog/the-center-of-the-pixel-is-0-50-5/ https://www.realtimerendering.com/blog/the-center-of-the-pix...
- Joker_vD 5y agoHuh. I thought it was obvious: e.g., the top-left corner of the screen is (0, 0), the bottom-right corner is (640, 480), and pixels are 1x1 — we take the coordinate of their top-left corner to be their coordinate, so the top-left pixel has coordinates (0, 0), and the bottom-right one has (639, 479), and obviously the coordinates of their centres are (0.5, 0.5) and (639.5, 479.5). But apparently some people treated pixels as geometrical points without size?
- demosito666 5y agoaka bubble sort
- miloignis 5y agoIt is definitely not bubble sort, which only uses a single index comparing items next to each other in the array.
- deleted 5y ago[deleted]
- balefrost 5y agoCheck the direction of the comparison, and check the bounds of the loops. It's not really bubble sort.
- recursive 5y agoAnd check whether the compared elements are adjacent.
- SketchySeaBeast 5y agoAt first it's entirely un-intuitive and obviously slow, but I kind of like the elegance, and the use of "<" makes sense once you realize that the final sweep will be with an i at the end of the array so that j will be ahead of it.
- sunnyque 5y agofor almost two decades I thought this is a bubble sorting algorithm
- Jtsummers 5y agoBubble sort only swaps adjacent pairs (thus "bubble", visualized the values "bubble up" to their correct spot) and is often abbreviated so that the inner loop runs on shorter segments (because the smallest or largest value, depending on how you write it, has been placed, no need to check that section again). this algorithm will swap non-adjacent pairs, making it more like insertion sort.
- klyrs 5y agoViewing this as an "algorithm" may be why people find it to be surprising*. I don't find it terribly surprising, because I've played with a lot of sorting networks. Viewed as a sorting network, it's really clear how and why the algorithm works (and where it wastes half of its time). * though, edflsafoiewq's analysis is nice and tidy edit: https://imgur.com/a/gXYE2Ru https://imgur.com/a/gXYE2Ru