Skip to content

Commit 75751ab

Browse files
64json64json
committed
add Quicksort
1 parent 13a7881 commit 75751ab

File tree

17 files changed

+97
-15
lines changed

17 files changed

+97
-15
lines changed

‎algorithm/category.json

+1-1
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@
1212
"insertion": "Insertion Sort",
1313
"selection": "Selection Sort",
1414
"bubble": "Bubble Sort",
15-
"quick": "Quick Sort"
15+
"quick": "Quicksort"
1616
}
1717
}
1818
}

‎algorithm/graph_search/bfs/basic/code.js

-1
Original file line numberDiff line numberDiff line change
@@ -12,5 +12,4 @@ function BFS(s) { // s = start node
1212
}
1313
}
1414
}
15-
1615
BFS(0);

‎algorithm/graph_search/bfs/config.json

+2-2
Original file line numberDiff line numberDiff line change
@@ -10,8 +10,8 @@
1010
"Construction of the failure function of the Aho-Corasick pattern matcher."
1111
],
1212
"cpx": {
13-
"time": "O(|E|)",
14-
"space": "O(|V|)"
13+
"time": "worst O(|E|)",
14+
"space": "worst O(|V|)"
1515
},
1616
"refs": [
1717
"https://en.wikipedia.org/wiki/Breadth-first_search"

‎algorithm/graph_search/bfs/shortest_path/code.js

-1
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,6 @@ function BFS() {
2222
}
2323
return W[e];
2424
}
25-
2625
var s = Math.random() * G.length | 0; // s = start node
2726
var e; // e = start node
2827
do {

‎algorithm/graph_search/dfs/all_paths/code.js

-1
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,6 @@ function DFS(node, parent) { // node = current node, parent = previous node
1111
D[node] = false; // label current node as undiscovered
1212
tracer._leave(node, parent);
1313
}
14-
1514
var D; // D[i] indicates whether the i-th node is discovered or not
1615
for (var i = 0; i < G.length; i++) { // start from every node
1716
tracer._print('start from ' + i);

‎algorithm/graph_search/dfs/basic/code.js

-1
Original file line numberDiff line numberDiff line change
@@ -6,5 +6,4 @@ function DFS(node, parent) { // node = current node, parent = previous node
66
}
77
}
88
}
9-
109
DFS(0);

‎algorithm/graph_search/dfs/config.json

+2-2
Original file line numberDiff line numberDiff line change
@@ -14,8 +14,8 @@
1414
"Finding biconnectivity in graphs."
1515
],
1616
"cpx": {
17-
"time": "O(|E|)",
18-
"space": "O(|V|)"
17+
"time": "worst O(|E|)",
18+
"space": "worst O(|V|)"
1919
},
2020
"refs": [
2121
"https://en.wikipedia.org/wiki/Depth-first_search"

‎algorithm/graph_search/dfs/shortest_path/code.js

-1
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,6 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
2020
D[node] = false; // label current node as undiscovered
2121
tracer._leave(node, parent, 0);
2222
}
23-
2423
var s = Math.random() * G.length | 0; // s = start node
2524
var e; // e = end node
2625
do {

‎algorithm/graph_search/dfs/weighted_graph/code.js

-1
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,6 @@ function DFS(node, parent, weight) { // node = current node, parent = previous n
1111
D[node] = false; // label current node as undiscovered
1212
tracer._leave(node, parent, 0);
1313
}
14-
1514
var D; // D[i] indicates whether the i-th node is discovered or not
1615
tracer._pace(1000);
1716
for (var i = 0; i < G.length; i++) { // start from every node

‎algorithm/sorting/bubble/basic/code.js

+22
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
tracer._print('original array = [' + D.join(', ') + ']');
2+
tracer._sleep(1000);
3+
tracer._pace(300);
4+
var N = D.length;
5+
var swapped;
6+
do {
7+
swapped = false;
8+
tracer._select(N - 1);
9+
for (var i = 1; i < N; i++) {
10+
if (D[i - 1] > D[i]) {
11+
tracer._print('swap ' + D[i - 1] + ' and ' + D[i]);
12+
var temp = D[i - 1];
13+
D[i - 1] = D[i];
14+
D[i] = temp;
15+
swapped = true;
16+
tracer._notify(i - 1, i);
17+
}
18+
}
19+
tracer._deselect(N - 1);
20+
N--;
21+
} while (swapped);
22+
tracer._print('sorted array = [' + D.join(', ') + ']');

‎algorithm/sorting/bubble/basic/data.js

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

‎algorithm/sorting/bubble/config.json

+14
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
{
2+
"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.",
3+
"apps": [],
4+
"cpx": {
5+
"time": "worst O(n<sup>2</sup>), best O(n), average O(n<sup>2</sup>)",
6+
"space": "worst O(1) auxiliary"
7+
},
8+
"refs": [
9+
"https://en.wikipedia.org/wiki/Bubble_sort"
10+
],
11+
"files": {
12+
"basic": "Basic"
13+
}
14+
}

‎algorithm/sorting/insertion/config.json

+2-2
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,8 @@
22
"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.",
33
"apps": [],
44
"cpx": {
5-
"time": "O(n<sup>2</sup>)",
6-
"space": "O(n)"
5+
"time": "worst O(n<sup>2</sup>), best O(n), average O(n<sup>2</sup>)",
6+
"space": "worst O(1) auxiliary"
77
},
88
"refs": [
99
"https://en.wikipedia.org/wiki/Insertion_sort"

‎algorithm/sorting/quick/basic/code.js

+32
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
tracer._print('original array = [' + D.join(', ') + ']');
2+
tracer._sleep(1000);
3+
tracer._pace(500);
4+
function quicksort(low, high) {
5+
if (low < high) {
6+
var p = partition(low, high);
7+
quicksort(low, p - 1);
8+
quicksort(p + 1, high);
9+
}
10+
}
11+
function partition(low, high) {
12+
var pivot = D[high];
13+
tracer._selectSet([low, high]);
14+
var i = low;
15+
for (var j = low; j < high; j++) {
16+
if (D[j] <= pivot) {
17+
var temp = D[i];
18+
D[i] = D[j];
19+
D[j] = temp;
20+
tracer._notify(i, j);
21+
i++;
22+
}
23+
}
24+
var temp = D[i];
25+
D[i] = D[high];
26+
D[high] = temp;
27+
tracer._notify(i, high);
28+
tracer._deselectSet([low, high]);
29+
return i;
30+
}
31+
quicksort(0, D.length - 1);
32+
tracer._print('sorted array = [' + D.join(', ') + ']');

‎algorithm/sorting/quick/basic/data.js

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

‎algorithm/sorting/quick/config.json

+14
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
{
2+
"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.",
3+
"apps": [],
4+
"cpx": {
5+
"time": "worst O(n<sup>2</sup>), best O(n log n), average O(n log n)",
6+
"space": "worst O(n) auxiliary"
7+
},
8+
"refs": [
9+
"https://en.wikipedia.org/wiki/Quicksort"
10+
],
11+
"files": {
12+
"basic": "Basic"
13+
}
14+
}

‎algorithm/sorting/selection/config.json

+2-2
Original file line numberDiff line numberDiff line change
@@ -2,8 +2,8 @@
22
"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.",
33
"apps": [],
44
"cpx": {
5-
"time": "O(n<sup>2</sup>)",
6-
"space": "O(n)"
5+
"time": "worst O(n<sup>2</sup>), best O(n<sup>2</sup>), average O(n<sup>2</sup>)",
6+
"space": "O(1) auxiliary"
77
},
88
"refs": [
99
"https://en.wikipedia.org/wiki/Selection_sort"

0 commit comments

Comments
 (0)