퀵 정렬 : 이해와 구현
이번 퀵 정렬도 앞서 본 병합 정렬과 마찬가지로
"분할 정복"에 근거하여 만들어진 정렬 방법이다.
실제로 이 또한 정렬대상을 반씩 줄여나가는 과정을 포함한다.
"퀵 자가 들어가는 걸 보면 제법 빠른 정렬인가봐요..? 그럼 그만큼 어렵겠쥬..?"
라는 생각을 할수 있지만
아니다!!!
훨씬 수월하게 병합 정렬보다 공부할 수 있다.
그 이유는 바로 !!
퀵 정렬의 코드가 더 간결하다.
그리고 우리는 이미 병합정렬을 공부했다!
퀵 정렬은 글로 이해하면 난해하기에 그림을 보자 !
left, right, pivot, low, high 라는 이름을 부여해야한다 !
여기서 피벗은 정렬을 진행하는데 필요한 일종의 "기준" 이라고 할 수 있다.
low 의 오른쪽 방향 이동 : 피벗보다 큰 값을 만날때까지!
high 의 왼쪽 방향 이동 : 피벗보다 작은 값 만날 때까지
==>
low : 피벗보다 정렬의 우선순위가 낮은 데이터를 만날때까지 왼쪽으로 이동
high : 피벗보다 정렬의 우선순위가 높은 데이터를 만날때까지 오른쪽으로 이동
그러고 계속 이동하고 바꾸고 반복하다가!!
어랍쇼 low와high가 서로 역전됐다!!
이때 이제 !
퀵 정렬의 핵심연산이 진행된다.
바로! 피벗의 이동이다!
피벗이 high자리로 가게된다.
어랏!? 무엇인가 발견하지 않았는가!
바로 5가 자신 자리에 들어갔다는것이다!
5는 5번째 자리로 들어갔다
그뿐인가!!
5의 왼쪽편에는 5보다 작은 값들이
5의 오른쪽편에는 5보다 큰 값들이 있다.
그렇다면 이제 무엇하겠는가!
마지막 그림을 보면 다시 left right pivot을 설정하였다.
그리고 이를 left 와 right가 각각 정렬대상의 시작과 끝을 이미 하므로!
left > right 즉 서로 교차됐을때 끝나게 하면된다!
이제 함수를 보자
swap 함수는
void Swap(int arr[],int idx1, int idx2)
{
int temp = arr[idx1];
arr[idx1] = arr[idx2];
arr[idx2] = temp;
}이다!
어떤가!
생각보다 핵심함수가 할만해 보이지 않는가!
그저 하나의 반복문안에서 low,high가 이동하고
이동을 완료했다면 swap하는 함수이다.
이 함수가 반환하는 것은 제 자리를 찾은 피벗의 인덱스 값이다.
그리고 이 값을 기준으로 대상을 오른쪽 왼쪽 영역으로 나뉘기에 Partition 이라는 함수이름이 딱 들어맞다!
그럼 이제 재귀함수를 보즈아..
역시 재귀는 간단하면서도 쌔고 생각해내기 어려운것같다.
pivot에 파티션의 반환 값을 저장하고 left~pivot-1,pivot+1~right까지 다시 재귀!!!
키야.. 피벗은 이미 정렬이 완료된 영역이니 이 부분을 빼고 정렬을 진행하는 것이다! 그리고 재귀의 반복조건인 left<=right 일때 재귀가 진행된다.
아름답지 않는가!!! ㅠㅅㅠ
그럼 이어서 main함수와 그 실행 결과를 보여주겠다 !
#include <stdio.h>
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 = arr[left]; // pivot is most left
int low = left+1;
int high = right;
//교차되기전까지 반복
while(low <= high)
{
// find higher than pivot
while(pivot > arr[low])
low++; // low going right
// find lower than pivot
while(pivot<arr[high])
high --;
//교차 되지 않았을때 서로 교환
if(low<=high)
Swap(arr,low,high);
}
Swap(arr,left,high); // 피벗과 하이가 가리키는 대상 교환
return high; // 옮겨진 피벗의 위치정보 반환.
}
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(void)
{
int arr[7] = {3,2,4,1,7,6,5};
int len = sizeof(arr)/sizeof(int);
int i;
QuickSort(arr, 0, len-1); //arr에 대해서 퀵 정렬 진행 시작 !
for(i=0;i<len;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}크아.. 완전 간결하고 이쁘다.
결과 또한 굿굿 !
하지만... arr[3] = {3,3,3}을 넣고 돌려보자.
실행결과가.. 안나온다!
이는 Partition 함수를 빠져 나오지 못해서 발생하는 일이다.
pivot == arr[low] == arr[high] 가 3이 세 개인 배열을 절열한다면 성립한다.
while(low <= high) { // find higher than pivot while(pivot > arr[low]) low++; // low going right // find lower than pivot while(pivot<arr[high]) high --;이렇게 된다면 안쪽 while 조건은 항상 거짓이 되어 low는 증가 기회를.. high는 감소의 기회를 얻지 못한다.
따라서 바깥 while 문을 빠져나가지 못한다.
그러므로 우리는 변경을 해야한다!
while(pivot >= arr[low] && low<= right)
low++; // low going right
// find lower than pivot
while(pivot<=arr[high] && high >= (left+1))
high --;우선 < 연산자와 >연산자를 각각 >= 연산자와 <= 연산자로 바꿔 놓았다.
때문에 3이 세 개 저장된 상황에서도 이 두 연산의 결과는 "참"이 되어 low,high 는 각각 증가/감소 기회를 얻고 이로 인해 역전된다.
하지만!!
이것으로 끝난다면 low,high가 배열의 정렬 범위를 넘어서는 문제가 발생한다.
따라서 경계검사를 위해
low<=right
high>=left+1 을 추가해줬다.
left+1 인 이유는 굳이 설명 안해줘도 알겠지?
만 까먹을 수 도있으니 적겠다!
바로 ! 피벗을 제외시키기 위함이다.
이 부분은 퀵 정렬을 구현하는데 있어서 쉽게 놓치는 부분이다!
그러니 이 오류를 생각하고있자!
피벗의 선택
앞서 우리는 피벗을 제일 왼쪽에 있는 데이터를 피벗으로 결정하였는데 !
사실은
전체 데이터를 기준으로 중간에 해당하는 값을 피벗으로 결정할 때 좋은 성능을 보인다.
"피벗이 중간에 해당하는 값일 경우, 정렬대상은 균등하게 나뉜다"
뭔 말인지 극단적인 예를 보자 !
선택되는 피벗의 수는 Partition함수의 호출횟수를 의미하고 호출횟수가 많다는 것은 그만큼 데이터의 비교 및 이동의 횟수가 증가함을 뜻한다!
즉, 좋은 성능을 보이려면 최대한 중간 값에 가까운 피벗이 지속적으로 선택되어야 한다.
그리고 이를 위해서 다음과 같은 방법이 사용된다.
정렬대상에서 세 개의 데이터를 추출한다. 그리고 그 중에서 중간 값에 해당하는 것을 피벗으로 선택한다.
이를 위해서는 많은 방법이 있다.
예를들어 그저 앞에서 세개를 추출하는 방법이나 맨 앞 맨 뒤 중간 값 중에서 선택하는 경우나!
어쨌든 상식적인 수준에서 결정된다!
퀵 정렬 : 성능 평가
물론.. 피벗에 인해서 n보다 하나 적은 수의 비교연산이 이뤄지지만 이는 무시할 수 있다.
그리고 이는 분할된 상태에서도 마찬가지이다.
그럼 이제 분할이 몇 단계에 걸쳐서 이뤄지는가에 관심을 두자 !
31개의 데이터를 대상으로 퀵 정렬을 진행한다고 가정해보자.
피벗이 항상 중간 값으로 결정되는 이상적인 경우라고도 가정하자!
그렇다면
- 31개의 데이터는 15개씩 둘로 나뉘어 총 2조각 이 된다 1차 나뉨
- 이어서 각각 7개씩 둘로 나뉘어 총 4조각이 된다
2차 나뉨- 이어서 각각 3개씩 둘로 나뉘어 총 8조각이 된다.
3차 나뉨- 이어서 각각 1개씩 둘로 나뉘어 총 16조각이 된다.
4차 나뉨
이를 통해 무엇을 필자가 얘기하는지 알겠는가!!
바로!
둘로 나뉘는 횟수를 K라 할때 데이터의 수와 관계는 
이렇다!!
따라서 비교연산 횟수에 따라 빅오는 
이다!
그런데...
빅-오는 최악의 경우에 구해야하지 않는가?
왜 최선의 경우에서 빅-오를 구하고 끝을 낼려는가!!!
하지만!
퀵 정렬의 경우에는 약간의 예외를 둔다.
그 이유는 "중간에 가까운 피벗을 선택하는 방법"을 적용 함으로써, 늘 최선의 경우는 아니지만 최선의 경우에 가까운 성능을 평균적으로 보이기 때문이다.
따라서 ! 이는 최선의 경우가 아닌 평균의 경우에 대한 빅-오로 보기도 한다!
그래도
최악의 경우 빅오를 구해보자 .
윽! 이는 단순한 정렬 알고리즘에서나 볼 수 있는 빅-오 이다!
하지만 아무도 이 결과를 기준으로 퀵 정렬을 평가하지않고
퀵 정렬은 별도의 메모리공간을 요구하지도 않고 데이터 이동횟수가 상대적으로 적어서 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.
