λ Cocktail sort

======= Algorithm ======= <syntax js> function cocktailSort(a) { var swapped; var first_swap; var first_swap_new; var last_swap; var last_swap_new; first_swap = 0; last_swap = a.length - 1; do { swapped = false; for (var i=first_swap; i<last_swap; i++) { // if items are out of order swap them if (a[i] > a[i+1]) { swap(a, i, i+1); last_swap_new = i; swapped = true; } } first_swap_new = last_swap_new; for (var i=last_swap_new; i>=first_swap; i--) { // if items are out of order swap them if (a[i] > a[i+1]) { swap(a, i, i+1); first_swap_new = i; } } last_swap = last_swap_new; first_swap = first_swap_new; } while(swapped); return a; }</syntax> ======= Support ======= <syntax js> function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function run(a) { cocktailSort(a); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Cocktail sort", "height":"450px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <link rel="stylesheet" type="text/css" href="algorithms-lib/graph.css"/> <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 firstSwap = x.lookupInScope("first_swap"); var lastSwap = x.lookupInScope("last_swap"); var idx = x.lookupInScope("i"); var bars = chart.selectAll("rect.data").data(graph.array, function(d) {return d.hash;}); if (idx !== oldI) { bars.classed("index", function(d, i) {return i===idx}); oldI = idx; } if (typeof firstSwap !== "number") firstSwap = -1; if (typeof lastSwap !== "number") lastSwap = 100; bars.classed("sorted", function(d, i) {return i<firstSwap || i>lastSwap}); } } </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>