λ Quicksort in-place

======= Algorithm ======= <syntax js> function partition(a, left, right, pivotIndex) { // left is the index of the leftmost element of the subarray // right is the index of the rightmost element of the subarray (inclusive) // number of elements in subarray = right-left+1 var storeIndex = left; var pivotValue = a[pivotIndex]; // Move pivot to end. swap(a, pivotIndex, right); // left ≤ i < right for (var i=left; i<right; i++) { if (a[i] <= pivotValue) { swap(a, i, storeIndex); storeIndex++; } } // Move pivot to its final place. swap(a, storeIndex, right); return storeIndex; } function quicksort(a, left, right) { // If the array has 2 or more items. if (left < right) { // Choose the middle value as a pivot. var pivotIndex = Math.floor((left+right)/2); // Get lists of bigger and smaller items and final position of pivot. var pivotNewIndex = partition(a, left, right, pivotIndex); // Recursively sort elements smaller than the pivot. quicksort(a, left, pivotNewIndex - 1); // Recursively sort elements at least as big as the pivot. quicksort(a, pivotNewIndex + 1, right); } } </syntax> ======= Support ======= <syntax js> function swap(a, i, j) { var t = a[i]; a[i] = a[j]; a[j] = t; } function run(a) { result = quicksort(a, 0, a.length-1); } </syntax> ======= Tests ======= <syntax js> </syntax> ======= Options ======= <syntax js> { "title":"Quicksort in-place", "height":"550px" } </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 left = x? x.lookupInScope("left") : -1; var right = x? x.lookupInScope("right") : -1; var sortingDepth = repeat(-1, array.length); 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 i >= left && i <= right; }); // draw pivot var pivot = null; if (x) { pivot = x.lookupInScope("pivotValue"); if (typeof pivot === "undefined") { pivot = x.lookupInScope("pivotIndex"); pivot = a[pivot]; } } 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>