quickSort
문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
입력
인자 1 : arr
number 타입을 요소로 갖는 배열
arr[i]는 정수
arr.length는 100,000 이하
출력
number 타입을 요소로 갖는 배열을 리턴해야 합니다.
배열의 요소는 오름차순으로 정렬되어야 합니다.
arr[i] <= arr[j] (i < j)
주의사항
퀵 정렬을 구현해야 합니다.
arr.sort 사용은 금지됩니다.
입력으로 주어진 배열은 중첩되지 않은 1차원 배열입니다.
입출력 예시
let output = quickSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]풀이
- 기준이 되는 수 pivot을 정한다.
- pivot보다 낮은 수들은 왼쪽 배열에, 높은 수들은 오른쪽 배열로 나누는 작업을 재귀적으로 수행한다.
function quickSort(arr, transform = (item) => item) {
// arr 길이가 1개 or 0 일때는 arr 그대로 리턴한다.
if (arr.length < 2) return arr;
// 기준이 되는 수를 고른다. arr의 마지막 인덱스 값
// pivot을 제외한 가장 왼쪽과 오른쪽 수를 비교한다.
let pivot = [arr[arr.length - 1]];
let left = [];
let right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (pivot > arr[i]) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort(left, transform).concat(pivot, quickSort(right, transform));
}
// if, arr=[3,1,21,9,10] 일 때...
// 1번째
// pivot = [10]
// left = [3]
// right = []
// 2번째
// pivot = [10]
// left = [3,1]
// right = []
// 3번째
// pivot = [10]
// left = [3,1]
// right = [21]
// 4번째
// pivot = [10]
// left = [3,1,9]
// right = [21,10]
// 첫번째 left, right 그룹 완성
// 재귀 반복...
⭐️
퀵 정렬은 pivot(기준점)을 기준으로 pivot보다 낮은 수들의 배열, pivot보다 큰 수들의 배열로 나눈다. 나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 요소가 하나뿐인 배열이 될 때까지 반복한다.
퀵 정렬은 매우 빠른 속도를 자랑하는 정렬이다.
하지만 배열이 올바르게 정렬되어 있을 경우 엄청나게 느려진다..
- 배열의 두번째 인덱스부터 비교를 시작하여 원소들과 비교하여 삽입할 위치를 정한다.
- 위치가 정해지면 뒤쪽의 원소들을 한칸씩 뒤로 이동시키고 그 자리에 삽입한다.
시간복잡도
평균 시간 복잡도는 O(N * logN)이다.
pivot값이 그룹 내에서 가장 큰값이거나 작은값이면 O(N)이 되지만 최악의 경우(애초에 정렬되어 있을 경우)에는 O(N^2)가 된다.
최악의 시간복잡도를 방지하기 위한 방법
-
랜덤화
배열의 랜덤한 두 개의 index를 뒤바꾸어주는 방식으로 배열이 정렬되어 있지 않도록 만든다. -
랜덤 기준점 선택
기준점을 난수를 발생시켜 선택하는 방법으로, 정렬되었거나, 정렬에 가까운 배열에서 최악을 선택하는 횟수가 적어질 것이다. -
Median Of Three Pivot
기준점을 선택할 때 3개의 원소를 후보로 두고 그 중간 값을 선택하는 방법으로 이렇게 기준점을 선택하면 최악의 경우는 반드시 피할 수 있다.
