-
Notifications
You must be signed in to change notification settings - Fork 0
/
script.js
78 lines (58 loc) · 2.12 KB
/
script.js
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
let count;
function quickSort(arr, pivotRuleTask) {
// Stop recusrion, because if array items less than 2 it is sorted
if (arr.length < 2) return arr;
count = count + arr.length - 1;
let pivotIndex = 0; // For the pivotRuleTask #1: always using first element of the array as the pivot element.
// For the pivotRuleTask #2: always using the final element of the given array as the pivot element
if (pivotRuleTask === 2) {
pivotIndex = arr.length - 1;
}
// For the pivotRuleTask #3: always using using the "median-of-three" pivot rule
if (pivotRuleTask === 3) {
let firstEl = arr[0];
let middleEl = arr[Math.floor((arr.length - 1) / 2)];
let lastEl = arr[arr.length - 1];
pivotElement = [firstEl, middleEl, lastEl].sort((a, b) => a - b)[1];
pivotIndex = arr.findIndex((el) => el === pivotElement);
}
// Swap pivot element to the start of array
[arr[0], arr[pivotIndex]] = [arr[pivotIndex], arr[0]];
let i = 0;
for (j = 1; j < arr.length; j++) {
if (arr[j] < arr[0]) {
i++;
[arr[j], arr[i]] = [arr[i], arr[j]];
}
}
// Swap first element(pivot) to its final position
[arr[i], arr[0]] = [arr[0], arr[i]];
// Divide arrays for 2 parts < and > pivot
let leftSide = arr.splice(0, i);
let rightSide = arr.splice(1);
// Recursion
return [...quickSort(leftSide, pivotRuleTask), ...arr, ...quickSort(rightSide, pivotRuleTask)];
}
const fs = require('fs');
const readline = require('readline');
async function processLineByLine(file) {
const fileStream = fs.createReadStream(file);
const rl = readline.createInterface({
input: fileStream,
crlfDelay: Infinity
});
const arr = [];
for await (const line of rl) {
arr.push(parseInt(line));
}
count = 0;
quickSort([...arr], 1);
console.log('task1:', count); // 162085
count = 0;
quickSort([...arr], 2);
console.log('task2:', count); // 164123
count = 0;
quickSort([...arr], 3);
console.log('task3:', count); // 138382
}
processLineByLine('QuickSort.txt');