- 문제
정수를 요소로 갖는 배열을 입력받아 오름차순으로 정렬하여 리턴해야 합니다.
Quick Sort (퀵 정렬)
불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음,
두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.
- 퀵 정렬은 다음의 단계들로 이루어진다.
분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.
결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
입출력 예시
let output = quickSort([3, 1, 21]);
console.log(output); // --> [1, 3, 21]- 풀이
function quickSort(array, transform = (item) => item) {
if (array.length < 2) return array;
const pivot = array[0];
let left = 1;
let right = array.length - 1;
while (left <= right) {
// 기준 수보다 왼쪽 요소의 수가 크고, 오른쪽 요소의 수가 작으면 두 수를 swap한다.
if (transform(array[left]) > transform(pivot) && transform(array[right]) < transform(pivot)) {
[array[left], array[right]] = [array[right], array[left]];
left++;
right--;
}
// 기준 수 보다 왼쪽 요소의 수가 작으면, left 인덱스만 하나 증가한다.
if (transform(array[left]) <= transform(pivot)) {
left++;
}
// 기준 수 보다 오른쪽 요소의 수가 크면, right 인덱스만 하나 증가한다.
if (transform(array[right]) >= transform(pivot)) {
right--;
}
}
// 기준 수는 자신 보다 작은 수 바로 오른쪽에 위치할 수 있도로고 swap하여 구분한다.
[array[0], array[left - 1]] = [array[left - 1], array[0]]
const leftArr = array.splice(0, left - 1);
const mid = array.splice(0, 1);
const rightArr = array;
return [
...quickSort(leftArr),
...mid,
...quickSort(rightArr)
]
}
sort에 여러가지 공부해야 할 알고리즘이 많이 있는 것 같다.bubbleSort,insertSort등이 기억나지만 온전히 나의 것으로 만들지 못했다.sort종류를 따로 블로깅하는 것도 좋겠다.
Log