퀵 정렬(Quicksort)은 리스트를 두 부분으로 분할하는 방식으로 동작하는 정렬 알고리즘입니다. 먼저 분할(Partition) 과정을 통해 피벗(Pivot) 요소를 하나 선택하고, 피벗보다 작은 값들은 왼쪽 부분에, 큰 값들은 오른쪽 부분에 배치합니다. 이후 분할된 각각의 리스트에 대해 동일한 절차를 재귀적으로 반복하여 전체를 정렬합니다.
이번 글에서는 약 100개의 요소를 가진 큰 배열을 정렬하는 예제를 다룹니다. 숫자들을 무작위 순서로 섞어(unshuffle) 정렬되지 않은 상태를 만든 뒤, 퀵 정렬 기법을 적용해 정렬하는 과정을 살펴보겠습니다.
퀵 정렬의 시간 복잡도
시간 복잡도 − 최선의 경우와 평균의 경우 O(n log n), 최악의 경우 O(n2)
공간 복잡도 − O(log n)
입력 − 정렬되지 않은 리스트: 90 45 22 11 22 50
출력 − 정렬 후 배열: 11 22 22 45 50 90
알고리즘
partition(array, lower, upper)
입력 − 데이터 배열, 하위 경계(lower boundary), 상위 경계(upper boundary)
출력 − 올바른 위치에 배치된 피벗
Begin pivot := array[upper] i := lower – 1 for j in range lower to higher, do if array[j] < pivot, then exchange the values of array[i] and array[j] i := i + 1 done exchange the values of array[upper] and array[i + 1] return i + 1 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
예제 코드
#include<iostream>
#include<cstdlib>
#include<ctime>
#define MAX 100
using namespace std;
void random_shuffle(int arr[]) { //배열 요소를 무작위 위치로 섞는 함수
srand(time(NULL));
for (int i = MAX - 1; i > 0; i--) {
int j = rand()%(i + 1);
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int partion(int arr[], int p, int r) {
int pivot = arr[r]; //마지막 요소를 피벗으로 지정
int i = p - 1;
for (int j = p; j < r; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i+1], arr[r]);
return i + 1;
}
void quick_sort(int arr[], int p, int q) { //리스트를 재귀적으로 정렬
int j;
if (p < q) {
j = partion(arr, p, q);
quick_sort(arr, p, j - 1);
quick_sort(arr, j + 1, q);
}
}
int main() {
int i;
int arr[MAX];
for (i = 0;i < MAX;i++)
arr[i] = i + 1;
random_shuffle(arr); //배열을 무작위로 섞기
quick_sort(arr, 0, MAX-1); //배열의 요소들을 정렬
for (i = 0; i < MAX;i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}실행 결과
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100