# λ Quick sort

======= Algorithm ======= <syntax js> function quickSort(a) { // If the array is 1 or less in size it is already sorted. if (a.length <= 1) { return a; } // Pick a pivot from the middle of the array. var pivotIndex = Math.floor(a.length/2); var pivot = a[pivotIndex]; var less = [], greater = []; // Iterate over all items in the array and put them in less or greater. for (var i=0; i<a.length; i++) { if (i === pivotIndex) { // Skip the pivot. continue; } if (a[i] <= pivot) { less.push(a[i]); } else { greater.push(a[i]); } } // Recurse and sort the arrays less and greater using quickSort. var sortedLess = quickSort(less); var sortedGreater = quickSort(greater); // Return the sorted array by concatenating less, pivot and greater. return sortedLess.concat([pivot], sortedGreater); } </syntax> ======= Support ======= <syntax js> function run(a) { result = quickSort(a); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Quick sort", "height":"490px" } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <style type='text/css'> .chart rect.data { fill: steelblue; notstroke: white; } .chart rect.subrange { fill: purple; } .chart rect.index { fill: red; } .chart rect.pivot { fill: red; } </style> <script src="http://d3js.org/d3.v2.js"></script> <script type="text/javascript"> var chart; var width = 300; window.onload = function() { // Setup the chart chart = d3.select("#chart").append("svg") .attr("class", "chart") .attr("width", width) .attr("height", 256); chart.append("g"); chart.append("rect") .attr("class", "pivot") .attr("height", 2) .attr("width", 278) .attr("x", 0) .attr("y", -10); } function rndNum() { return 1 + Math.floor(Math.random()*200); } var a = []; var visualisedArray; var hashIndex = 0; function n(d) { this.data = d; // Save a hash so we can uniquely identify each number. this.hash = ""+hashIndex; hashIndex++; this.valueOf = function() {return this.data;}; } for (var j=0; j<20; j++) { a.push(new n(rndNum())); } function randomise() { var from = visualisedArray? visualisedArray.slice() : a; for (var j=0; j<20; j++) { //a[j] = from[j]; a[j].data = rndNum(); } reset(); drawGraph(null, null, 100); var bars = chart.select("g").selectAll(".data").data(a, function(d) {return d.hash;}); bars.transition(100) .attr("y", function(d) { return 256 - d; }) .attr("height", function(d) { return d; }); } function reverse() { var from = visualisedArray? visualisedArray.slice() : a.slice(); for (var j=0; j<20; j++) { a[j] = from[19-j]; } reset(); drawGraph(null, null, 100); } function repeat(s, n) { var r = []; for (var i=0;i<n;i++) { r.push(s); } return r; } function args(forCloning) { if (forCloning) { var newA = []; for (var i=0, c=a.length; i<c; i++) { newA.push(a[i].data); } return newA; } return a; } function globals() { return { result: undefined }; } function update(n, x, isRunning, duration, prev) { if (duration < 0) { return; // State-less visualisation. } if (x) { drawGraph(n, x, duration); } } function drawGraph(n, x, duration) { var array = a; var index = x? x.lookupInScope("i") : -1; var sortingDepth = repeat(-1, array.length); // put together complete array from recursion if (x && x.lookupInScope("a")) { array = x.lookupInScope("a"); sortingDepth = repeat(0, array.length); var sortedLess = x.lookupInScope("sortedLess"); if (!sortedLess) { if (n && n.lineno === 28 && x.returnedValue) { sortedLess = x.returnedValue; } } if (sortedLess) { var greater = x.lookupInScope("greater"); var sortedGreater = x.lookupInScope("sortedGreater"); if (!sortedGreater) { if (n && n.lineno === 29 && x.returnedValue) sortedGreater = x.returnedValue; } var pivot = x.lookupInScope("pivot"); array = sortedLess.concat([pivot], sortedGreater? sortedGreater : greater); } // recurse down stack var stack = x.stack; for (var i=stack.length-2; i>=0; i--) { var x2 = stack[i]; var sortedLess = x2.lookupInScope("sortedLess"); var greater = x2.lookupInScope("greater"); var pivot = x2.lookupInScope("pivot"); if (pivot) { if (sortedLess) { array = sortedLess.concat([pivot], array); var d = stack.length-i; sortingDepth = repeat(d, sortedLess.length).concat([d], sortingDepth); } else { array = array.concat([pivot], greater); var d = stack.length-i; sortingDepth = sortingDepth.concat([d], repeat(d, greater.length)); } } } var startI = -1, endI=array.length; for (var i=0; i<array.length; i++) { var d = sortingDepth[i]; if (startI < 0 && d === 0) { startI = i; } if (startI>=0 && d !== 0) { endI = i; break; } } index += startI; if (index >= endI) index = -1; } else if (x && x.lookupInScope("result")) { array = x.lookupInScope("result"); } visualisedArray = array; var n = array.length; var barWidth = Math.floor((width-20-2*(n-1))/n); var barSpacing = barWidth+2; var bars = chart.select("g").selectAll(".data").data(array, function(d) {return d.hash;}); bars.enter().append("rect") .attr("class", "data") .attr("y", function(d) { return 256 - d; }) .attr("height", function(d) { return 0+d; }) .attr("width", barWidth); bars.transition().duration(duration).attr("x", function(d, i) { return barSpacing*i; }); bars.classed("index", function(d, i) { return i===index; }); bars.classed("subrange", function(d, i) { return sortingDepth[i] === 0; }); // draw pivot pivot = x? x.lookupInScope("pivot") : null; var pivotMarker = chart.select(".pivot"); if (pivot) { pivotMarker.attr("y", 256 - pivot); } else pivotMarker.attr("y", -10); } </script> </head> <body> <div style="position:absolute;padding:2px"> <button onclick="randomise()">Random</button> <button onclick="reverse()">Reverse</button> </div> <div id="chart"></div> </body> </html> </syntax>