퀵 정렬(Quick Sort) 알고리즘 (C언어 구현)

1. 퀵 정렬 소개

 

퀵 정렬은 분할 정복(Divide and Conquer)을 통하여 평균적으로 빠른 속도로 정렬을 하는 알고리즘이다.

 

n개의 데이터에 대하여 평균적인 시간 복잡도는 O(n log n)이지만, 최악의 경우에는 O(n^2)이다.

 

2. 퀵 정렬 알고리즘 동작 과정

 

1) 리스트 안에 한 원소를 pivot으로 설정한다.

 

2) pivot보다 작은 요소들은 pivot 앞으로 옮기고 pivot보다 큰 요소들은 pivot뒤로 옮긴다.

 

3) pivot을 제외한 왼쪽 리스트와 오른쪽 리스트에 대하여

각각 위의 1) ~ 2) 과정을 분할이 불가능할 때까지 반복한다.

 

3. 그림을 이용한 설명

 

초기 리스트: {2, 4, 1, 8, 6, 3, 5, 7}

초기 리스트

 

pivot을 시작점으로 설정하며 pivot 다음 요소부터 가장 작은 값은 left, 가장 큰 값은 right가 가리킨다.

 

left = 1, right = 7

 

left가 가리키는 값은 pivot값보다 큰 값이 나올 때까지 오른쪽으로 이동하며,

right가 가리키는 값은 pivot값보다 작은 값이 나올때 까지 왼쪽으로 이동한다.

 

left = 1, right 2

 

이동을 완료한 시점에서 right 자체값이 left 자체값보다 크므로 각자 가리키는 값을 swap 한다.

 

left,right swap 결과

 

아직 left 값이 right 값보다 작으므로 위의 과정을 반복한다.

그렇게 되면 left가 가리키는 값은 4, right가 가리키는 값은 1이 된다.

 

left = 2, right = 1

 

left 자체 값이 right 자체값보다 커졌으므로 right이 가리키는 값과

pivot이 가리키는 값을 swap 하고 반복문은 종료된다.

 

pivot, right swap 결과

 

이제 다음은 start = 2, end = 7을 인자로 하는 함수가 실행되며 pivot, left, right를 표시하면 아래와 같다.

 

left = 3, right = 7

 

left 자체 값이 right자체 값보다 커질 때까지 위의 과정을 반복한다.

 

left = 3, right = 5 -> left,right swap

 

left = 4, right = 3 -> pivot, right swap

 

다음은 start = 4, end = 7로 하는 함수가 실행되며 위의 과정을 반복한다.

 

left = 5, right = 7

 

left = 5, right = 7 -> left,right swap

 

left = 6, right = 5 -> pivot, right swap

 

다음은 start = 6, end = 7에 대하여 함수가 실행된다.

left, right 값은 7로 동일하며 우측에 pivot보다 큰 값은 없기에 left 자체 값은 8로 업데이트된다. 

그러므로 left 자체 값이 right 자체 값보다 크므로 pivot과 right을 swap 한다.

 

left = 8, right = 7 -> pivot, right swap

 

이렇게 하여 정렬이 완성되었다.

 

4. 알고리즘 코드

#include <stdio.h>
#define size 8

void printArray(int* data) {
    int i;
    for (i = 0; i < size; i++) printf("%d ", data[i]);
    printf("\n");
}

void quickSort(int* data, int start, int end) {
    if (start >= end) return; // 요소의 개수가 1개인 경우
    
    printf("start = %d end = %d\n", start, end);    //start, end위치 출력
    int pivot = start; // 피봇: 첫 번째 요소
    int left = start + 1, right = end, temp;

    while (left <= right) { // 엇갈릴 때까지 반복 
        while (left <= end && data[left] <= data[pivot]) {
            left++; //pivot이 가리키는 값보다 큰 값을 만날 때까지
        }
        while (right > start && data[right] >= data[pivot]) {
            right--; // pivot이 가리키는 값보다 작은 값을 만날 때까지
        }
        if (left > right) { //pivot값과 right값 swap
            temp = data[right];
            data[right] = data[pivot];
            data[pivot] = temp;
        }
        else {
            temp = data[left];  //left값과 right값 swap
            data[left] = data[right];
            data[right] = temp;
        }
    }
    printArray(data);   //배열 출력
    quickSort(data, start, right - 1);  //왼쪽 리스트 재귀적 반복
    quickSort(data, right + 1, end);    //오른쪽 리스트 재귀적 반복
}

int main(void) {
    int arr[] = { 2, 4, 1, 8, 6, 3, 5, 7 };
    quickSort(arr, 0, size - 1);
    return 0;
}

 

실행 화면