Quick Sort 정렬 알고리즘

Quick Sort

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 기준점 Pivot 보다 작으면 왼쪽으로, 크면 오른쪽으로 swap하는 분할 함수
int Partition(string& str, int Left, int Right)
{
    char Pivot = str[Right]; // 마지막 요소를 기준 pivot으로 설정
    int i = Left - 1; // 작은 요소의 인덱스

    for (int j = Left; j <= Right; ++j)
    {
    	// 오름차순 정렬
        if (str[j] < Pivot)
        {
            i++;
            swap(str[i], str[j]); // 작은 요소를 왼쪽으로 이동
        }
    }
    swap(str[i + 1], str[Right]); // 기준이 되었던 Pivot 요소 값을 확정 위치로 swap.
    				  // str[i+1]보다 앞의 값들은 Pivot요소보다 작음.

    return i + 1; // 확정된 위치 인덱스 반환
}

void QuickSort(string& str, int Left, int Right)
{
    if (Left < Right)
    {
        int Pivot = Partition(str, Left, Right); // 분할하여 확정된 자리 인덱스 값 저장.
        QuickSort(str, Left, Pivot - 1); // 확정된 자리의 왼쪽 값들 재귀호출로 정렬.
        QuickSort(str, Pivot + 1, Right); // 확정된 자리의 오른쪽 값들 재귀호출로 정렬.
    }
}

int main() 
{
    string Str = "aBcDeF";
    
    QuickSort(Str, 0, Str.size() - 1);
    
    cout << Str;
    
    return 0;
}

 

퀵솔트는 평균적으로 O(n log n)의 속도를 가진 정렬 알고리즘이며, 최악의 경우엔 O(n2)이다.

• 오름차순으로 정렬한다고 가정했을 때, Pivot을 하나 정해서 왼쪽에는 Pivot보다 작은 값들을, 오른쪽엔 Pivot보다 큰 값들을 정렬해 분할한다.
• 이후 Pivot의 자리가 정해졌기 때문에 요소의 시작부터 Pivot - 1의 자리까지, Pivot + 1의 자리부터 요소의 끝까지 재귀호출을 하며 반복적으로 하나씩 자리를 확정해나가며 정렬한다.