퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)란?

한 데이터를 골라 Pivot으로 설정하고,

Pivot보다 작은 값은 왼쪽으로 넘기고 큰 값은 오른쪽으로 넘기면서 정렬하는 방식이다.

퀵 정렬의 특징

시간복잡도 최악 O(n^2), 평균 O(n log n)

 

분할정복 알고리즘이다.

평균적으로 매우 빠른 속도로 수행된다.

퀵 정렬 원리

1. 전체 배열을 대상으로 함수를 호출한다.

2. 가장 오른쪽 값을 Pivot으로 잡는다. (Pivot을 랜덤으로 잡으면 랜덤 퀵소트다.)

3. Pivot보다 작은 값들을 다 왼쪽으로 넘긴다. 

3. Pivot이 들어갈 위치에 있는 값과 가장 오른쪽 값을 swap한다.

4. Pivot을 제외하고, 왼쪽과 오른쪽 배열을 계속 재귀함수 부른다.

만드는 데 너무 오래 걸렸다... ㅋㅋ

퀵 소트 구현 (C++)

#include <iostream>
#include <ctime>

int Partition(int* arr, int l, int r)
{
    int pivot = arr[r]; // 가장 오른쪽 값을 피봇으로 잡는다.

    int pivotIndex = l; // 나중에 피봇이 들어갈 위치
    for (int i = l; i < r; i++) // 배열 앞에서부터 돌면서,
    {
        if (arr[i] < pivot) // 피봇보다 작은 값은 앞으로 땡긴다.
        {
            int temp = arr[i];
            arr[i] = arr[pivotIndex];
            arr[pivotIndex] = temp;

            // 피봇보다 작은 값이 있다는 뜻이므로,
            // 피봇이 들어갈 위치를 한 칸 뒤로 땡긴다.
            pivotIndex++;  
        }
    }

    // (피봇 위치에 있는 값)과 (피봇으로 잡은 가장 오른쪽 값)을 스왑한다.
    int temp = arr[r]; 
    arr[r] = arr[pivotIndex];
    arr[pivotIndex] = temp;

    return pivotIndex;
}
void QuickSort(int* arr, int l, int r)
{
    if (l >= r) // 배열 크기가 하나보다 작으면 더 이상 배열을 나누지 않는다.
    {
        return;
    }

    int p = Partition(arr, l, r); // 피봇 인덱스 반환

    // 피봇 인덱스를 제외한
    QuickSort(arr, l, p - 1); // 왼쪽 배열
    QuickSort(arr, p + 1, r); // 오른쪽 배열
}

int main()
{
    std::cout << "----------Random Value Array----------\n";
    srand((unsigned int) time(0));
    int arr[10];
    int arrLength = 10;
    for (int i = 0; i < arrLength; i++)
    {
        arr[i] = rand() % 100;
        std::cout << arr[i] << " ";
    }

    std::cout << "\n----------Quick Sort----------\n";
    QuickSort(arr, 0, arrLength - 1);
    for (int i = 0; i < arrLength; i++)
    {
        std::cout << arr[i] << " ";
    }
}

출력

----------Random Value Array----------
85 8 18 2 15 56 96 32 22 47
----------Quick Sort----------
2 8 15 18 22 32 47 56 85 96