Sorting algorithms visualizer
sorting-algorithms.com
sorting-algorithms.com
http://www.cs.usfca.edu/~galles/visualization/Algorithms.htm...
Many algorithms and nice visualizations.
These visualizers I think can get you there even faster. I just love this stuff.
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...
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.
- 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?
- Operates in place, requiring O(1) extra space.
- Worst-case O(n·lg(n)) key comparisons.
- Worst-case O(n) swaps.
[0]: https://phunehehe.net/best-sorting-algorithm/ [1]: https://en.wikipedia.org/wiki/Block_sort
Unfortunately, it's limited to sorting numbers, and uses O(n) additional space (to be precise, it uses O(n) additional volume).
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 (hit run, then play/rewind/etc.)
The source is available at https://github.com/awalGarg/alpg if anyone feels like dabbling in.
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 :-(.
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 , ...
Heres a similar one that was posted to HN recently: http://jasonpark.me/AlgorithmVisualizer/
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."
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
A folk dance group made sorting algo visualizations via Hungarian / Romanian folk dances :)
(https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort)
[1]: http://visualgo.net/