퀵 정렬(Quicksort)은 리스트를 두 부분으로 나누는 분할 정복(Divide and Conquer) 방식의 대표적인 정렬 알고리즘입니다. 먼저 분할(Partition) 과정을 통해 피벗(pivot) 요소를 하나 선택하고, 피벗을 기준으로 왼쪽에는 피벗보다 작은 값들을, 오른쪽에는 피벗보다 큰 값들을 배치합니다. 분할이 완료되면 각각 나뉜 부분 리스트에 대해 동일한 절차를 재귀적으로 반복하여 전체 배열을 정렬합니다.
퀵 정렬의 시간 및 공간 복잡도
- 시간 복잡도: 최선의 경우와 평균의 경우 O(n log n), 최악의 경우 O(n²)
- 공간 복잡도: O(log n)
입력 및 출력 예시
입력:
정렬되지 않은 리스트: 90 45 22 11 22 50
출력:
정렬 전 배열: 90 45 22 11 22 50
정렬 후 배열: 11 22 22 45 50 90
알고리즘
partition(array, lower, upper)
입력: 데이터 배열, 하위 경계(lower), 상위 경계(upper)
출력: 올바른 위치에 놓인 피벗
Begin
pivot := array[lower]
start := lower, end := upper
while start < end do
while array[start] <= pivot AND start < end do
start := start + 1
done
while array[end] > pivot do
end := end – 1
done
if start < end then
swap array[start] with array[end]
done
array[lower] := array[end]
array[end] := pivot
return end
End
quickSort(array, left, right)
입력: 데이터 배열과 배열의 하위·상위 경계
출력: 정렬된 배열
Begin
if lower < right then
q = partition(array, left, right)
quickSort(array, left, q-1)
quickSort(array, q+1, right)
End
C++ 구현 예제
#include<iostream>
using namespace std;
void swapping(int &a, int &b) { // a와 b의 값을 교환
int temp;
temp = a;
a = b;
b = temp;
}
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
int partition(int *array, int lower, int upper) {
// Hoare 분할 기법으로 피벗의 올바른 위치를 찾음
int pivot, start, end;
pivot = array[lower]; // 첫 번째 요소를 피벗으로 지정
start = lower; end = upper;
while(start < end) {
while(array[start] <= pivot && start<end) {
start++; // start 포인터를 오른쪽으로 이동
}
while(array[end] > pivot) {
end--; // end 포인터를 왼쪽으로 이동
}
if(start < end) {
swap(array[start], array[end]); // 작은 값과 큰 값을 교환
}
}
array[lower] = array[end];
array[end] = pivot;
return end;
}
void quickSort(int *array, int left, int right) {
int q;
if(left < right) {
q = partition(array, left, right);
quickSort(array, left, q-1); // 왼쪽 부분 배열 정렬
quickSort(array, q+1, right); // 오른쪽 부분 배열 정렬
}
}
int main() {
int n;
cout << "요소 개수 입력: ";
cin >> n;
int arr[n]; // 입력받은 개수만큼 배열 생성
cout << "요소 입력:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "정렬 전 배열: ";
display(arr, n);
quickSort(arr, 0, n-1); // 마지막 인덱스는 (n-1)
cout << "정렬 후 배열: ";
display(arr, n);
}
실행 결과
요소 개수 입력: 6
요소 입력:
90 45 22 11 22 50
정렬 전 배열: 90 45 22 11 22 50
정렬 후 배열: 11 22 22 45 50 90
퀵 정렬은 평균적으로 매우 빠른 성능을 보여 실무에서 널리 사용됩니다. 다만 이미 정렬된 배열이나 역순 배열처럼 피벗 선택이 극단적으로 불균형해지는 경우 최악의 성능인 O(n²)까지 떨어질 수 있으므로, 무작위 피벗 선택이나 중간값(median-of-three) 기법 등을 함께 활용하면 안정적인 성능을 얻을 수 있습니다.