[알고리즘] 퀵정렬(QuickSort)
가장 빨라서 이름이 Quick 정렬(정확히 말하자면 가장 빠른놈은 아니지만 빠른 편에 속하는 놈임)
하나의 리스트를 pivot을 기준으로 두 개의 부분리스트로 나누어
하나는 피벗보다 작은 값들의 부분리스트,
다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음,
각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법임.
한번의 퀵정렬에서는 이렇게 pivot 의 자리만 찾고
나머지 데이터들은 pivot보다 작은값, pivot보다 큰값 으로 나눠두기만 한다.
그 다음 이분할된 부분에서 각각 pivot을 찾아서 해당 pivot 자리만 찾아주고 이렇게 재귀로 나가는 것이다.
[ 퀵정렬 핵심 ]
1. 퀵정렬도 일종의 Divide and Conquer 분할정복 문제이다.
2. 퀵정렬은 "기준값(pivot)"이란 새로운 도구를 사용한다.
3. 퀵정렬은 한번의 퀵정렬에서 모든 데이터의 자리를 찾아주는 것이 아닌, 딱 1개의 데이터(pivot)의 위치만 찾아준다
[ MergeSort vs QuickSort ]
MergeSort와 QuickSort 모두 기본적으로 '분할 정복' 알고리즘을 기반으로 정렬되는 방식이다.
Merge Sort는 하나의 리스트를 무조건 '절반'으로 나누어 분할 정복을 하고,
Quick Sort의 경우 피벗(pivot)의 값에 따라
피벗보다 작은 값을 갖는 부분리스트와
피벗보다 큰 값을 갖는 부분리스트의 크기가 다를 수 있기 때문에
하나의 리스트에 대해 비균등하게 나뉜다는 점이 있다.
[ QuickSort의 이해 ]
퀵정렬은 여태껏배운 O(N*logN) 정렬들(HeapSort / MergeSort) 과 다르다.
바로 해당 범위 내에 " 기준값(pivot) " 을 통해 정렬을 진행한다는 점이다.
기준값을 토대로 각 데이터들의 대소관계를 파악하고 이를 통해 정렬을 한다.
퀵정렬에 사용되는 도구는 세 가지가 있다
1. 기준대상인 pivot
2. 왼쪽에서 오른쪽으로 움직이는 low
3. 오른쪽에서 왼쪽으로 움직이는 high
여기서 low와 high는 서로 관계가 없다.
둘 다 독립적으로 움직이는 존재들이고 우리가 신경써야할 것은 해당값이 pivot(기준값) 보다 크냐 작냐 뿐이다!
pivot을 기준으로 왼쪽에는 작은값들 오른쪽에는 큰값들로 정렬해주기만 하면 되기 때문이다.
(맨 위 그림 참고. 퀵정렬은 모든 관심은 pivot한테 가있다)
따라서 low와 high의 무빙은 다음과 같아야한다.
1. arr[low] 값이 pivot보다 크면 멈춘다
2. arr[high] 값이 pivot보다 작으면 멈춘다
3. 그 두 값을 Swap해준다
여기서 짚고 넘어가야할게 지금 말한 이 과정은 한 개의 cycle 에 대한 과정이다.
즉 위 과정은 모든 원소를 정렬하는게 아닌,
하나의 Pivot의 위치를 찾아주고 나머지는 아직 위치가 제자리가 아닌 상황이다.
따라서 종료조건은 바로 low와 high가 교차하여 지나갈때이다!
둘이 교차했다는 것은 그 이전에 Swap해야할 것들은 다 Swap했다는 것이고
이는 pivot보다 작은값 과 큰값이 다 나눠졌다는 뜻이기 때문이다!!
왜냐하면 교차될때까지 한 일이
low는 pivot보다 크면 멈추고
high는 pivot보다 작으면 멈춰서
두 값을 교체해준 일이 였기 때문이다.
따라서 low와 high가 교차, 즉 만날때는
당연히 왼쪽은 작은놈, 오른쪽은 큰놈들
둘로 나눠져 있을 수 밖에 없다!
따라서 이게 종료조건이 된다.
그러므로 pivot과 high만 교체해주면 된다.
이렇게되면 한번의 퀵정렬이 실행된 것이고
여기서 재귀적으로 퀵정렬을 호출시켜주면 된다.
[QuickSort.c]
QuickSort의 재귀과정도 MergeSort의 재귀과정과 동일하다.
맨 왼쪽꺼부터 파고 오른쪽으로 천천히 올라오는 재귀호출을 보인다.
그러니까 오른쪽 왼쪽이 동시에 재귀가 진행되는게 절대 아니란 얘기다!
#pragma warning(disable:4996)
#include <stdio.h>
#include <stdlib.h>
int findPivot(int left, int right) {
return rand() % (right - left + 1) + left;
}
void swap(int arr[], int idx1, int idx2) {
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}
int Partition(int arr[], int left, int right) {
int pivot = findPivot(left, right);
while (left < right) {
// L은 pivot 만나면 무조건 정지
while (arr[left] < arr[pivot] && left < right) left++;
while (arr[right] >= arr[pivot] && left < right) right--;
swap(arr, left, right);
if (left == pivot) pivot = right;
else if (right == pivot) pivot = left;
}
// left와 right가 만난 상황이니
// left right 둘 중 아무나 pivot과 바꿔준 후
// 한 턴의 정렬을 종료한다
int temp = arr[pivot];
arr[pivot] = arr[left];
arr[left] = temp;
return left;
}
void printArr(int arr[], int N) {
for (int i = 0; i < N; i++) {
printf(" %d", arr[i]);
}
return;
}
void QuickSort(int arr[], int left, int right) {
// 원소가 한 개 이상이면
if (left < right) {
int pivot = Partition(arr, left, right);
QuickSort(arr, left, pivot - 1);
QuickSort(arr, pivot+1, right);
}
}
int main() {
int N;
scanf("%d", &N);
int* arr = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
}
QuickSort(arr, 0, N - 1);
for (int i = 0; i < N; i++) {
printf(" %d", arr[i]);
}
free(arr);
return 0;
}
while (low <= high) {
// code
if(low<=high) Swap(arr, low, high);
}
여기서 이렇게 while문 안에 동일한 조건의 if문이 있는 이유는
low와 high가 교차되는 경우를 걸러내기 위해서 이다.