알고 있으면 매우 유용한 알고리즘인 퀵 정렬에 대해 소개합니다 :D
퀵 정렬(quick sort) 알고리즘의 개념 요약
- ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘입니다.
- 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다.
- 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법입니다.
- 합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할합니다.
분할 정복(divide and conquer) 방법
- 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다.
- 분할 정복 방법은 대개 순환 호출을 이용하여 구현합니다.
과정 설명
- 리스트 안에 있는 한 요소를 선택하며, 고른 원소를 피벗(pivot) 이라고 합니다.
- 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨집니다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬합니다.
- 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복합니다.
- 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복합니다.
- 부분 리스트들이 더 이상 분할이 불가능할 때 즉, 리스트의 크기가 0이나 1이 될 때까지 반복합니다.
퀵 정렬(quick sort) 알고리즘의 구체적인 개념
하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법입니다.
퀵 정렬은 다음의 단계들로 이루어집니다.
- 분할(Divide): 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할합니다.
- 정복(Conquer): 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용합니다.
- 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병합니다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다.
JavaScript로 구현한 퀵 정렬
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = require("fs").readFileSync(filePath).toString().split("\n");
// 퀵 선택 알고리즘을 채택해서 사용
function solution(input) {
const k = input[0].split(" ");
const arr = input[1].split(" ");
const result = quick(arr.map((item) => Number(item)));
return result[k[1] - 1];
}
function quick(arr, left = 0, right = arr.length - 1) {
const mid = parseInt((left + right) / 2);
const pivot = arr[mid];
const newLeft = divide(arr, left, right, pivot);
if (left >= right) {
return;
}
quick(arr, newLeft, right);
quick(arr, left, newLeft - 1);
return arr;
}
function divide(arr, left, right, pivot) {
while (left <= right) {
while (arr[left] < pivot) {
left++;
}
while (pivot < arr[right]) {
right--;
}
if (left <= right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
left++;
right--;
}
}
return left;
}
console.log(solution(input));
// 처음 풀이한 코드
function solution(input) {
const k = input[0].split(" ");
const result = quickSort(arr[1].split(" "));
return result[k[1] - 1];
}
function quickSort(arr) {
console.log("arr", arr);
if (!arr.length) {
return [];
}
const pivot = arr[0];
const min = [];
const max = [];
for (let i = 0; i < arr.length; i++) {
if (arr[i] < pivot) {
min.push(arr[i]);
} else if (arr[i] > pivot) {
max.push(arr[i]);
}
}
const minSorted = quickSort(min);
const maxSorted = quickSort(max);
return [...minSorted, pivot, ...maxSorted];
}
console.log(solution(input));
퀵 정렬의 장, 단점
장점
- 속도가 빠릅니다. 실제로 다른 정렬과 비교했을 때 속도가 가장 빠른 모습을 보여줍니다.(아래 표 참고)
단점
- 정렬된 배열에 대해서는 퀵 정렬의 불균현 분할에 의해 수행시간이 더 많이 걸립니다.
- 그래서 pivot을 지정할 때 배열을 균등하게 분할할 수 있는 데이터를 선택해야 합니다.(ex: 배열 요소의 중간값)
단순(구현 간단)하지만 비효율적인 방법
- 삽입 정렬
- 선택 정렬
- 버블 정렬
복잡하지만 효율적인 방법
- 퀵 정렬
- 힙 정렬
- 합병 정렬
- 기수 정렬
참고 자료 링크
최근댓글