User Tools

Site Tools


Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
algorithm:insertion_sort [2013/05/04 11:32]
will
algorithm:insertion_sort [2015/02/02 08:28] (current)
Line 1: Line 1:
-[algorithm ​Insertion sort]+======= λ Insertion sort ======
  
-====== Algorithm ======+<​nowiki>​ 
 +======= Algorithm ​=======
 <syntax js> <syntax js>
 function insertSort(a) { function insertSort(a) {
Line 10: Line 11:
         }         }
     }     }
-    ​ 
-    return a; 
 } }
 </​syntax>​ </​syntax>​
  
-====== Support ======+======= Support ​=======
 <syntax js> <syntax js>
 function swap(a, i, j) { function swap(a, i, j) {
Line 28: Line 27:
 </​syntax>​ </​syntax>​
  
-====== Options ======+======= Tests ======= 
 +<syntax js> 
 +</​syntax>​ 
 + 
 +======= Options ​=======
 <syntax js> <syntax js>
 { {
 +    "​title":​ "​Insertion sort",
     "​height":​ "​270px"​     "​height":​ "​270px"​
 } }
 </​syntax>​ </​syntax>​
  
-====== Visualisation ======+======= Visualisation ​=======
 <syntax html> <syntax html>
 <​html>​ <​html>​
 <​head>​ <​head>​
-<style type='text/css'>​ +<link rel="​stylesheet" ​type="text/css" href="​algorithms-lib/​graph.css"/>
-.chart rect { +
-  fill: steelblue;​ +
-  notstroke: white; +
-+
-.chart rect.sorted { +
-  fill: lightsteelblue;​ +
-+
-.chart rect.index { +
-  fill: red; +
-+
-</style>+
 <script src="​http://​d3js.org/​d3.v2.js"></​script>​ <script src="​http://​d3js.org/​d3.v2.js"></​script>​
 +<script src="​algorithms-lib/​graph.js"></​script>​
 <script type="​text/​javascript">​ <script type="​text/​javascript">​
-var chart+var graph = new Graph(20)
-var width = 300;+
 window.onload = function() { window.onload = function() {
-    ​// Setup the chart +    chart = graph.createGraph(d3.select("#​chart"​))
-    ​chart = d3.select("#​chart"​).append("​svg"​) +
-        .attr("​class",​ "​chart"​) +
-        .attr("​width",​ width) +
-        .attr("​height",​ 256); +
-    drawGraph(a,​ -1, -1, 100);+
 } }
  
-function ​rndNum() { +function ​args(forCloning) { 
-    return ​1 + Math.floor(Math.random()*20);+    return ​forCloning? graph.getClonableArray() : graph.array;
 } }
- 
-var a = []; 
-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() { 
-    for (var j=0; j<20; j++) { 
-        a[j].data = rndNum(); 
-    } 
-    reset(); 
-    drawGraph(a,​ -1, -1, 100); 
     ​     ​
-    ​var bars = chart.selectAll("​rect"​).data(a,​ function(d) {return d.hash;​});​ +var lastUpdateDate ​= 0;
-     +
-    bars.transition(100) +
-        .attr("​y",​ function(d) { return 256 - d*10; }) +
-        .attr("​height",​ function(d) { return d*10; }); +
-+
-function reverse() { +
-    for (var j=0; j<10; j++) { +
-        t = a[j]; a[j] = a[19-j]; a[19-j] = t; +
-    } +
-    reset(); +
-    drawGraph(a,​ -1, -1, 100); +
-}+
  
-function args() { +function update(n, x, isRunning, duration, prev) {
-    return a; +
-+
- +
-function update(n, x, duration) {+
     if (duration < 0) {     if (duration < 0) {
         return; // State-less visualisation.         return; // State-less visualisation.
     }     }
     if (x) {     if (x) {
 +        graph.drawGraph(duration,​ 0);
 +        ​
 +        var sortedN = x.lookupInScope("​sortedN"​);​
         var idx = x.lookupInScope("​i"​);​         var idx = x.lookupInScope("​i"​);​
-        var sortedN ​x.lookupInScope("​sortedN"​);​+        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++; 
 +    } 
 +        bars.classed("sorted",​ function(d, i) {return sortedN && i<​sortedN});
         ​         ​
-        ​drawGraph(a,​ idx, sortedN, duration); +        ​// Unfortunate use of line numbers to highlight index being moved. 
-    } +        if (!n || (n.lineno !== 4 && n.lineno !== 5)){ 
-+         bars.classed("index", ​false); 
- +        } 
-var oldI; +        ​else if (n.lineno === 5) { 
- +            bars.classed("​index",​ function(d, i) {return i===idx});​ 
-function drawGraph(a, idx, sortedN, duration) { +        }
-    var = a.length; +
-    var barWidth ​Math.floor((width-20-2*(n-1))/​n);​ +
-    var barSpacing ​barWidth+2;​ +
-     +
-    var bars chart.selectAll("​rect"​).data(a, function(d) {return d.hash;}); +
-     +
-    ​bars.enter().append("rect"​) +
-        .attr("​y", ​function(d{ return 256 - d*10}) +
-        ​.attr("​height",​ function(d) { return d*10; }) +
-        ​.attr("​width",​ barWidth);​ +
-     +
-    bars.transition().duration(duration).attr("​x",​ function(d, i) { return barSpacing*i;​ }); +
-    if (idx!==oldI) { +
-        bars.classed("​index",​ function(d, i) {return i===idx});​ +
-        ​oldI = idx; +
-    ​} +
-    // Increase the sorted section when we have an index being moved down. +
-    if (typeof idx !== "​undefined"​) { +
-        sortedN++;+
     }     }
-    bars.classed("​sorted",​ function(d, i) {return sortedN && i<​sortedN});​ 
 } }
 </​script>​ </​script>​
Line 148: Line 88:
 <​body>​ <​body>​
   <div style="​position:​absolute;​padding:​2px">​   <div style="​position:​absolute;​padding:​2px">​
-    <button onclick="​randomise()">​Random</​button>​ +    <button onclick="​graph.randomise(200)">​Random</​button>​ 
-    <button onclick="​reverse()">​Reverse</​button>​+    <button onclick="​graph.randomise(5)">​Few Unique</​button>​ 
 +    <button onclick="​graph.almostSorted()">​Almost sorted</​button>​ 
 +    <button onclick="​graph.reverse()">​Reverse</​button>​
   </​div>​   </​div>​
 <div id="​chart"></​div>​ <div id="​chart"></​div>​
Line 155: Line 97:
 </​html>​ </​html>​
 </​syntax>​ </​syntax>​
 +</​nowiki>​
algorithm/insertion_sort.1367692321.txt.gz · Last modified: 2015/02/02 08:23 (external edit)