5 ms·

Sorting algorithms visualizer

221 points by wener 10y ago

ins0 10y ago
One of my favorite sites that i usually share with my students is: http://www.cs.usfca.edu/~galles/visualization/Algorithms.html http://www.cs.usfca.edu/~galles/visualization/Algorithms.htm... Many algorithms and nice visualizations.
- federicoponzi 10y ago
  Thanks, really interesting!
- spike021 10y ago
  Agreed. This was a nice resource to use while I was taking a data structures and algorithms class.
- phlyingpenguin 10y ago
  Thank you. I use the sorting-algorithms visualization and it is usually a great hook for getting students to grok the rest of the content. It'll be great to have more resources.
- epalmer 10y ago
  Thank you. When I was in college (many decades ago) I just though insertion sorting was it. Then bubble sorts. I did not expect the mental flip I did when we starting researching quick sorts. That changed my perspective on obvious but incorrect assumptions forever. These visualizers I think can get you there even faster. I just love this stuff.
  - drostie 10y ago
    I found out that my usual way of sorting cards as a kid was a variant of quicksort. This is to sort the cards first into black v. red, then the black cards into spades v. clubs, then the spades into high v. low, then finally sort the low ones by inspection (a kind of insertion sort I guess), sort the high ones by inspection, sort the clubs similarly, etc. Like most quicksorts, this definitely uses O(log(n)) space as you have a deck of reds, a deck of clubs, and a deck of high spades while you're handling the low spades...
mp3geek 10y ago
When comparing the sort algorithms, how is one defined as stable vs not-stable?
- jwl 10y ago
  Whether items with same sorting key will remain in the same order or not https://en.wikipedia.org/wiki/Sorting_algorithm#Stability https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
kowdermeister 10y ago
This is a quite unique take on sorting visualizations: A folk dance group made sorting algo visualizations via Hungarian / Romanian folk dances :) https://www.youtube.com/user/AlgoRythmics/videos https://www.youtube.com/user/AlgoRythmics/videos
felixhummel 10y ago
It would be great if sound was added: http://panthema.net/2013/sound-of-sorting/ http://panthema.net/2013/sound-of-sorting/
wgman 10y ago
"The ideal sorting algorithm would have the following properties: - Stable: Equal keys aren't reordered. - Operates in place, requiring O(1) extra space. - Worst-case O(n·lg(n)) key comparisons. - Worst-case O(n) swaps. - Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys. There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application." Is there any formal proof that such an algorithm doesn't exist? Are some of those criterion mutually exclusive?
- nightcracker 10y ago
  Most of these are possible to combine (see for example https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort), but I feel that this subset is impossible together: - Operates in place, requiring O(1) extra space. - Worst-case O(n·lg(n)) key comparisons. - Worst-case O(n) swaps. I don't have a formal proof, but I believe one should be possible.
- phunehehe0 10y ago
  I went through the list of algorithms in Wikipedia [0] and a reader pointed out that block sort [1] is an interesting case. It has all the best properties listed, except the worst case swaps, which I can't find in Wikipedia. [0]: https://phunehehe.net/best-sorting-algorithm/ https://phunehehe.net/best-sorting-algorithm/ [1]: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort
- alejohausner 10y ago
  Well, spaghetti sort runs in linear time: O(n) time is spent setting up the device, and O(n) reading out the result. The actual sorting step is O(1) !!! Unfortunately, it's limited to sorting numbers, and uses O(n) additional space (to be precise, it uses O(n) additional volume).
foota 10y ago
This is interesting, I'd never thought about considering the number of swaps that an algorithm does. It seems like low swapping algos should be better in multithreaded environments due to less locking.
- dspillett 10y ago
  There can be a lot more to consider than just the number of comparisons (which a lot of sort algorithm texts concentrate on if they fixate on one thing) which can have an effect on which sort is better for a given circumstance. If an exchange is very expensive then you might prefer an order of magnitude more comparisons in order to reduce the number of exchanges needed. The structure of your data makes a difference too especially if you are trying to sort in-place with little or no extra memory: an exchange by insertion is very efficient with a linked list (just rearrange the links) but can be very expensive with a fixed array (shifting the last element to the front involves moving every other element up one). Sometimes the comparison might be rather expensive at times: if you are trying to sort data stored over many distributed nodes then you need to be careful to pick an algorithm that can constrain itself as much as possible to the local data on each node. Concurrency can be a big issue even if not running on distributed data: some algorithms are much more "lock heavy" than others. And even for a single threaded local only sort on modern CPUs cache use can make a big difference: an algorithm that you intuit should run quickly because it can move objects very far at each step might not be all that good because it much more rarely sees cache hits when looking at data than one that works on smaller local chunks in its inner loop. No one method fits every use: sometimes you want an exchange class sort, sometimes insertion class, sometimes , ...
greggman 10y ago
Here's another http://greggman.github.io/doodles/sort.html http://greggman.github.io/doodles/sort.html
awalGarg 10y ago
Shameless-self-plug: I once wrote a generic algorithm visualizer where you write your own algorithm, and a view function. Then the framework records the state of the algorithm as it changes and passes it to the view function. Then you can play the states like you play a video, go back and forth etc. Here is an example with bubble-sort: http://awal.js.org/alpg/?gist=8b5c6679edc3b85106fb http://awal.js.org/alpg/?gist=8b5c6679edc3b85106fb (hit run, then play/rewind/etc.) The source is available at https://github.com/awalGarg/alpg https://github.com/awalGarg/alpg if anyone feels like dabbling in.
quantumtremor 10y ago
Just for fun: my friend and I 3D printed a model of SelectionSort: https://gfycat.com/HospitableTenderDiamondbackrattlesnake https://gfycat.com/HospitableTenderDiamondbackrattlesnake. Each successive layer behind the front one is one iteration of the algorithm. We also made mergesort and quicksort versions, and I'm working on a model of Dijkstra's right now. To be honest the 3D model doesn't really confer a greater understanding of the algorithm as hoped, but it's nice to play with.
- marinabercea 10y ago
  Interesting approach. If this was part of a series and perhaps in a different material + color-mapped (think Shapeways full color sandstone for instance), I could see someone very passionate about algorithms wanting to buy/own/print them.
alexroan 10y ago
So damn cool
BlackFingolfin 10y ago
This is a really nice page! It would be even nicer if there was some way to find out who made it and/or how to contact the author(s); and/or how and whether one can add more algorithms (e.g. I'd love to see timsort and introsort). As it is, this site seems to be completly anonymous. Which is of course a valid choice by the author(s), but IMHO quite sad :-(.
- yakshaving_jgt 10y ago
  Not completely anonymous. http://who.is/whois/http://www.sorting-algorithms.com http://who.is/whois/http://www.sorting-algorithms.com
  - Retr0spectrum 10y ago
    https://github.com/ericdolson https://github.com/ericdolson
- ericdolson 10y ago
  I am the "guilty" party. sorting-algorithms.com is my site. I have actually been working on a complete refactor of the site and open source the codebase so that others can contribute and add new algorithms. Feel free to reach out - olson {{dot}} ericd {{at}} gmail {{dot}} com
hellofunk 10y ago
This page just goes to show how illuminating a visualizer can be to understanding something we all (programmers) do every day, either on our own or using a tool.
dspillett 10y ago
It misses out sleep sort... (https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort)
smickie 10y ago
Doesn't have the best sorting algorithm of all: https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort
s_dev 10y ago
This interactive visualiser works alongside the code it's executing: http://www.bluffton.edu/~nesterd/java/SortingDemo.html http://www.bluffton.edu/~nesterd/java/SortingDemo.html Heres a similar one that was posted to HN recently: http://jasonpark.me/AlgorithmVisualizer/ http://jasonpark.me/AlgorithmVisualizer/
- awalGarg 10y ago
  Not sure how I feel about this, but the second link you posted is remarkably similar to my alpg[1] project. UI buttons, rendering, usage of Github gist for sharing, url format of shared links, etc. I wrote alpg 3 months back, and the that one has first commit 13 days ago... :| A bit weirded out by this but I am biased ofcourse. Should I care? [1]: http://github.com/awalGarg/alpg http://github.com/awalGarg/alpg
  - s_dev 10y ago
    To clarify I'm not the author of either of the links I simply shared what I found. If you did decide to care you'd have to take it up with the repo owner.
stillworks 10y ago
Is there a way to control the speed ?
banyek 10y ago
I hope you have seen the folk dance shorting visuals...? https://www.youtube.com/watch?v=lyZQPjUT5B4 https://www.youtube.com/watch?v=lyZQPjUT5B4
Ono-Sendai 10y ago
Kind of useless if you aren't going to have radix sort IMO.
- russtrotter 10y ago
  Ya good point. Radix sort is not a comparison-based sort so maybe it's in a different niche. I've always had a soft spot for it :) https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort
wtetzner 10y ago
This is pretty cool. I've always found selection sort to be the most intuitive. When I was in school, a professor mentioned that bubble sort is sort of the "easy" sort that people would discover on their own, but I always thought it seemed complicated compared to selection sort. Selection sort is basically "Find the next smallest item in the remaining unsorted list, and use it as the next value."
- igravious 10y ago
  I think you are both right :) Both seem to me like strategies that you'd intuitively hit upon. I think bubble-sort is a bit more mathsy but a certain type of mind would hit upon it. Because bubble-sort is "Go through the list swapping adjacent items depending on value, Keep doing that until you get no swaps." which is pretty trivial as well. I remember heap-sort kind of blowing my mind when shown to me. When this kind of topic comes up I am always reminded of D. J. Bernstein's Crit-bit Trees: https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html
0x54MUR41 10y ago
There is also Visual Algo [1]. Visual Algo is not only sorting but also data structures algorithms visualizer. [1]: http://visualgo.net/ http://visualgo.net/
username3 10y ago
Quick sort with D3.js https://www.google.com/search?q=bl.ocks.org+quick+sort https://www.google.com/search?q=bl.ocks.org+quick+sort
chris-laffra 10y ago
For visualizations of numerous other algorithms, check out http://pyalgoviz.appspot.com http://pyalgoviz.appspot.com, where both the algorithms and the visualizations are editable. You can replay both the execution and the visualization step by step.

221 points by wener 10y ago

ins0 10y ago

One of my favorite sites that i usually share with my students is: http://www.cs.usfca.edu/~galles/visualization/Algorithms.html http://www.cs.usfca.edu/~galles/visualization/Algorithms.htm... Many algorithms and nice visualizations.

federicoponzi 10y ago
Thanks, really interesting!
spike021 10y ago
Agreed. This was a nice resource to use while I was taking a data structures and algorithms class.
phlyingpenguin 10y ago
Thank you. I use the sorting-algorithms visualization and it is usually a great hook for getting students to grok the rest of the content. It'll be great to have more resources.
epalmer 10y ago
Thank you. When I was in college (many decades ago) I just though insertion sorting was it. Then bubble sorts. I did not expect the mental flip I did when we starting researching quick sorts. That changed my perspective on obvious but incorrect assumptions forever. These visualizers I think can get you there even faster. I just love this stuff.
- drostie 10y ago
  I found out that my usual way of sorting cards as a kid was a variant of quicksort. This is to sort the cards first into black v. red, then the black cards into spades v. clubs, then the spades into high v. low, then finally sort the low ones by inspection (a kind of insertion sort I guess), sort the high ones by inspection, sort the clubs similarly, etc. Like most quicksorts, this definitely uses O(log(n)) space as you have a deck of reds, a deck of clubs, and a deck of high spades while you're handling the low spades...

mp3geek 10y ago

When comparing the sort algorithms, how is one defined as stable vs not-stable?

jwl 10y ago
Whether items with same sorting key will remain in the same order or not https://en.wikipedia.org/wiki/Sorting_algorithm#Stability https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

kowdermeister 10y ago

This is a quite unique take on sorting visualizations: A folk dance group made sorting algo visualizations via Hungarian / Romanian folk dances :) https://www.youtube.com/user/AlgoRythmics/videos https://www.youtube.com/user/AlgoRythmics/videos

felixhummel 10y ago

It would be great if sound was added: http://panthema.net/2013/sound-of-sorting/ http://panthema.net/2013/sound-of-sorting/

wgman 10y ago

"The ideal sorting algorithm would have the following properties: - Stable: Equal keys aren't reordered. - Operates in place, requiring O(1) extra space. - Worst-case O(n·lg(n)) key comparisons. - Worst-case O(n) swaps. - Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys. There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application." Is there any formal proof that such an algorithm doesn't exist? Are some of those criterion mutually exclusive?

nightcracker 10y ago
Most of these are possible to combine (see for example https://github.com/BonzaiThePenguin/WikiSort https://github.com/BonzaiThePenguin/WikiSort), but I feel that this subset is impossible together: - Operates in place, requiring O(1) extra space. - Worst-case O(n·lg(n)) key comparisons. - Worst-case O(n) swaps. I don't have a formal proof, but I believe one should be possible.
phunehehe0 10y ago
I went through the list of algorithms in Wikipedia [0] and a reader pointed out that block sort [1] is an interesting case. It has all the best properties listed, except the worst case swaps, which I can't find in Wikipedia. [0]: https://phunehehe.net/best-sorting-algorithm/ https://phunehehe.net/best-sorting-algorithm/ [1]: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort
alejohausner 10y ago
Well, spaghetti sort runs in linear time: O(n) time is spent setting up the device, and O(n) reading out the result. The actual sorting step is O(1) !!! Unfortunately, it's limited to sorting numbers, and uses O(n) additional space (to be precise, it uses O(n) additional volume).

foota 10y ago

This is interesting, I'd never thought about considering the number of swaps that an algorithm does. It seems like low swapping algos should be better in multithreaded environments due to less locking.

dspillett 10y ago
There can be a lot more to consider than just the number of comparisons (which a lot of sort algorithm texts concentrate on if they fixate on one thing) which can have an effect on which sort is better for a given circumstance. If an exchange is very expensive then you might prefer an order of magnitude more comparisons in order to reduce the number of exchanges needed. The structure of your data makes a difference too especially if you are trying to sort in-place with little or no extra memory: an exchange by insertion is very efficient with a linked list (just rearrange the links) but can be very expensive with a fixed array (shifting the last element to the front involves moving every other element up one). Sometimes the comparison might be rather expensive at times: if you are trying to sort data stored over many distributed nodes then you need to be careful to pick an algorithm that can constrain itself as much as possible to the local data on each node. Concurrency can be a big issue even if not running on distributed data: some algorithms are much more "lock heavy" than others. And even for a single threaded local only sort on modern CPUs cache use can make a big difference: an algorithm that you intuit should run quickly because it can move objects very far at each step might not be all that good because it much more rarely sees cache hits when looking at data than one that works on smaller local chunks in its inner loop. No one method fits every use: sometimes you want an exchange class sort, sometimes insertion class, sometimes , ...

greggman 10y ago

Here's another http://greggman.github.io/doodles/sort.html http://greggman.github.io/doodles/sort.html

awalGarg 10y ago

Shameless-self-plug: I once wrote a generic algorithm visualizer where you write your own algorithm, and a view function. Then the framework records the state of the algorithm as it changes and passes it to the view function. Then you can play the states like you play a video, go back and forth etc. Here is an example with bubble-sort: http://awal.js.org/alpg/?gist=8b5c6679edc3b85106fb http://awal.js.org/alpg/?gist=8b5c6679edc3b85106fb (hit run, then play/rewind/etc.) The source is available at https://github.com/awalGarg/alpg https://github.com/awalGarg/alpg if anyone feels like dabbling in.

quantumtremor 10y ago

Just for fun: my friend and I 3D printed a model of SelectionSort: https://gfycat.com/HospitableTenderDiamondbackrattlesnake https://gfycat.com/HospitableTenderDiamondbackrattlesnake. Each successive layer behind the front one is one iteration of the algorithm. We also made mergesort and quicksort versions, and I'm working on a model of Dijkstra's right now. To be honest the 3D model doesn't really confer a greater understanding of the algorithm as hoped, but it's nice to play with.

marinabercea 10y ago
Interesting approach. If this was part of a series and perhaps in a different material + color-mapped (think Shapeways full color sandstone for instance), I could see someone very passionate about algorithms wanting to buy/own/print them.

alexroan 10y ago

So damn cool

BlackFingolfin 10y ago

This is a really nice page! It would be even nicer if there was some way to find out who made it and/or how to contact the author(s); and/or how and whether one can add more algorithms (e.g. I'd love to see timsort and introsort). As it is, this site seems to be completly anonymous. Which is of course a valid choice by the author(s), but IMHO quite sad :-(.

yakshaving_jgt 10y ago
Not completely anonymous. http://who.is/whois/http://www.sorting-algorithms.com http://who.is/whois/http://www.sorting-algorithms.com
- Retr0spectrum 10y ago
  https://github.com/ericdolson https://github.com/ericdolson
ericdolson 10y ago
I am the "guilty" party. sorting-algorithms.com is my site. I have actually been working on a complete refactor of the site and open source the codebase so that others can contribute and add new algorithms. Feel free to reach out - olson {{dot}} ericd {{at}} gmail {{dot}} com

hellofunk 10y ago

This page just goes to show how illuminating a visualizer can be to understanding something we all (programmers) do every day, either on our own or using a tool.

dspillett 10y ago

It misses out sleep sort... (https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort)

smickie 10y ago

Doesn't have the best sorting algorithm of all: https://en.wikipedia.org/wiki/Bogosort https://en.wikipedia.org/wiki/Bogosort

s_dev 10y ago

This interactive visualiser works alongside the code it's executing: http://www.bluffton.edu/~nesterd/java/SortingDemo.html http://www.bluffton.edu/~nesterd/java/SortingDemo.html Heres a similar one that was posted to HN recently: http://jasonpark.me/AlgorithmVisualizer/ http://jasonpark.me/AlgorithmVisualizer/

awalGarg 10y ago
Not sure how I feel about this, but the second link you posted is remarkably similar to my alpg[1] project. UI buttons, rendering, usage of Github gist for sharing, url format of shared links, etc. I wrote alpg 3 months back, and the that one has first commit 13 days ago... :| A bit weirded out by this but I am biased ofcourse. Should I care? [1]: http://github.com/awalGarg/alpg http://github.com/awalGarg/alpg
- s_dev 10y ago
  To clarify I'm not the author of either of the links I simply shared what I found. If you did decide to care you'd have to take it up with the repo owner.

stillworks 10y ago

Is there a way to control the speed ?

banyek 10y ago

I hope you have seen the folk dance shorting visuals...? https://www.youtube.com/watch?v=lyZQPjUT5B4 https://www.youtube.com/watch?v=lyZQPjUT5B4

Ono-Sendai 10y ago

Kind of useless if you aren't going to have radix sort IMO.

russtrotter 10y ago
Ya good point. Radix sort is not a comparison-based sort so maybe it's in a different niche. I've always had a soft spot for it :) https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort

wtetzner 10y ago

This is pretty cool. I've always found selection sort to be the most intuitive. When I was in school, a professor mentioned that bubble sort is sort of the "easy" sort that people would discover on their own, but I always thought it seemed complicated compared to selection sort. Selection sort is basically "Find the next smallest item in the remaining unsorted list, and use it as the next value."

igravious 10y ago
I think you are both right :) Both seem to me like strategies that you'd intuitively hit upon. I think bubble-sort is a bit more mathsy but a certain type of mind would hit upon it. Because bubble-sort is "Go through the list swapping adjacent items depending on value, Keep doing that until you get no swaps." which is pretty trivial as well. I remember heap-sort kind of blowing my mind when shown to me. When this kind of topic comes up I am always reminded of D. J. Bernstein's Crit-bit Trees: https://cr.yp.to/critbit.html https://cr.yp.to/critbit.html

0x54MUR41 10y ago

There is also Visual Algo [1]. Visual Algo is not only sorting but also data structures algorithms visualizer. [1]: http://visualgo.net/ http://visualgo.net/

username3 10y ago

Quick sort with D3.js https://www.google.com/search?q=bl.ocks.org+quick+sort https://www.google.com/search?q=bl.ocks.org+quick+sort

chris-laffra 10y ago

For visualizations of numerous other algorithms, check out http://pyalgoviz.appspot.com http://pyalgoviz.appspot.com, where both the algorithms and the visualizations are editable. You can replay both the execution and the visualization step by step.