add Selection Sort

64json · 64json · commit 13a7881fe27c · 2016-05-19T19:58:13.000-05:00
diff --git a/algorithm/sorting/insertion/basic/data.js b/algorithm/sorting/insertion/basic/data.js
@@ -1,3 +1,3 @@
 var tracer = new Array1DTracer();
-var D = tracer.createRandomData();
+var D = tracer.createRandomData(15);
 tracer.setData(D);
diff --git a/algorithm/sorting/selection/basic/code.js b/algorithm/sorting/selection/basic/code.js
@@ -0,0 +1,23 @@
+tracer._print('original array = [' + D.join(', ') + ']');
+tracer._sleep(1000);
+tracer._pace(500);
+for (var i = 0; i < D.length - 1; i++) {
+    var minJ = i;
+    tracer._select(i);
+    for (var j = i + 1; j < D.length; j++) {
+        if (D[j] < D[minJ]) {
+            tracer._select(j);
+            minJ = j;
+            tracer._deselect(j);
+        }
+    }
+    if (minJ != i) {
+        tracer._print('swap ' + D[i] + ' and ' + D[minJ]);
+        var temp = D[i];
+        D[i] = D[minJ];
+        D[minJ] = temp;
+        tracer._notify(i, minJ);
+    }
+    tracer._deselect(i);
+}
+tracer._print('sorted array = [' + D.join(', ') + ']');
diff --git a/algorithm/sorting/selection/basic/data.js b/algorithm/sorting/selection/basic/data.js
@@ -0,0 +1,3 @@
+var tracer = new Array1DTracer();
+var D = tracer.createRandomData(15);
+tracer.setData(D);
diff --git a/algorithm/sorting/selection/config.json b/algorithm/sorting/selection/config.json
@@ -0,0 +1,14 @@
+{
+  "def": "Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and it has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.",
+  "apps": [],
+  "cpx": {
+    "time": "O(n<sup>2</sup>)",
+    "space": "O(n)"
+  },
+  "refs": [
+    "https://en.wikipedia.org/wiki/Selection_sort"
+  ],
+  "files": {
+    "basic": "Basic"
+  }
+}
diff --git a/js/module/array1d.js b/js/module/array1d.js
@@ -17,8 +17,12 @@ Array1DTracer.prototype.setData = function (D) {
 };
 
 // Override
-Array1DTracer.prototype._notify = function (idx) {
-    Array2DTracer.prototype._notify.call(this, 0, idx);
+Array1DTracer.prototype._notify = function (idx1, idx2) {
+    if (idx2 === undefined) {
+        Array2DTracer.prototype._notify.call(this, 0, idx1);
+    } else {
+        Array2DTracer.prototype._notify.call(this, 0, idx1, 0, idx2);
+    }
 };
 
 // Override
diff --git a/js/module/array2d.js b/js/module/array2d.js
@@ -59,9 +59,12 @@ Array2DTracer.prototype.setData = function (D) {
     return false;
 };
 
-Array2DTracer.prototype._notify = function (x, y) {
-    this.pushStep({type: 'notifying', x: x, y: y, value: this.D[x][y]}, true);
-    this.pushStep({type: 'notified', x: x, y: y}, false);
+Array2DTracer.prototype._notify = function (x1, y1, x2, y2) {
+    var second = x2 !== undefined && y2 !== undefined;
+    this.pushStep({type: 'notifying', x: x1, y: y1, value: this.D[x1][y1]}, !second);
+    if (second) this.pushStep({type: 'notifying', x: x2, y: y2, value: this.D[x2][y2]}, true);
+    this.pushStep({type: 'notified', x: x1, y: y1}, false);
+    if (second) this.pushStep({type: 'notified', x: x2, y: y2}, false);
 };
 
 Array2DTracer.prototype._select = function (sx, sy, ex, ey) {
diff --git a/js/module/graph.js b/js/module/graph.js
@@ -37,7 +37,6 @@ GraphTracer.prototype.createRandomData = function (N, ratio) {
             else G[i].push((Math.random() * (1 / ratio) | 0) == 0 ? 1 : 0);
         }
     }
-    console.log(G);
     return G;
 };
 
@@ -86,7 +85,7 @@ GraphTracer.prototype.setTreeData = function (G, root) {
 // Override
 GraphTracer.prototype.setData = function (G) {
     if (Tracer.prototype.setData.call(this, arguments)) return true;
-
+    
     graph.clear();
     var nodes = [];
     var edges = [];
diff --git a/js/module/weighted_graph.js b/js/module/weighted_graph.js
@@ -34,13 +34,12 @@ WeightedGraphTracer.prototype.createRandomData = function (N, ratio, min, max) {
             }
         }
     }
-    console.log(G);
     return G;
 };
 
 // Override
 WeightedGraphTracer.prototype.setData = function (G) {
-    if (Tracer.prototype.setData.call(this, arguments)) return;
+    if (Tracer.prototype.setData.call(this, arguments)) return true;
 
     graph.clear();
     var nodes = [];
@@ -83,6 +82,8 @@ WeightedGraphTracer.prototype.setData = function (G) {
         ratio: 1
     });
     this.refresh();
+
+    return false;
 };
 
 GraphTracer.prototype._weight = function (target, weight, delay) {
@@ -99,7 +100,6 @@ GraphTracer.prototype._leave = function (target, source, weight) {
 
 //Override
 WeightedGraphTracer.prototype.processStep = function (step, options) {
-    console.log(step);
     switch (step.type) {
         case 'weight':
             var targetNode = graph.nodes(n(step.target));
diff --git a/js/tracer.js b/js/tracer.js
@@ -32,7 +32,7 @@ Tracer.prototype.createRandomData = function (arguments) {
 
 Tracer.prototype.setData = function (arguments) {
     var data = JSON.stringify(arguments);
-    if (lastData == data) return true;
+    if (lastModule == this.module && lastData == data) return true;
     lastData = data;
     return false;
 };

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,3 @@`
	`1`	`+var tracer = new Array1DTracer();`
	`2`	`+var D = tracer.createRandomData(15);`
	`3`	`+tracer.setData(D);`