퀵 정렬 quick sort

퀵 정렬

퀵 정렬이란

• 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이라고 한다.
• 균등하게 배열을 자르는 합병정렬과는 달리 퀵 정렬은 배열을 비균등하게 분할한다.

퀵 정렬 과정

1. 피봇 정하기: 배열 중 하나를 골라 pivot으로 선택한다,
   • 이때 pivot을 어떻게 선택하느냐가 퀵 정렬 수행 성능에 직접적인 영향을 미친다.
2. 분할: 피봇을 기준으로 피봇보다 작은 요소들은 모두 피봇의 왼쪽으로, 큰 요소들은 오른쪽으로 옮긴다.
3. 재귀: 피봇을 제외한 왼쪽과 오른쪽 배열을 다시 정렬한다.
   • 합병: 부분 리스트에서도 피봇을 다시 정하여 divide and conquer를 반복한다.
   • 부분리스트들이 더이상 분할이 불가능해질 때까지 반복한다.

예제

• 배열에 5 3 8 4 9 1 6 이 저장되어있다고 해보자.
• 해당 배열을 오름차순으로 정리할 것이다.

1. pivot 설정하기
   • pivot을 설정하는 방법: 1. 가장 앞, 2. 중간, 3. 가장 뒤의 원소를 선택하는 세가지 방법이 있다.
   • 여기서는 중간을 pivot으로 설정한다. 4가 pivot이 된다.
   • left: 가장 왼쪽 값, right: 가장 오른쪽 값
2. 인덱스 low, high를 이용하여 값 탐색하기
   • low
     - low는 왼쪽 부분리스트를 만드는데 사용된다.
     • 왼쪽에서부터 오른쪽으로 탐색하다가 pivot보다 큰 데이터를 찾으면 멈춘다.
   • high
     - high는 오른쪽 부분리스트를 만드는데 사용된다.
     • 오른쪽에서부터 왼쪽으로 탐색하다가 pivot 보다 작은 데이터를 찾으면 멈춘다.
   • 우리가 하고싶은 것은 오름차순 정렬이므로 pivot을 기준으로 작은데이터가 왼쪽, 큰 데이터가 오른쪽에 와야 한다. 때문에 low 와 high가 각각 pivot보다 크고 작은 데이터를 발견하면 멈추는 것이다.
   • 때문에 해당 값을 발견하게 되면, low와 high의 데이터를 swap한다.
3. 위의 탐색 과정은 low와 high가 서로 엇갈리지 않는 한 계속 반복된다.
   • while(low<high)
4. low와 high가 엇갈리는 순간 while문을 탈출하게 되고, 정렬이 완성된다.

해당 과정을 코드로 정리하면 다음과 같다.

코드

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int> &list, int left, int right){
    int pivot = list[(left+right)/2];
    int low = left;
    int high = right+1;

    while(low <high){
        //low가 범위 안에 있고 && 왼쪽 값이 pivot보다 작으면
        while(low <right && list[low]<pivot)
            low++; //low 오른쪽으로 한칸 이동
        //high가 범위 안에 있고 && 오른쪽 값이 pivot보다 크면
        while(high>left && list[high]>pivot)
            high--; //high 왼쪽으로 한칸이동
        //위의 두상황에 어긋나면 값 정렬 변경
        if(low <high)
            swap(list[low], list[high]);
    }
    swap(list[left], list[high]);
    return high;
}

void quickSort(vector<int> &list, int left, int right){
    if(left < right){
        int q = partition(list, left, right);
        quickSort(list, left, q-1);
        quickSort(list, q+1, right);
    }
}

int main (){
    int n;
    cin >> n;
    
    vector<int> numbers;
    numbers.assign(n, 0);

    //입력
    for(int i=0; i<n; i++){
        cin >> numbers[i];
    }
    //연산
    quickSort(numbers, 0, n-1);

    //출력
    for(int i=0; i<n; i++){
        cout << numbers[i] << '\n';
    }


    return 0;
}