λ Bucket sort

======= Algorithm ======= <syntax js> function bucketSort(array, max, numBuckets) { var buckets = new Array(10); // Add all the values to the buckets, uniformly dividing the numbers // into ordered buckets (insertion sort on a linked-list). for (var i=0, c=array.length; i<c; i++) { var slot = Math.floor(array[i]/(1+max)*numBuckets); if (!buckets[slot]) { buckets[slot] = new LinkedList(); } buckets[slot].insertOrdered(array[i]); } // Get all the value out of the buckets in order. var outputIndex = 0; for (var j=0, c=buckets.length; j<c; j++) { if (buckets[j]) { buckets[j].forEach(function(x) { array[outputIndex++] = x; }); } } }</syntax> ======= Support ======= <syntax js> var toSort = []; for (var genIndex=0; genIndex<20; genIndex++) { toSort.push(Math.floor(Math.random()*100)); } function run() { bucketSort(toSort, 100, 10); } LinkedList.prototype.insertOrdered = function(data) { var insertOrderedNode = function(node, data) { if (!node || data <= node.data) { node = new LinkedList.Node(data, node); } else { node.next = insertOrderedNode(node.next, data); } return node; } this.first = insertOrderedNode(this.first, data); } LinkedList.prototype.forEach = function(callback) { var n = this.first; while (n) { callback(n.data); n = n.next; } }</syntax> ======= Tests ======= <syntax js> /* Unit tests… function testA() { if (!ok) { throw "Not ok." } } */ </syntax> ======= Options ======= <syntax js> { "title":"Bucket sort", "height":"450px", "import": ["linked-list"] }</syntax> ======= Visualisation ======= <syntax html> <html> <head> <script src="http://d3js.org/d3.v3.js"></script> <script src="algorithms-lib/list.v2.js"></script> <link rel="stylesheet" type="text/css" href="algorithms-lib/list.css"/> <style type='text/css'> input { width: 50px; } .array rect { fill: #eef; stroke: #ccf; } .added text { opacity: 0.25; } svg { font-family: Verdana, Helvetica; font-size: 12px; } </style> <script> function setup() { svg = d3.select("#result") .append("svg") .attr("width", 348) .attr("height", 450) .append("g").attr("transform", "translate(20.5,20.5)"); returnText = svg.append("text") .attr("dx", "0") .attr("dy", "40"); listVis = new ListVisualisation(svg); } var poppedMarker = {}; function globals() { // Return a unique marker that enables to identify when popped has not been set. return {"popped": poppedMarker}; } var nodeIndex = 0; function idNode(node) { if (!node.hasOwnProperty("id")) { node.id = nodeIndex++; } } function updateArray(x, clean, duration) { var array = x.lookupInScope("array"); array = array? array : x.lookupInScope("toSort"); // Create lists. for (var i=0;i<array.length;i++) { var node = {x:i%10*32, y:Math.floor(i/10)*38, value:array[i], id:"array"+i, classname:"array", arrayIndex:i}; listVis.elements.push(node); } } function updateHash(x, clean, duration) { var buckets = x.lookupInScope("buckets"); // Create lists. listVis.elements = []; buckets = buckets? buckets : []; for (var i=0;i<buckets.length;i++) { var list = buckets[i]; if (list) { // Copy in list. var x = 60; var n = list.first; while (n) { n.x = x; x += 60; n.y = i*32 + 82; n.hashIndex = listVis.elements.length; idNode(n); listVis.elements.push(n); n = n.next; } } } for (var i=0;i<buckets.length;i++) { listVis.elements.push({x:0, y:32*i+82, id:"ptr"+i, value:buckets[i]? buckets[i].first : null}); } } function update(n, x, isRunning, duration) { // Update the d3 visualisation. updateHash(x, false, duration); updateArray(x, false, duration); // Highlight selected slot. var sortIndex = x.lookupInScope("i"); var saveIndex = x.lookupInScope("outputIndex"); if (typeof sortIndex !== "number") sortIndex = -1; if (typeof saveIndex !== "number") saveIndex = -1; svg.select("#list-data").selectAll("g") .data(listVis.elements, function(d) {return d.id;}) .classed("added", function(d, j) { return (typeof d.arrayIndex === "number" && d.arrayIndex >= saveIndex && d.arrayIndex < sortIndex) || (typeof d.hashIndex === "number" && d.hashIndex < saveIndex); }); listVis.update(duration); } window.onload = function() { setup(); }; </script> </head> <body style="height:480px"> <div id=result> </div> </body> </html></syntax>