-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsort.js
More file actions
115 lines (105 loc) · 2.39 KB
/
sort.js
File metadata and controls
115 lines (105 loc) · 2.39 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
const arr = [14, 38, 5, 44, 3];
function bubbleSort(arr) {
for (let i = 0; i < arr.length; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
console.log(arr);
return arr;
}
function selectSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i;
for (let j = i + 1; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
function insertSort(arr) {
for (let i = 1; i < arr.length; i++) {
for (let j = i; j >= 0; j--) {
if (arr[j - 1] > arr[j]) {
[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
}
}
}
console.log(arr);
return arr;
}
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
const left = [];
const right = [];
const mid = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] <= mid) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left).concat(mid, quickSort(right));
}
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
function merge(left, right) {
const result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left.slice(), right.slice());
}
}
function heapSort(arr) {
let len = arr.length;
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, i, len);
}
for (let i = len - 1; i > 0; i--) {
[arr[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, 0, i);
}
return arr;
}
function heapify(arr, i, len) {
let left = 2 * i + 1;
let right = 2 * i + 2;
let max = i;
if (left < len && arr[left] > arr[max]) {
max = left;
}
if (right < len && arr[right] > arr[max]) {
max = right;
}
if (max !== i) {
[arr[i], arr[max]] = [arr[max], arr[i]];
heapify(arr, max, len);
}
}
// bubbleSort(arr);
// selectSort(arr);
// insertSort(arr);
// console.log(quickSort(arr));
// console.log(mergeSort(arr));
console.log(heapSort(arr));