[C 알고리즘] 퀵 정렬 - Quick Sort Algorithm

퀵 정렬은 이름부터 퀵 정렬이다. 당연히 앞의 3개 정렬이 가지는 시간복잡도 O(N^2)보다는 빠를 것이다.

퀵 정렬은 대표적인 분할정복 알고리즘으로  O(N*logN)의 시간복잡도를 가진다.

 

퀵 정렬은 피벗값(=키값)이라는 개념이 등장하게 되는데 이것을 먼저 받아들여야한다.

보통 피벗값은 가장 앞에있는 값을 일반적으로 선택한다.

 

피벗값을 선택 한 후에 , 왼쪽에서 피벗값보다 큰 값을 선택하고, 오른쪽에서 작은 값을 선택한다.

예시를 통해 나타내자면

3 7 8 1 5 9 6 10 2 4 // 피벗값 : 3 , 왼쪽에서 선택한 큰 값 : 7 , 오른쪽에서 선택한 작은 값 2

이게 일반적인 반복상황이다. 이런 경우에 7과 2를 바꾸어준다. 이런 과정을 언제까지 반복하냐면

엇갈릴때까지 반복한다. 여기서 말하는 엇갈린다는 것은

지금 경우를 보면 인덱스가 작은쪽에서 큰 값을 선택하고, 인덱스가 큰쪽에서 작은 값을 선택하여

그것을 바꾸어준다. 즉 오름차순으로 정렬하는 것이다.

 

근데 만약 반복을 거치다보니 다음과 같은 상황이 되었다고 생각해보자.

3 2 1 8 5 9 6 10 7 4 // 피벗값 : 3, 왼쪽에서 선택한 큰 값 : 8, 오른쪽에서 선택한 작은 값 : 1

이미 오름차순으로 정렬되어있음을 알수있다. 우리는 오름차순 정렬을 해야하는데 3이라는 피벗값을 두고

오름차순 정렬을 반복하다보니, 더이상 정렬할게 남지 않은것이다. 이제 더 이상 피벗값 3은 역할을 할수없다.

이 상황을 엇갈렸다고 표현한다. 나는 이 말을 특정 피벗값의 역할이 끝났다라고 이해했다. 

 

이렇게 엇갈린 경우에 새로운 피벗값을 설정해주어야한다. 그 방법은 두 개의 선택된 값 1,8중에서 작은 값인 1과

피벗값 3을 바꾸어 주면 된다. 이것은 받아들여야한다

 

1 2 3 8 5 9 6 10 7 4 // 여기서 새로운 피벗값 1, 그리고 파란색으로 표시된 3은 정렬되었다고 하고 3을 기준으로 

 좌     우의 집합이       분할된것을 알수있다.  이 분할된 집합에 위와 같은 과정을 다시 거친다. 

1 2 // 8 5 9 6 10 7 4

 

즉 정리하자면 특정 피벗값을 가지고 엇갈릴때까지 오름차순 정렬을 반복하다가, 엇갈리게되면(= 피벗값의 역할이 끝나게되면) 새로운 피벗값을 설정하고 그 이전의 피벗값이 정렬되게 되면서 두 집합으로 분할된다.

그 분할된 집합에 또 위 과정을 반복하는것이다. 

 

이러한 알고리즘때문에 분할정복 알고리즘을 썼다고 하는 것이다.

 

 

처음 퀵 정렬을 접했을때  함수 재귀호출이 낯설어서 굉장히 이해가 어려웠었다. 다른 글에서 재귀호출 방식을 연습하는 주제로 글을 다룰것이다.

 

코드를 파트별로 나누어서 설명을 해서 이해를 돕겠다.

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

void quicksort(int* data, int start, int end) {     if (start >= end) { //원소가 1개인경우 그대로 두기         return;     }       int key = start;     int i = start + 1; // i는 왼쪽 시작영역에서 부터 출발하여 큰 값을 찾는 애     int j = end;// j는 오른쪽 끝 영역에서부터 출발하여 작은 값을 찾는애    int temp;     while (i <= j) // 엇갈리지않았다면 반복     {         while (i <= end && data[i] <= data[key]) { //키 값보다 큰 값을 만나기 위해  작은값의 조건일때는 i++반복             i++;         }         while (j > start&& data[j] >= data[key]) { //키 값보다 작은값을 만나기위해  큰 값의 조건일때는 j--반복             j--;         }           if (i > j) {//while 탈출조건일경우, (즉 엇갈린경우), if문을 시행하고 탈출              temp = data[j];             data[j] = data[key];             data[key] = temp;         }         else{             temp = data[i];             data[i] = data[j];             data[j] = temp;               }     }     quicksort(data, start, j - 1);     quicksort(data, j+1, end); } Colored by Color Scripter

cs

먼저 start와 end는 처음 호출에서 당연히 0부터 배열의 마지막 인덱스까지이다.

변수선언내용

위의 알고리즘에서 언급한대로 key값은 피벗값으로 일반적으로 처음값 즉 start 값으로 설정한다.

i는 start+1로 지정해두고 ( 피벗값 바로 오른쪽이 시작지점),

j는 end 지점으로 둔다

while문은 엇갈릴때까지 반복한다.

여기 큰 while문을 엇갈릴때까지 즉 설정된 피벗값이 역할을 다 할때까지 반복한다. 이 한번의 반복이 끝나면

두 집합으로 분할되는것이라고 이해하면 된다.

data[i]는 data[key] (= 피벗값)과 비교하여 큰 값을 찾는 것이고

data[j]는 data[key] (= 피벗값)과 비교하여 작은 값을 찾는 것이다.

 

일반적으로는 두 값을 반복해서 스왑해주다가 만약 엇갈린다면(=피벗값의 역할이 끝났다면) 새로운 피벗값을 설정해주고 while문을 탈출하게된다. 

 

분할정복을 위한 재귀호출

그 뒤 정렬된 피벗값을 기준으로 좌 우를 분할하고 그 분할된 집합 각각에 또 정렬을 수행한다.

 

 

 

// 5개의 정수를 오름차순으로 정렬하는 퀵 정렬 구현 코드

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

#pragma warning(disalbe:4996) #include <stdio.h> int number = 5; int data[] = { 10,1,2,3,4}; void show() {     int i;     for (i = 0; i < number; i++) {         printf("%d", data[i]);     } }   void quicksort(int* data, int start, int end) {     if (start >= end) { //원소가 1개인경우 그대로 두기         return;     }       int key = start;     int i = start + 1;     int j = end;         int temp;     while (i <= j) // 엇갈리지않았다면 반복     {         while (i <= end && data[i] <= data[key]) { //키 값보다 큰 값을 만나기 위해 작은값의 조건일때는 i++반복             i++;         }         while (j > start&& data[j] >= data[key]) { //키 값보다 작은값을 만나기위해 큰 값의 조건일때는 j--반복             j--;         }           if (i > j) {//while 탈출조건일경우, (즉 엇갈린경우), if문을 시행하고 탈출              temp = data[j];             data[j] = data[key];             data[key] = temp;         }         else{             temp = data[i];             data[i] = data[j];             data[j] = temp;               }     }     quicksort(data, start, j - 1);     quicksort(data, j+1, end); }   int main() {     quicksort(data, 0, number - 1);     show();     return 0; } Colored by Color Scripter

cs