[C] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

---

퀵정렬? 

퀵 정렬은 빠른 속도와, 간단한 구현방법 때문에

가장 많이 사용하는 정렬 방법으로 알려져 있습니다.

구현방법이 간편하다고 하지만, 개인적으로 이해하는데 시간이 좀 걸렸습니다.

퀵 정렬은 피벗으로 왼쪽에는 작은 값 오른쪽에는 큰값으로 정렬하는 방법입니다.

피벗?

특정 기준은 피벗(pivot)이라고 부릅니다.

복잡도

최악의 경우의 복잡도는 아래와 같지만 

(최악의 경우 : 피벗이 가장 작은 수 이거나 가장 큰 수가 계속 선정되는 경우)

평균적인 복잡도는 아래와 같습니다.

어떠한 방법?

피벗을 가장 마지막 인덱스로 설정했습니다.

아래와 같은 배열이 있을 때 

피벗 6을 기준으로 왼쪽과 오른쪽 끝에서부터

왼쪽은 6보다 큰 수 오른쪽은 6보다 작은 수를 찾습니다.

양쪽 다 찾은 수가 있다면 자리를 교환 해줍니다.

교환 후 계속해서 진행 한 후 

왼쪽과 오른쪽의 수가 같아 지면 종료하고 

피벗과 만난지점의 자리를 바꿔줍니다.

자리를 바꾼뒤 확인 해보면

피벗 기준으로 왼쪽에는 작은 수 오른쪽에는 큰수만 오게 됩니다.

각각 나눠진 영역에서 반복해서 같은 방법으로 진행 하면 정렬이 됩니다.

반복은 재귀호출로 진행하게 됩니다.

---

배열과 재귀호출을 이용한 퀵 정렬 예제

퀵 정렬 함수

if문 : 재귀 호출을 통해 종료를 위한 조건문

첫번째 while : 피벗보다 작은 수 큰 수를 찾기위한 반복문

두번째, 세번째 while : 각각 피벗보다 작은 수, 큰수를 찾는 반복문

첫번째 재귀 호출 : 피벗 기준 왼쪽을 정렬하기 위한 재귀 호출

두번째 재귀 호출 : 피벗 기준 오른쪽을 정렬하기 위한 재귀 호출

void quick_sort(int array[], int size){

int pivot, temp;

if(size>1){

pivot = array[size-1];

int left = -1;

int right = size-1;

while(1){

while(array[++left]<pivot);

while(array[--right]>pivot);

if(left>=right) break;

temp = array[left];

array[left] = array[right];

array[right] = temp;

}

temp = array[left];

array[left] = array[size-1];

array[size-1] = temp;

quick_sort(array, left);

quick_sort(array+left+1, size-left-1);

}

}

배열 출력 함수

void print_array(int array[], int size){

for(int i=0; i<size; i++){

printf("%-4d",array[i]);

}

printf("\n");

}

실행 함수

정렬 전 배열과 위의 기준대로 정렬한 결과를 출력합니다.

void main(){

int array[] = {2,7,1,3,4,0,8,5,9,6};

int size = sizeof(array)/sizeof(int);

printf("########### Sorting before ###########\n");

print_array(array, size);

quick_sort(array, size);

printf("########### Sorting after ###########\n");

print_array(array, size);

}

실행 결과

---

참고 : C로 배우는 알고리즘 (이재규)

위키백과(퀵 정렬)

---

관련 포스팅

[DataStructure] 기수 정렬(Radix Sort)

[DataStructure] 퀵 정렬(Quick Sort)

[DataStructure] 셸 정렬(Shell Sort)

[DataStructure] 버블 정렬(Bubble Sort)

[DataStructure] 삽입 정렬(Insertion Sort)

[DataStructure] 선택 정렬(Selection Sort)