자료구조 - 퀵 정렬

[퀵 정렬(Quick Sort)]

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘의 하나로, 평균적으로 가장 빠른 정렬 알고리즘 중 하나입니다.

리스트를 분할하고 정복하며, 재귀적으로 정렬을 수행합니다.

퀵 정렬은 피벗(pivot)을 선택하여 리스트를 분할하고, 분할된 부분 리스트를 정렬합니다. 시간 복잡도는 평균적으로 O(nlogn) 이지만, 최악의 경우 O(n^2) 입니다.

 

 

 

 

퀵 정렬 과정

1. 리스트에서 피벗을 선택합니다. 보통 리스트의 중간 요소를 선택합니다.
2. 피벗을 기준으로 작은 요소는 피벗의 왼쪽으로, 큰 요소는 피벗의 오른쪽으로 분할합니다.
3. 분할된 부분 리스트에 대해 재귀적으로 퀵 정렬을 수행합니다.
4. 재귀적인 호출이 끝나면 모든 부분 리스트가 정렬되었으므로 리스트를 합병합니다.

 

퀵 정렬 의사 코드

함수 quickSort(arr, low, high):
    if low < high:
        // 리스트를 분할하고 피벗의 인덱스를 반환
        pivot_idx = partition(arr, low, high)

        // 피벗을 기준으로 왼쪽 부분 리스트 정렬
        quickSort(arr, low, pivot_idx - 1)
        // 피벗을 기준으로 오른쪽 부분 리스트 정렬
        quickSort(arr, pivot_idx + 1, high)

함수 partition(arr, low, high):
    pivot = arr[high]  // 피벗을 선택
    i = low - 1  // 작은 요소들의 끝을 나타내는 인덱스

    for j = low부터 high-1까지:
        if arr[j] <= pivot:
            i += 1
            arr[i]와 arr[j]를 교환

    arr[i + 1]와 arr[high]를 교환  // 피벗을 올바른 위치로 이동
    반환 i + 1  // 피벗의 인덱스 반환

 

 

퀵 정렬 예제

예시 리스트: [64, 25, 12, 22, 11]

첫 번째 재귀 호출:
    리스트를 피벗을 기준으로 분할하여 피벗의 인덱스를 반환합니다.
    피벗을 기준으로 왼쪽 부분 리스트([25, 12, 22, 11])와 오른쪽 부분 리스트([64])로 나뉩니다.

두 번째 재귀 호출(왼쪽 부분 리스트):
    왼쪽 부분 리스트를 다시 분할하여 피벗의 인덱스를 반환합니다.
    피벗을 기준으로 왼쪽 부분 리스트([12, 11])와 오른쪽 부분 리스트([25, 22])로 나뉩니다.

세 번째 재귀 호출(왼쪽 부분 리스트):
    왼쪽 부분 리스트는 더 이상 분할할 수 없으므로 재귀 호출이 종료됩니다.

세 번째 재귀 호출(오른쪽 부분 리스트):
    오른쪽 부분 리스트도 더 이상 분할할 수 없으므로 재귀 호출이 종료됩니다.

 

 

 

퀵 정렬 코드

#include <iostream>
#include <vector>

using namespace std;

// 리스트를 피벗을 기준으로 분할하고 피벗의 인덱스를 반환
int partition(vector<int>& arr, int low, int high) 
{
    int pivot = arr[high];  // 피벗 선택
    int i = low;  // 작은 요소들의 끝을 나타내는 인덱스

    for (int j = low; j < high; j++) 
    {
        if (arr[j] <= pivot)
        {
            swap(arr[i], arr[j]);
            i++;
        }
    }
    swap(arr[i], arr[high]);  // 피벗을 올바른 위치로 이동
    return i;
}

// 퀵 정렬 함수
void quickSort(vector<int>& arr, int low, int high)
{
    if (low < high) 
    {
        // 리스트를 분할하고 피벗의 인덱스를 반환
        int pivot_idx = partition(arr, low, high);

        // 피벗을 기준으로 왼쪽 부분 리스트 정렬
        quickSort(arr, low, pivot_idx - 1);
        // 피벗을 기준으로 오른쪽 부분 리스트 정렬
        quickSort(arr, pivot_idx + 1, high);
    }
}

int main() 
{
    vector<int> arr = {64, 25, 12, 22, 11};  // 예제 리스트

    cout << "정렬 전: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    // 퀵 정렬 수행
    quickSort(arr, 0, arr.size() - 1);

    cout << "정렬 후: ";
    for (int i : arr) 
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}