-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick_sort.js
More file actions
47 lines (28 loc) · 1.04 KB
/
quick_sort.js
File metadata and controls
47 lines (28 loc) · 1.04 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
/*
Sort list of numbers in O(log n) using Recursion
3 main steps:
1) Choose the pivot (reference value).
2) Divide the rest of the array in two, placing everything smaller than the pivot on the
left and greater than the pivot on the right.
3) Recursively apply the previous steps to the sub-arrays if they have more than 1 element.
*/
function quickSort(list) {
if ( list.length < 2) return list;
let pivot = list[0];
let left = [];
let right = [];
for ( let i=1; i < list.length; i++ ){
switch ( true ){
case ( list[i] < pivot ):
left.push( list[i] );
break;
case ( list[i] >= pivot ):
if( list[i] )
right.push( list[i] );
break;
}
}
return [].concat( quickSort( left ), pivot, quickSort( right ));
};
const range = n => Array.from({length: n}, (value, key) => key)
quickSort(range(1000));