퀵정렬(quick sort)

퀵정렬(quick sort)

---

피벗을 선택후 피벗 기준 분리 후 재귀적으로 정렬
원리

1. 피벗 선택 → 피벗 기준 앞-뒤로 교환(정렬)
2. 분리된 사이의 값을 피벗으로 재설정(재귀)
3. 재설정된 피벗 기준으로 다시 분리(정렬)

pseudocode

힙정렬(base : 배열시작주소, n : 배열요소 개수)
1. 배열을 최대 힙으로 구성
    반복(i : n/2 - 1 -> 0)
        최대 힙 구성 함수 호출 (base, n, i)

2. 정렬 수행
    반복(i : n-1 -> 1)
        base[0]와 base[i] 교환
        최대 힙 구성 함수 호출 (base, i, 0)

최대 힙 구성 함수(base : 배열시작주소, n : 배열요소 개수, i : 현재 노드 인덱스)
    // 현재 노드와 자식들 중에서 최대값을 찾아 교환
    // 교환된 자리에 대해 재귀 호출

best case 시간복잡도 : $O(n$ $log$ $n)$
avg case 시간복잡도 : $O(n$ $log$ $n)$
worst case 시간복잡도 : $O(n^2)$ (피벗을 잘못 선택한 경우)
안정성 : 불안정
장점 : 평균적으로 가장 빠른 정렬(분)
단점 : 정렬된 리스트인 경우 시간이 더 걸림

실제코드

#include <stdio.h>

// 두 요소를 교환하는 함수
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Median-of-Three 방식으로 피벗 선택
int medianOfThree(int arr[], int left, int right) {
    int mid = (left + right) / 2;

    // 세 값 중 중간값을 선택
    if (arr[left] > arr[mid]) swap(&arr[left], &arr[mid]);
    if (arr[left] > arr[right]) swap(&arr[left], &arr[right]);
    if (arr[mid] > arr[right]) swap(&arr[mid], &arr[right]);

    // 피벗을 right - 1 위치에 놓고 반환
    swap(&arr[mid], &arr[right - 1]);
    return arr[right - 1];
}

// 퀵정렬 함수
void quickSort(int *arr, int left, int right) {
    // 무한 재귀 탈출
    if (left >= right) return;

    // 피벗 선택
    int pivot = medianOfThree(arr, left, right);
    int i = left;
    int j = right - 2; // 조정된 인덱스

    // 피벗 기준 앞-뒤로 교환
    while (1) {
        while (arr[++i] < pivot);
        while (arr[--j] > pivot);
        if (i < j) {
            swap(&arr[i], &arr[j]);
        } else {
            break;
        }
    }

    swap(&arr[i], &arr[right - 1]); // 피벗을 최종 위치로 이동

    // 분할 후 재귀 호출
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}

int main() {
    int arr[20] = {
        3, 5, 2, 2, 4,
        6, 1, 3, 7, 8,
        2, 11, 2, 21, 20,
        12, 14, 1, 6, 16
    };
    int n = sizeof(arr) / sizeof(int);
    quickSort(arr, 0, n - 1);

    // 정렬된 배열 출력
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}