quick 정렬을 구현해 봅시다.

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
let arr = [100,83,12,55,24,18,71,56,43,21,59,89,21,44];
function quickSort(arr) {
if (arr.length < 2) return arr;
let pivotIndex = arr.length - 1;
let pivot = arr[pivotIndex];
let divIndex = pivotIndex - 1;
firstLoop: for (var i = 0; i <= divIndex; i++) {
if (arr[i] > pivot) {
for (let j = divIndex; j >= i; j--) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
divIndex = j;
break;
}
if(i === j){
[arr[pivotIndex], arr[i]] = [arr[i], arr[pivotIndex]];
break firstLoop;
}
}
}
}
return [].concat(quickSort(arr.slice(0,i)), pivot, quickSort(arr.slice(i+1)));
}
console.log(quickSort(arr)); // [12, 18, 21, 21, 24, 43, 44, 55, 56, 59, 71, 83, 89, 100]