Quick Sort

http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/Database/algorithm/Quick_Sort

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

  • 최악일 때 n^2, 최선 nlogn, 그러나 컴퓨터 아키텍처에서 효율적으로 작동하기 때문에 오히려 다른 nlogn 정렬보다 빠름
  • 피봇의 위치가 퀵 정렬의 성능을 좌우

 

과정

  1. 리스트 안에 있는 한 요소 (피벗)을 선택
  2. 피벗을 기준으로 피벗보다 작은 요소는 피벗 왼쪽, 큰 요소는 피벗 오른쪽으로 옮김
  3. 피벗을 제외한 왼쪽 리스트와 오르쪽 리스트를 다시 정렬
    • 분할된 부분 리스트에 대하여 순환 호출하여 정렬 반복
    • 부분 리스트에서도 다시 피벗 정하고 피벗 기준으로 2개의 부분 리스트로 나누는 과정 반복
  4. 부분 리스트들이 더이상 분할 불가능 할 때까지 반복
    • 리스트의 크기가 0이나 1이 될 때 까지
#include <stdio.h>
#include <iostream>
using namespace std;

void Quick_Recursive(int data[], int left, int right){
    int pivot, l_hold, r_hold;
    l_hold = left; r_hold = right;
    pivot = data[left];//0번째 원소를 pivot으로 선택

    while (left < right){

        //값이 선택한 피봇과 같거나 크다면, 이동할 필요가 없다 
        while ((data[right] >= pivot) && (left < right))right--;
       
        //그렇지 않고 값이 피봇보다 작다면, 피봇의 위치에 현재 값을 넣는다
        if (left != right) data[left] = data[right];

        //왼쪽부터 현재 위치까지 값을 읽어들이면서 
        //피봇보다 큰 값이 있다면, 값을 이동한다
        while ((data[left] <= pivot) && (left < right)) left++;
        if (left != right) {
            data[right] = data[left];
            right--;
        }
    }

    //모든 스캔이 끝났다면, 피봇값을 현재 위치에 입력한다
    //이제 피봇을 기준으로 왼쪽에는 피봇보다 작거나 같은 값만 남았다
    data[left] = pivot;
    pivot = left;
    left = l_hold;
    right = r_hold;

    //재귀 호출을 수행
    if (left < pivot) Quick_Recursive(data, left, pivot - 1);
    if (right > pivot) Quick_Recursive(data, pivot + 1, right);
}

void Quick_Sort(int data[], int array_size){
    Quick_Recursive(data, 0, array_size - 1);
}

int main(){
    int array[7] = { 11, 45, 23, 81, 28, 34 };

    cout << "Before : ";
    for (int i = 0; i < 6; ++i) cout << array[i] << " ";
    cout << endl;

    Quick_Sort(array, 6);

    cout << "After : ";
    for (int i = 0; i < 6; ++i) cout << array[i] << " ";
    cout << endl;
    return 0;
}

You may also like...