add Quicksort

64json · 64json · commit 75751ab58447 · 2016-05-20T02:44:53.000-05:00
diff --git a/algorithm/category.json b/algorithm/category.json
@@ -12,7 +12,7 @@
       "insertion": "Insertion Sort",
       "selection": "Selection Sort",
       "bubble": "Bubble Sort",
-      "quick": "Quick Sort"
+      "quick": "Quicksort"
     }
   }
 }
diff --git a/algorithm/graph_search/bfs/basic/code.js b/algorithm/graph_search/bfs/basic/code.js
@@ -12,5 +12,4 @@ function BFS(s) { // s = start node
         }
     }
 }
-
 BFS(0);
diff --git a/algorithm/graph_search/bfs/config.json b/algorithm/graph_search/bfs/config.json
@@ -10,8 +10,8 @@
     "Construction of the failure function of the Aho-Corasick pattern matcher."
   ],
   "cpx": {
-    "time": "O(|E|)",
-    "space": "O(|V|)"
+    "time": "worst O(|E|)",
+    "space": "worst O(|V|)"
   },
   "refs": [
     "https://en.wikipedia.org/wiki/Breadth-first_search"
diff --git a/algorithm/graph_search/bfs/shortest_path/code.js b/algorithm/graph_search/bfs/shortest_path/code.js
@@ -22,7 +22,6 @@ function BFS() {
     }
     return W[e];
 }
-
 var s = Math.random() * G.length | 0; // s = start node
 var e; // e = start node
 do {
diff --git a/algorithm/graph_search/dfs/all_paths/code.js b/algorithm/graph_search/dfs/all_paths/code.js
@@ -11,7 +11,6 @@ function DFS(node, parent) { // node = current node, parent = previous node
     D[node] = false; // label current node as undiscovered
     tracer._leave(node, parent);
 }
-
 var D; // D[i] indicates whether the i-th node is discovered or not
 for (var i = 0; i < G.length; i++) { // start from every node
     tracer._print('start from ' + i);
diff --git a/algorithm/graph_search/dfs/basic/code.js b/algorithm/graph_search/dfs/basic/code.js
@@ -6,5 +6,4 @@ function DFS(node, parent) { // node = current node, parent = previous node
         }
     }
 }
-
 DFS(0);
diff --git a/algorithm/graph_search/dfs/config.json b/algorithm/graph_search/dfs/config.json
@@ -14,8 +14,8 @@
     "Finding biconnectivity in graphs."
   ],
   "cpx": {
-    "time": "O(|E|)",
-    "space": "O(|V|)"
+    "time": "worst O(|E|)",
+    "space": "worst O(|V|)"
   },
   "refs": [
     "https://en.wikipedia.org/wiki/Depth-first_search"
diff --git a/algorithm/graph_search/dfs/shortest_path/code.js b/algorithm/graph_search/dfs/shortest_path/code.js
@@ -20,7 +20,6 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
     D[node] = false; // label current node as undiscovered
     tracer._leave(node, parent, 0);
 }
-
 var s = Math.random() * G.length | 0; // s = start node
 var e; // e = end node
 do {
diff --git a/algorithm/graph_search/dfs/weighted_graph/code.js b/algorithm/graph_search/dfs/weighted_graph/code.js
@@ -11,7 +11,6 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
     D[node] = false; // label current node as undiscovered
     tracer._leave(node, parent, 0);
 }
-
 var D; // D[i] indicates whether the i-th node is discovered or not
 tracer._pace(1000);
 for (var i = 0; i < G.length; i++) { // start from every node
diff --git a/algorithm/sorting/bubble/basic/code.js b/algorithm/sorting/bubble/basic/code.js
@@ -0,0 +1,22 @@
+tracer._print('original array = [' + D.join(', ') + ']');
+tracer._sleep(1000);
+tracer._pace(300);
+var N = D.length;
+var swapped;
+do {
+    swapped = false;
+    tracer._select(N - 1);
+    for (var i = 1; i < N; i++) {
+        if (D[i - 1] > D[i]) {
+            tracer._print('swap ' + D[i - 1] + ' and ' + D[i]);
+            var temp = D[i - 1];
+            D[i - 1] = D[i];
+            D[i] = temp;
+            swapped = true;
+            tracer._notify(i - 1, i);
+        }
+    }
+    tracer._deselect(N - 1);
+    N--;
+} while (swapped);
+tracer._print('sorted array = [' + D.join(', ') + ']');
diff --git a/algorithm/sorting/bubble/basic/data.js b/algorithm/sorting/bubble/basic/data.js
@@ -0,0 +1,3 @@
+var tracer = new Array1DTracer();
+var D = tracer.createRandomData(15);
+tracer.setData(D);
diff --git a/algorithm/sorting/bubble/config.json b/algorithm/sorting/bubble/config.json
@@ -0,0 +1,14 @@
+{
+  "def": "Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.",
+  "apps": [],
+  "cpx": {
+    "time": "worst O(n<sup>2</sup>), best O(n), average O(n<sup>2</sup>)",
+    "space": "worst O(1) auxiliary"
+  },
+  "refs": [
+    "https://en.wikipedia.org/wiki/Bubble_sort"
+  ],
+  "files": {
+    "basic": "Basic"
+  }
+}
diff --git a/algorithm/sorting/insertion/config.json b/algorithm/sorting/insertion/config.json
@@ -2,8 +2,8 @@
   "def": "Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.",
   "apps": [],
   "cpx": {
-    "time": "O(n<sup>2</sup>)",
-    "space": "O(n)"
+    "time": "worst O(n<sup>2</sup>), best O(n), average O(n<sup>2</sup>)",
+    "space": "worst O(1) auxiliary"
   },
   "refs": [
     "https://en.wikipedia.org/wiki/Insertion_sort"
diff --git a/algorithm/sorting/quick/basic/code.js b/algorithm/sorting/quick/basic/code.js
@@ -0,0 +1,32 @@
+tracer._print('original array = [' + D.join(', ') + ']');
+tracer._sleep(1000);
+tracer._pace(500);
+function quicksort(low, high) {
+    if (low < high) {
+        var p = partition(low, high);
+        quicksort(low, p - 1);
+        quicksort(p + 1, high);
+    }
+}
+function partition(low, high) {
+    var pivot = D[high];
+    tracer._selectSet([low, high]);
+    var i = low;
+    for (var j = low; j < high; j++) {
+        if (D[j] <= pivot) {
+            var temp = D[i];
+            D[i] = D[j];
+            D[j] = temp;
+            tracer._notify(i, j);
+            i++;
+        }
+    }
+    var temp = D[i];
+    D[i] = D[high];
+    D[high] = temp;
+    tracer._notify(i, high);
+    tracer._deselectSet([low, high]);
+    return i;
+}
+quicksort(0, D.length - 1);
+tracer._print('sorted array = [' + D.join(', ') + ']');
diff --git a/algorithm/sorting/quick/basic/data.js b/algorithm/sorting/quick/basic/data.js
@@ -0,0 +1,3 @@
+var tracer = new Array1DTracer();
+var D = tracer.createRandomData(15);
+tracer.setData(D);
diff --git a/algorithm/sorting/quick/config.json b/algorithm/sorting/quick/config.json
@@ -0,0 +1,14 @@
+{
+  "def": "Quicksort (sometimes called partition-exchange sort) is an efficient sorting algorithm, serving as a systematic method for placing the elements of an array in order. Developed by Tony Hoare in 1959, with his work published in 1961, it is still a commonly used algorithm for sorting. When implemented well, it can be about two or three times faster than its main competitors, merge sort and heapsort.",
+  "apps": [],
+  "cpx": {
+    "time": "worst O(n<sup>2</sup>), best O(n log n), average O(n log n)",
+    "space": "worst O(n) auxiliary"
+  },
+  "refs": [
+    "https://en.wikipedia.org/wiki/Quicksort"
+  ],
+  "files": {
+    "basic": "Basic"
+  }
+}
diff --git a/algorithm/sorting/selection/config.json b/algorithm/sorting/selection/config.json
@@ -2,8 +2,8 @@
   "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)"
+    "time": "worst O(n<sup>2</sup>), best O(n<sup>2</sup>), average O(n<sup>2</sup>)",
+    "space": "O(1) auxiliary"
   },
   "refs": [
     "https://en.wikipedia.org/wiki/Selection_sort"

Original file line number	Diff line number	Diff line change
`@@ -12,7 +12,7 @@`
`12`	`12`	`"insertion": "Insertion Sort",`
`13`	`13`	`"selection": "Selection Sort",`
`14`	`14`	`"bubble": "Bubble Sort",`
`15`		`- "quick": "Quick Sort"`
	`15`	`+ "quick": "Quicksort"`
`16`	`16`	`}`
`17`	`17`	`}`
`18`	`18`	`}`
Original file line number	Diff line number	Diff line change
`@@ -12,5 +12,4 @@ function BFS(s) { // s = start node`
`12`	`12`	`}`
`13`	`13`	`}`
`14`	`14`	`}`
`15`		`-`
`16`	`15`	`BFS(0);`
Original file line number	Diff line number	Diff line change
`@@ -22,7 +22,6 @@ function BFS() {`
`22`	`22`	`}`
`23`	`23`	`return W[e];`
`24`	`24`	`}`
`25`		`-`
`26`	`25`	`var s = Math.random() * G.length \| 0; // s = start node`
`27`	`26`	`var e; // e = start node`
`28`	`27`	`do {`
Original file line number	Diff line number	Diff line change
`@@ -11,7 +11,6 @@ function DFS(node, parent) { // node = current node, parent = previous node`
`11`	`11`	`D[node] = false; // label current node as undiscovered`
`12`	`12`	`tracer._leave(node, parent);`
`13`	`13`	`}`
`14`		`-`
`15`	`14`	`var D; // D[i] indicates whether the i-th node is discovered or not`
`16`	`15`	`for (var i = 0; i < G.length; i++) { // start from every node`
`17`	`16`	`tracer._print('start from ' + i);`
Original file line number	Diff line number	Diff line change
`@@ -6,5 +6,4 @@ function DFS(node, parent) { // node = current node, parent = previous node`
`6`	`6`	`}`
`7`	`7`	`}`
`8`	`8`	`}`
`9`		`-`
`10`	`9`	`DFS(0);`
Original file line number	Diff line number	Diff line change
`@@ -20,7 +20,6 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n`
`20`	`20`	`D[node] = false; // label current node as undiscovered`
`21`	`21`	`tracer._leave(node, parent, 0);`
`22`	`22`	`}`
`23`		`-`
`24`	`23`	`var s = Math.random() * G.length \| 0; // s = start node`
`25`	`24`	`var e; // e = end node`
`26`	`25`	`do {`