퀵 정렬(Quick Sorting)

  • 퀵 정렬이란 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법이다. 값을 서로 교체하는데에 N번, 엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로 평균적으로 NlogN의 시간복잡도를 가진다.

  • 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 가진다.

  • 편향된 분할이 발생할 때 연산이 N^2이 될 수 도 있다. (왼쪽으로 편항되어서 분할 되거나 그 반대의 경우) 따라서, 직접 구현하기 보다는 C++의 algorithm 라이브러리의 sort 함수를 사용한다.

  • 하나의 리스트를 피벗을 기준으로 비균등하게 분할 하고, 분할된 리스트를 정렬하고, 분할 된 리스트를 다시 합한다.

    • 분할 : 피벗을 기준으로 비균등하게 2개의 부분배열으로 분할
    • 정복 : 부분 배열을 정렬한 후 순활 호출을 이용해서 다시 분할 정복
    • 결합 : 정렬된 부분 배열들을 하나의 배열에 합병 시킨다.

퀵 정렬 구현방법

  1. 먼저 피벗값을 선정한다. 피벗값을 5로 선정한다.

image.png

  1. 피벗에서 오른쪽 방향으로 이동하면서 피벗값(5)보다 큰 값을 찾는다. 그리고 배열의 오른쪽에서부터 왼쪽으로 이동하면서 피벗값(5)보다 작은 값을 찾는다.

image.png

  1. 피벗보다 큰 값과, 피벗보다 작은 값을 swap 시킨다.

image.png

image.png

  1. 피벗에서 오른쪽 방향으로 이동하면서 피벗값(5)보다 큰 값을 찾는다. 그리고 배열의 오른쪽에서부터 왼쪽으로 이동하면서 피벗값(5)보다 작은 값을 찾는다.

image.png

  1. 피벗보다 큰 값과, 피벗보다 작은 값을 swap 시킨다.

image.png

  1. 피벗에서 오른쪽 방향으로 이동하면서 피벗값(5)보다 큰 값을 찾는다. 그리고 배열의 오른쪽에서부터 왼쪽으로 이동하면서 피벗값(5)보다 작은 값을 찾는다. (이 경우, 큰값과 작은값이 서로 엇갈리는 상황이 발생하였으므로 피벗값과 더 작은 값을 서로 교체한다.)

image.png

image.png

  1. 피벗값 5를 기준으로 왼쪽,오른쪽을 분할해서 양쪽값을 퀵정렬 수행한다. 각각의 부분 배열들이 정렬이 수행된다.

image.png

image.png

퀵 정렬 구현

#include<stdio.h>
#define SIZE 1000

int a[SIZE];

int swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void quickSort(int start, int end) {

    if(start >= end) return;
    int key = start, i = start + 1, j = end, temp;
    //엇갈릴때까지 반복 
    while(i <= j) {
        while(i <= end && a[i] <= a[key]) i++;
        while(j > start && a[j] >= a[key]) j--;
        if(i > j) swap(&a[key],&a[j]);
        else swap(&a[i],&a[j]);
    }
    quickSort(start,j-1);
    quickSort(j + 1,end);

}
int main(void) {
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    quickSort(0,n-1);
    for(int i = 0; i < n; i++) printf("%d",a[i]);
    return 0;

}