-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquickSortv3.js
More file actions
56 lines (41 loc) · 1.12 KB
/
quickSortv3.js
File metadata and controls
56 lines (41 loc) · 1.12 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
function swap(items, leftIndex, rightIndex) {
var temp = items[leftIndex];
items[leftIndex] = items[rightIndex];
items[rightIndex] = temp;
}
function partitioning(items, left, right) {
var pivot = items[Math.floor((right + left) / 2)]; // middle element
leftPointer = left; // left pointer
rightPointer = right; // right pointer
while (leftPointer <= rightPointer) {
while (items[leftPointer] < pivot) {
leftPointer++;
}
while (items[rightPointer] > pivot) {
rightPointer--;
}
if (leftPointer <= rightPointer) {
swap(items, leftPointer, rightPointer);
leftPointer++;
rightPointer--;
}
}
return leftPointer;
}
function quickSort(items, left, right) {
var index;
if (items.length > 1) {
index = partitioning(items, left, right);
if (left < index - 1) {
quickSort(items, left, index - 1);
}
if (index < right) {
quickSort(items, index, right);
}
}
return items;
}
var items = [4, 6, 8, 2, 9, 3, 5, 7, 1]
// call the quick sort
var sortedArray = quickSort(items, 0, items.length - 1);
console.log('sortedArray', sortedArray)