4 ms·

This is how it looks like https://xosh.org/VisualizingSorts/sorting.html#IYZwngdgxgBAZgV2gFwJYHsIwgUwO4DK6ATsgBTDHEA0MAJscHgJQwDeAUDFJiMtjAC8MSsQB0AGxwQA5sgAWAb

This 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 ago
Wow 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 ago
  What 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 ago
    I 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 ago
      Each 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 ago
This 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 ago
  Click Start at the bottom of control panel on right.
- SamBam 5y ago
  It'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 ago
Break 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 ago
And 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 ago
Is the "Parallel Merge Sort" working? It doesn't seem to be doing anything ...
- smusamashah 5y ago
  Fixed
  - ColinWright 5y ago
    Super! Thank you.

chubot 5y ago

Wow 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 ago
What 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 ago
  I 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 ago
    Each 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 ago

This 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 ago
Click Start at the bottom of control panel on right.
SamBam 5y ago
It'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 ago

Break 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 ago

And 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 ago

Is the "Parallel Merge Sort" working? It doesn't seem to be doing anything ...

smusamashah 5y ago
Fixed
- ColinWright 5y ago
  Super! Thank you.