[알고리즘] 퀵 소트

퀵 소트

• 피벗을 이용
• i, j 포인터를 설정한다.
• i는 피봇을 제외한 처음 원소부터 피봇보다 큰 값을 찾는다.
• j는 끝에서부터 피봇보다 작은 값을 찾는다.
• i번째와 j번째를 바꾼다.
• 찾는도중에 i > j 가 되었다. (엇갈렸다.)
• 피봇과 j를 바꾼다.
• 바꾸게 되면, 피봇의 좌측으로는 피봇보다 작은값들만 존재하게 된다.
• 반대로 피봇의 우측으로는 피봇보다 큰 값들만 존재하게 된다.
• 분할정복 알고리즘을 통해 피봇을 기준으로 좌측과 우측에서 각각 다시 퀵 정렬을 수행한다.
• 이렇게 분할정복 알고리즘을 사용하기 때문에 빠른 속도로 정렬을 수행할 수 있다.
• 출처

#include <iostream>

using namespace std;

void quick_sort(int *data, int start, int end){
    if(start >= end){
        // 원소가 1개인 경우
        return; 
    }
    
    int pivot = start;
    int i = pivot + 1; // 왼쪽 출발 지점 
    int j = end; // 오른쪽 출발 지점
    int temp;
    
    while(i <= j){
        // 포인터가 엇갈릴때까지 반복
        while(i <= end && data[i] <= data[pivot]){
            i++;
        }
        while(j > start && data[j] >= data[pivot]){
            j--;
        }
        
        if(i > j){
            // 엇갈림
            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        }else{
            // i번째와 j번째를 스왑
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    } 
    
    // 분할 계산
    quick_sort(data, start, j - 1);
    quick_sort(data, j + 1, end);
}

int main(void)
{
    int data[10] = {4, 1, 2, 3, 9, 7, 8, 6, 10, 5};

    quick_sort(data,0,9);

    for(int i = 0; i<10;i++) cout<<data[i]<<" ";
    return 0;
}