You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
302 lines
10 KiB
302 lines
10 KiB
<!DOCTYPE html>
|
|
<html lang="en">
|
|
<head>
|
|
<meta charset="UTF-8">
|
|
<title>Sort Algorithm Walkthroughs</title>
|
|
|
|
<link rel="stylesheet" href="vendor/fontawesome/css/font-awesome.css">
|
|
<link rel="stylesheet" href="css/style.css">
|
|
</head>
|
|
<body>
|
|
<h1>Sort algorithm walkthroughs</h1>
|
|
<h2>Using D3 to animate sort algorithms</h2>
|
|
<hr>
|
|
|
|
<p>
|
|
Here are visualizations of common sorting algorithms. Use the comparisons counter
|
|
and number of items to observe the performance of each randomized case.
|
|
</p>
|
|
|
|
<p>
|
|
All source data is shuffled using the <a href='http://blog.codinghorror.com/the-danger-of-naivete/'>Fisher-Yates</a> algorithm.
|
|
</p>
|
|
|
|
<p>
|
|
There's a fun clip about the sounds of sorting <a href="https://www.youtube.com/watch?v=t8g-iYGHpEA">here</a>.
|
|
</p>
|
|
|
|
<h3>Quick sort discussion</h3>
|
|
|
|
<a class='src' href='http://gogs.benburlingham.com/ben.burlingham/d3-sort-visualization/src/master/js/quicksort.js'>Source Code</a>
|
|
|
|
<p>
|
|
<span class='title'>Implementation</span>
|
|
<ul>
|
|
<li>Select a pivot element anywhere in the list</li>
|
|
<li>Uses "left" and "right" markers that approach each other from opposite ends of the list</li>
|
|
<li>Left marker halts if its current value is greater than pivot</li>
|
|
<li>Right marker halts if its current value is less than pivot</li>
|
|
<li>Swap after both markers are halted, then continue moving inwards</li>
|
|
<li>Once markers pass eachother, recurse for sublists on each side of pivot</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<p>
|
|
<span class='title'>Notes</span>
|
|
<ul>
|
|
<li>"Conquer and divide" algorithm</li>
|
|
<li>Performance depends heavily on pivot selection</li>
|
|
<li>O(n) time possible with partitioning</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<div class="sorter"
|
|
data-algorithm='quick'
|
|
data-stable='No'
|
|
data-adaptive='No'
|
|
data-worst-perf='O (n^2)'
|
|
data-avg-perf='O (n log n)'
|
|
data-best-perf='O (n log n)'
|
|
data-worst-memory='0'
|
|
></div>
|
|
|
|
<hr>
|
|
|
|
<h3>Merge sort discussion</h3>
|
|
|
|
<a class='src' href='http://gogs.benburlingham.com/ben.burlingham/d3-sort-visualization/src/master/js/mergesort.js'>Source Code</a>
|
|
|
|
<p>
|
|
<span class='title'>Implementation</span>
|
|
<ul>
|
|
<li>Recursively split array until only single element slices remain.</li>
|
|
<li>Consider two slices. Compare their heads and unshift minimum into a result array.</li>
|
|
<li>Continue comparing heads and unshifting until the two slices are empty.</li>
|
|
<li>Build result arrays from all the slices.</li>
|
|
<li>Recurse the comparison process on the result arrays.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<p>
|
|
<span class='title'>Notes</span>
|
|
<ul>
|
|
<li>Top down variant: Recursively split into halves, sort halves depth first, ending with original two halves. Tree-like. Implemented here.</li>
|
|
<li>Bottom up variant: Split fixed intervals, sort each interval, join into full array, split larger interval, repeat.</li>
|
|
<li>Natural variant: Bottom up, but with adaptive interval selection over existing ordering.</li>
|
|
<li><a href="http://stackoverflow.com/questions/10153393/mergesort-is-bottom-up-faster-than-top-down">Discussion of variants</a></li>
|
|
</ul>
|
|
</p>
|
|
|
|
<div class="sorter"
|
|
data-algorithm='merge'
|
|
data-stable='Yes'
|
|
data-adaptive='Yes'
|
|
data-worst-perf='O (n log n)'
|
|
data-avg-perf='O (n log n)'
|
|
data-best-perf='O (n log n)'
|
|
data-worst-memory='O (n)'
|
|
></div>
|
|
|
|
<hr>
|
|
|
|
<h3>Selection sort discussion</h3>
|
|
|
|
<a class='src' href='http://gogs.benburlingham.com/ben.burlingham/d3-sort-visualization/src/master/js/selectionsort.js'>Source Code</a>
|
|
|
|
<p>
|
|
<span class='title'>Implementation</span>
|
|
<ul>
|
|
<li>Consider [0]. Compare it to the rest of the elements to find the minimum value.</li>
|
|
<li>Swap [0] with the index of the minimum. [0] is now finished.</li>
|
|
<li>Proceed to [1]. Repeat.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<p>
|
|
<span class='title'>Notes</span>
|
|
<ul>
|
|
<li>To remember: selection sort selects the minimum.</li>
|
|
<li>Be aware of the unstable version, where a swap is greedy.</li>
|
|
<li>No other sorting algorithm has less data movement (<a href="http://rosettacode.org/wiki/Sorting_algorithms/Selection_sort">Rosetta Code</a>)</li>
|
|
<li>Good for cases where writes are expensive.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<div class="sorter"
|
|
data-algorithm='selection'
|
|
data-stable='Yes'
|
|
data-adaptive='No'
|
|
data-worst-perf='O (n^2)'
|
|
data-avg-perf='O (n^2)'
|
|
data-best-perf='O (n^2)'
|
|
data-worst-memory='0'>
|
|
</div>
|
|
|
|
<hr>
|
|
|
|
<h3>Insertion sort discussion</h3>
|
|
|
|
<a class='src' href='http://gogs.benburlingham.com/ben.burlingham/d3-sort-visualization/src/master/js/insertionsort.js'>Source Code</a>
|
|
|
|
<p>
|
|
<span class='title'>Implementation</span>
|
|
<ul>
|
|
<li>Compare [1] and [0]. Swap if [0] > [1].</li>
|
|
<li>Compare [2] and [1]. Swap if needed. Continue swapping downward one by one until no swap is needed.</li>
|
|
<li>Repeat with [3], [4], etc. until end of the array.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<p>
|
|
<span class='title'>Notes</span>
|
|
<ul>
|
|
<li>Simplicity can make insertion sort a good choice for small arrays.</li>
|
|
<li>Similar to selection sort, but uses bubbling rather than minimums.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<div class="sorter"
|
|
data-algorithm='insertion'
|
|
data-stable='Yes'
|
|
data-adaptive='Yes'
|
|
data-worst-perf='O (n^2)'
|
|
data-avg-perf='O (n^2)'
|
|
data-best-perf='O (n)'
|
|
data-worst-memory='0'
|
|
></div>
|
|
|
|
<hr>
|
|
|
|
<h3>Shellsort discussion</h3>
|
|
|
|
<a class='src' href='http://gogs.benburlingham.com/ben.burlingham/d3-sort-visualization/src/master/js/shellsort.js'>Source Code</a>
|
|
|
|
<p>
|
|
<span class='title'>Implementation</span>
|
|
<ul>
|
|
<li>Decide on a gap width. 3 is used here.</li>
|
|
<li>Start at [3]. Compare to [0]. Swap if [0] > [3].</li>
|
|
<li>Move to [4]. Compare to [1]. Swap if necessary.</li>
|
|
<li>Move to [5]. Compare to [2]. Swap if necessary.</li>
|
|
<li>Continue the pattern and bubble downstream, exactly like insertion sort but with a gap of 3, not 1.</li>
|
|
<li>After the end of the list is reached, it is weakly sorted. Perform a final insertion sort.</li>
|
|
<li>Note: Insertion sort is a shell sort with a gap of 1.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
|
|
<p>
|
|
<span class='title'>Notes</span>
|
|
<ul>
|
|
<li>Weakly sorts elements to prepare for final pass using different sort algorithm</li>
|
|
<li>Average performance depends on gap selection, but...</li>
|
|
<li>Dependence on input data makes gap selection highly subjective</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<div class="sorter"
|
|
data-algorithm='shell'
|
|
data-stable='No'
|
|
data-adaptive='Yes'
|
|
data-worst-perf='O (n^2)'
|
|
data-avg-perf='-'
|
|
data-best-perf='O (n lg n)'
|
|
data-worst-memory='n'
|
|
></div>
|
|
|
|
<hr>
|
|
|
|
<h3>Bubble sort discussion</h3>
|
|
|
|
<a class='src' href='http://gogs.benburlingham.com/ben.burlingham/d3-sort-visualization/src/master/js/bubblesort.js'>Source Code</a>
|
|
|
|
<p>
|
|
<span class='title'>Implementation</span>
|
|
<ul>
|
|
<li>Order [1] and [0].</li>
|
|
<li>Order [2] and [1].</li>
|
|
<li>Continue to the end. Note that there is at most one swap per index.</li>
|
|
<li>Repeat the process until fully ordered. Keep a boolean that shows if swaps have been made.</li>
|
|
<li>Once there is a pass without swaps, all elements have bubbled down to their proper positions.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<p>
|
|
<span class='title'>Notes</span>
|
|
<ul>
|
|
<li>If even one number is out of place means a new pass must be done.</li>
|
|
<li>"Turtles" are small values that crawl slowly toward their position near the front.</li>
|
|
<li>"Rabbits" are large values that hop quickly to their position near the end.</li>
|
|
<li>Variations on bubble sort (cocktail sort, comb sort) try to address the turtle problem.</li>
|
|
</ul>
|
|
</p>
|
|
|
|
<div class="sorter"
|
|
data-algorithm='bubble'
|
|
data-stable='Yes'
|
|
data-adaptive='Yes'
|
|
data-worst-perf='O (n^2)'
|
|
data-avg-perf='O (n^2)'
|
|
data-best-perf='O (n)'
|
|
data-worst-memory='0'
|
|
></div>
|
|
|
|
<!--
|
|
<h3>radix sort discussion</h3>
|
|
|
|
<div class="sorter" data-algorithm='radix'></div>
|
|
|
|
<!--
|
|
<h3>Heapsort discussion</h3>
|
|
|
|
<div class="sorter"></div>
|
|
|
|
<h3>Bubblesort discussion</h3>
|
|
NOTE http://stackoverflow.com/questions/17270628/insertion-sort-vs-bubble-sort-algorithms
|
|
<div class="sorter"></div>
|
|
|
|
<h3>Radixsort discussion</h3>
|
|
|
|
<div class="sorter"></div>
|
|
-->
|
|
|
|
<script type="text/javascript" src='../core/js/ui.js'></script>
|
|
<script type="text/javascript" src='../core/js/prism.js'></script>
|
|
|
|
<script type='text/javascript' src='vendor/d3/d3.min.js'></script>
|
|
<script type='text/javascript' src='js/visualizer.js'></script>
|
|
<script type='text/javascript' src='js/itemgroup.js'></script>
|
|
<script type='text/javascript' src='js/visualizer-dom.js'></script>
|
|
<script type='text/javascript' src='js/sorter.js'></script>
|
|
<script type='text/javascript' src='js/quicksort.js'></script>
|
|
<script type='text/javascript' src='js/mergesort.js'></script>
|
|
<script type='text/javascript' src='js/insertionsort.js'></script>
|
|
<script type='text/javascript' src='js/shellsort.js'></script>
|
|
<script type='text/javascript' src='js/selectionsort.js'></script>
|
|
<script type='text/javascript' src='js/bubblesort.js'></script>
|
|
<script type='text/javascript' src='js/radixsort.js'></script>
|
|
|
|
<script type='text/javascript'>
|
|
var dump = function(arr) {
|
|
var d = [];
|
|
arr.forEach(function(obj) {
|
|
d.push(obj.value);
|
|
})
|
|
|
|
return d.join(',');
|
|
};
|
|
|
|
|
|
// Wrap anonymous function to avoid polluting global namespace.
|
|
(function() {
|
|
var elements = document.querySelectorAll('.sorter');
|
|
var V;
|
|
for (key in elements) {
|
|
if (elements.hasOwnProperty(key)) {
|
|
new Visualizer(elements[key]);
|
|
}
|
|
}
|
|
})();
|
|
</script>
|
|
</body>
|
|
</html>
|
|
|