퀵 정렬이란?
퀵 정렬은 분할 정복 기법을 활용하여 주어진 배열을 효율적으로 정렬하는 알고리즘이다. 배열을 작은 부분으로 나누어 정렬하면서 전체 배열을 정렬해 나가는 방식으로 작동 평균적으로 빠른 속도로 정렬이 이루어지며, 많은 프로그래밍 언어의 내장 정렬 함수에도 활용되는 알고리즘이다.
시간 복잡도
- 평균적인 시간 복잡도는 O(n log n)
- 최악의 경우 O(n2)
기본 동작 원리
- 기준 선택: 배열에서 기준(pivot)으로 사용할 숫자를 선택해서 가장 오른쪽으로 보냅니다.
- 분할과 정렬: 기준에서 왼쪽에는 작은 수, 오른쪽에는 큰 수가 오도록 배열을 정렬합니다.
- 비교와 교환: 기준을 제외한 왼쪽과 오른쪽의 수를 비교하면서 작은 수는 오른쪽으로 큰 수는 왼쪽으로 이동시킵니다. 만약 왼쪽 수가 기준보다 크고, 오른쪽 수가 기준보다 작다면 서로 위치를 바꿉니다.
- 분할 재귀: 왼쪽과 오른쪽 수가 만날 때까지 위 과정을 반복합니다. 만난 수와 기준을 바꾸어 기준의 위치를 확정하고, 왼쪽과 오른쪽 부분 배열을 재귀적으로 퀵 정렬합니다.
코드
function quickSort(arr) {
if (arr.length <= 1) return arr; // 배열의 길이가 1 이하면 이미 정렬된 상태이므로 반환
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]); // 기준보다 크거나 같은 수는 오른쪽 배열에 추가
}
}
return [...quickSort(left), pivot, ...quickSort(right)]; // 왼쪽, 기준, 오른쪽 배열을 재귀적으로 정렬하여 병합
}
const array = [4, 1, 7, 6, 3, 8, 2, 5];
const sortedArray = quickSort(array);
console.log(sortedArray); // [1, 2, 3, 4, 5, 6, 7, 8]