pivot(중심축) 을 정하고, 중심축 보다 작은 값들은 왼쪽으로 큰 값들은 오른쪽으로 보내는 것이다.
이렇게 pivot을 정해서 왼쪽 오른쪽으로 나누고 다시금 왼쪽 오른쪽에 대해 재귀적으로 pivot을 정해서 왼쪽 오른쪽을 나누고,, 이 과정을 반복하면 결국 정렬이 완성 된다.
1. 먼저, 배열의 길이가 1과 같거나 작게 될 경우 배열을 바로 리턴한다.
2. 리스트 가운데 하나의 원소를 고르고 pivot 이라고 한다. : 첫번째 인덱스를 pivot으로 정했다.
3. 배열 안에서 pivot을 제외한 모든 요소를 탐색해서 pivot보다 작으면 left, 크면 right라는 배열에 넣는다.
-> let left = []; let right = [];
-> 이 과정은 인덱스가 arr.length만큼 반복한다
4. left와 right에 값이 모두 넣어졌으면 각각의 배열에 대해 quickSort를 재귀하도록 해서 다시 정렬한다.
5. left, pivot, right를 합쳐서 리턴한다.
const quickSort = function (arr) {
if (arr.length <= 1) return arr;
const pivot = arr[0];
const left = [];
const right = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] <= pivot) left.push(arr[i]);
else right.push(arr[i]);
}
const lSorted = quickSort(left);
const rSorted = quickSort(right);
return [...lSorted, pivot, ...rSorted];
};
퀵 정렬에 대해서 구글링해보니 병합정렬(merge sort)와 많이 비교하는 것 같았다.
<퀵 정렬, 병합 정렬 공통점>
<퀵 정렬, 병합 정렬 차이점>
잘 봤습니다!, 근데 let left = []; let right = []; 를 사용하시면 in-place sort 가 안 되지 않나요?