0x09.정렬 알고리즘(3):퀵 정렬

4.퀵 정렬(Quick Sort)

위 정렬 방법은 리스트에서 기준점이 되는 데이터를 선정한 후에, 기준보다 작은 데이터들을 왼쪽으로, 큰 데이터들을 오른쪽으로 정렬해나가는 방식으로 기준점을 기준으로 정렬이 완료가 되면 기준점의 좌우로 다시 분할하여 정렬을 하는 방식이다.

위와 같은 리스트가 있다고 가정해보자. 위의 리스트에서는 arry[4]의 데이터 값은 5가 기준(pivot)점이 된다.

파란색으로 표시된 부분을 시작으로 맨 왼쪽부분은 5보다 큰 값을 가진 값이 나올때까지 한 칸씩 오른쪽으로, 맨 오른쪽부분은 작은 값이 나올때까지 한 칸씩 왼쪽으로 이동하며 값을 비교한다.

여전히 기준값을 기준으로 조건에 맞지 않기에 계속해서 이동하며 값을 비교한다.

자 array[2]의 값은 6으로 기준값보다 크고, array[5]의 값은 4로 기준값보다 작다. 이제 이 두 값을 아래와 같이 스왑해준다.

이렇게 정렬을 해주면 기준값을 기준으로 왼쪽에서 작은 값들만, 오른쪽에는 큰 값들만 모여있게 된다. 이제 기존의 기존값의 왼쪽과 오른쪽으로 분할을 한다.

위와 같이 분할을 하면 새로운 기준점을 정하고 다시 정렬을 실시한다.

이번에는 새로운 기준점으로 array[1]과 array[5]가 지정되었다.

그룹의 크기가 1이 될때까지 반복 수행하면 위와 같이 정렬된 리스트를 얻을 수 있다.

void QuickSort(int *array, int leftstart, int rightstart)   //인자로 배열, 가장 왼쪽, 가장 오른쪽

{

int temp;                                                    //자리변경에 사용됨

int left=leftstart;                                           //검색 데이터 위치(왼쪽, 아래는 오른쪽)

int right=rightstart;                                      

int pivot=array[(left+right)/2];                          //기준점 잡기

while(left<=right)                                         

{

while(array[left]<pivot)

left++;

while(array[right]>pivot)

right--;

if(left<=right)                                           //조건 일치 시 데이터 교환

{

temp=array[left];

array[left]=array[right];

array[right]=temp;

left++;

right--;

}

}

if(leftstart<right)                                             //데이터 교환 과정에서 left와 right 위치가 바뀜!!

QuickSort(array,leftstart,right);

if(left<rightstart)

QuickSort(array,left,rightstart);

}

※ 위 그림 예제는 코드와 실행 결과가 다를 수 있음