정렬 - 퀵정렬

퀵 정렬

퀵 정렬은 정렬 중에서 빠른 속도로 인해 유명한 대표적인 정렬 방법론 중 하나이다.

이는 분할 정복 방법을 통해서 배열을 정렬하게 된다.

배열의 값들 중 하나의 원소를 고르고, 이를 피벗이라고 명한다.

이 앞에는 피벗보다 작은 값이 오도록, 이 뒤에는 큰 값이 오도록 배열을 정렬하고 둘로 나눈 뒤,

다시 이 작은 배열에 대해 재귀적으로 퀵 정렬을 반복한다.

generateRandomArray, printArray, swap

int partition(int *myArray, int left, int right) {
    int pivot = myArray[left];
    int i = left, j = right;

    while (i < j) {
        while (pivot < myArray[j]) {
            j--;
        }
        while (i < j && pivot >= myArray[i]) {
            i++;
        }
        swap(&myArray[i], &myArray[j]);
    }
    swap(&myArray[left], &myArray[i]);

    return i;
}

void quickSort(int *myArray, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(myArray, left, right);

        quickSort(myArray, left, pivotIndex - 1);
        quickSort(myArray, pivotIndex + 1, right);
    }
}

static int arrayLength = 20;
int *myArray = generateRandomArray(arrayLength);

printArray(myArray, arrayLength);

quickSort(myArray, 0, arrayLength - 1);

printArray(myArray, arrayLength);

free(myArray);

작은 것부터, 점점 커지게, 오름차순으로 정렬한 예제이다.

퀵 정렬은 최선의 경우 O(N * log N) 의 복잡도를, 최악의 경우 O(N²)의 복잡도를 가지게 된다.

하지만 불필요한 데이터의 이동을 줄이고, 한 번 결정된 피벗들은 재 연산때 필요하지 않게 되므로, 빠른 속도를 보장할 수 있다.

다만 불안정 정렬이라는 단점이 존재한다.