[C] 퀵 정렬이란? C언어로 퀵 정렬 구현하는 코드

1. 퀵 정렬이란

 

퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는 데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로, 평균적으로 0(NlogN)의 시간 복잡도를 가진다. 

 

퀵 정렬은 편향된 분할이 발생할 때 연산의 양이 최악의 경우 O(N2) 이다. 따라서 실제로 정렬할 때는 퀵 정렬을 굳이 직접 구현하지는 않는다. C++에 Algorithm 라이브러리에 포함된 sort() 함수는 퀵 정렬을 기반으로 하면서 O(NlogN)을 보장한다. 

 

피벗 값이 가장 왼쪽이라고 가정한다.

5

4

3

8

9

6

7

1

10

2

 

(1) 5의 왼쪽부터 시작해서 5보다 큰 값을 찾는다. 또 오른쪽부터 시작해서 5보다 작은 값을 찾는다. 그리고 둘을 교체한다.

5

4

3

8

9

6

7

1

10

2

교체 후,

5

4

3

2

9

6

7

1

10

8

 

(2) 다시 왼쪽부터 하나씩 살피며 5보다 큰 수를 찾고, 오른쪽부터 하나씩 살피며 5보다 작은 수를 찾아 둘을 교체한다.

5

4

3

2

9

6

7

1

10

8

교체 후,

5

4

3

2

1

6

7

9

10

8

 

(3) 마찬가지로 왼쪽부터 5보다 큰 수, 오른쪽부터 5보다 작은 수를 찾는다. 그런데 이번엔 둘의 위치가 엇갈려서 큰 수가 작은 수보다 뒤에 온다.

5

4

3

2

1

6

7

9

10

8

이 경우, 작은 값과 피벗 값을 바꿔준다.

1

4

3

2

5

6

7

9

10

8

 

(4) 5를 기준으로 5를 포함하여 왼쪽에 있는 수끼리, 5보다 오른쪽에 있는 수 끼리 재귀적으로 똑같은 연산을 수행해 준다. 

1

4

3

2

5

6

7

9

10

8

 

(5) 완성

1

2

3

4

5

6

7

8

9

10

 

원소를 절반씩 나눌 때 logN의 시간 복잡도가 나오는 대표적인 구조가 완전 이진 트리다. 정렬을 한 번 마친 후 오른쪽과 왼쪽에서 각각 수행을 하기 때문에 높이가 짧다.

 

2. 퀵 정렬 구현

 

(1) 배열 a를 초기화해주고 swap 함수를 만든다.

#include <stdio.h> 
#define SIZE 1000

int a[SIZE];

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

 

(2)  해당 부분 배열의 시작과 끝 인덱스를 인자로 받는 quickSort 함수를 만들어준다.

- i는 왼쪽에서, j는 오른쪽에서 출발한다.

- i 인덱스와 j 인덱스가 엇갈리지 않을 때까지만 반복하는 while문에서는 부분 배열에서 피벗보다 큰 값, 작은 값을 하나씩 찾아내어 교체하는 작업을 한 번씩 해 준다.

- 그 작업이 끝나면 부분배열을 나눠서 quickSort 함수를 재귀적으로 호출해 준다.

void quickSort(int start, int end) {
    if (start >= end) return;
    int key = start, i = start + 1, j = end, temp;
    while (i <= j) {
        while (i <= end && a[i] <= a[key]) i++; 
        while (j > start && a[j] >= a[key]) j--;
        
        if (i > j) swap(&a[key], &a[j]);
        else swap(&a[i], &a[j]);
    }
    
    quickSort(start, j - 1);
    quickSort(j + 1, end); 
}

 

(3) 입력을 받아서 퀵 정렬을 해 본다.

int main(void) {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    quickSort(0, n - 1);
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
}

 

(4) 결과를 확인한다.

5
3 4 1 9 7
1 3 4 7 9