λ Shell sort

======= Algorithm ======= <syntax js> function shellSort(a) { var gaps = [5, 3, 1]; // Sort all elements using each gap in turn. for (var j = 0; j < gaps.length; j++) { var gap = gaps[j]; for (var start = 0; start<a.length && start<gap; start++) { insertSortGap(a, start, gap); } } return a; } function insertSortGap(a, start, gap) { // An insertion sort which sorts every 'gap' element starting from 'start'. for (var sortedN = start+gap; sortedN < a.length; sortedN += gap) { // Shift unsorted value downwards until it is sorted. for (var i = sortedN; i > 0 && a[i] < a[i-gap]; i -= gap) { swap(a, i, i-gap); } } } </syntax> ======= Support ======= <syntax js> function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function run(a) { shellSort(a); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title": "Shell sort", "height": "320px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <link rel="stylesheet" type="text/css" href="algorithms-lib/graph.css"/> <style type='text/css'> .chart rect.skipped { fill: #EEE; } </style> <script src="http://d3js.org/d3.v2.js"></script> <script src="algorithms-lib/graph.js"></script> <script type="text/javascript"> var graph = new Graph(20); window.onload = function() { chart = graph.createGraph(d3.select("#chart")) } function args(forCloning) { return forCloning? graph.getClonableArray() : graph.array; } var oldI; function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } if (x) { graph.drawGraph(duration); var sortedN = x.lookupInScope("sortedN"); var idx = x.lookupInScope("i"); var start = x.lookupInScope("start"); var gap = x.lookupInScope("gap"); var bars = chart.selectAll("rect.data").data(graph.array, function(d) {return d.hash;}); // Increase the sorted section when we have an index being moved down. if (typeof idx !== "undefined") { sortedN++; } // Increase the sorted section when we have an index being moved down. if (typeof idx !== "undefined") { sortedN++; } if (idx !== oldI) { bars.classed("index", function(d, i) {return i===idx}); oldI = idx; } // Catch cases just before starting a new gap sequence. if (typeof gap !== "undefined") { if (start == gap) { start = gap-1; } if (start > gap) { start = 0; } } bars.classed("skipped", function(d, i) {return typeof start !== "undefined" && (i-start)%gap !== 0}); if (typeof start === "undefined") { start=0; } bars.classed("sorted", function(d, i) {return sortedN && i<sortedN && (i-start)%gap === 0}); } } </script> </head> <body> <div style="position:absolute;padding:2px"> <button onclick="graph.randomise(200)">Random</button> <button onclick="graph.randomise(5)">Few Unique</button> <button onclick="graph.almostSorted()">Almost sorted</button> <button onclick="graph.reverse()">Reverse</button> </div> <div id="chart"></div> </body> </html> </syntax>