Quick Sort 알고리즘

Quick Sort

퀵정렬이란?

찰스 앤터니 리처드 호어가 개발한 범용 정렬 알고리즘으로, 현 알고리즘 중 가장 고성능(최적의 항에서) 을 자랑하는 알고리즘으로, 주어진 배열을 정렬하는 분할 정복(Divide and Conquer)알고리즘 이다.

 

분할정복

알고리즘의 기본 해결방법으로, 엄청 크고 방대한 문제를 조금조금씩 나눠가면서 용이하게 풀 수 있는 문제단위로 나눈 다음 다시 합쳐서 해결하는 방식

 

특징 및 장점

• 평균 시간 복잡도는 O(n long n)이다. 가장 최악으로 치솟으면 O(n^2)이다.
• 제자리 정렬(in-place Sort)로, 추가적인 메모리 공간이 거의 필요가 없다.
• 비교 기반 정렬 알고리즘 중 가장 빠른 알고리즘 중 하나이다.

퀵정렬의 과정

퀵 정렬은 다음과 같은 과정으로 배열을 정렬한다.

1. 배열에서 피벗(pivot)을 선택한다.(피벗은 임의의 수를 이야기함)
2. 피벗을 기준으로 배열을 두 부분으로 분할한다. 피벗보다 작은 요소는 왼쪽에 큰 요소는 오른쪽에 배치되게 한다.
3. 왼쪽 부분배열 과 오른쪽 부분 배열에 대해 동일한 과정을 반복한다.

---

원리

쉽게 정리하면 다음과 같다.

 그리고 끝까지 이동헀을 때, 6을 중앙으로 옮기고 다시 처음부터 반복한다.

다시 처음부터 4를 Pivot으로 잡고 반복

 

여기에 분할정복 알고리즘을 섞으면 처음에 있던 GIF와 같은 방식으로 정렬이 이루어진다.

 

구현

 

C++코드로 구현하면 다음과 같이 이루어진다.

void quickSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int pivotIndex = partition(arr, left, right);
        quickSort(arr, left, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, right);
    }
}

int partition(std::vector<int>& arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[right]);
    return i + 1;
}