8. 퀵정렬 - 배열 선언 / 구현하기 / 사용하기

퀵정렬

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

원소를 절반씩 나눌 때 logN의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리이다. 각각의 부분 배열들이 각자 정렬을 수행하는 점에서, 퀵정렬의 이러한 구조는 완전 이진트리와 흡사하다. 완전 이진 트리 형태는 컴퓨터 공학에서 가장 선호하는 이상적인 형태이다.

 

퀵정렬 - 배열선언

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000

int a[SIZE];

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

퀵정렬 구현하기

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);
}

퀵정렬 사용하기

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]);
    system("pause");
    return 0;
}

 

퀵정렬은 편향된 분할이 발생할 때, 연산의 양이 O(N^2)이다. 따라서 실제로 정렬을 할 땐 퀵 정렬을 직접 구현하지 않는다. C++의 Algorithm 라이브러리를 사용한다. Algorithm 라이브러리의 sort() 함수는 퀵 정렬을 기반으로 하되 O(NlogN)을 보장한다.