Chap3-2 퀵정렬(QuickSort)

3.2 퀵정렬

퀵 정렬은 분할 정복 알고리즘으로 분류하지만 분할할 수 없을 때까지 분할 후 합병이 아닌 분할 정복, 분할 정보의 과정을 반복하는 알고리즘

• 2개의 부분 문제로 분할, 각 부분 문제의 크기가 일정하지 않음(비균등 분할)
• -a = 2이고 b의 값은 정해지지 않음

 

퀵정렬 알고리즘의 아이디어

  순환의 방법으로 과정이 수행된다.

1. 배열의 원소 중 하나를 “피봇”이라는 이름으로 선정
2. 피봇이 위치한 곳을 기준으로 작은 것은 피봇의 왼편으로 큰 것을 피봇의 오른편으로 보낸다.
3. 피봇을 제외한 왼쪽 부분에서 새로운 피봇을 정하여 이 과정을 반복
4. 왼쪽 부분에서 더 이상 정렬할 것이 없다면 오른쪽 부분에서 새로운 피봇을 찾아 이 과정을 반복한다.

 

피봇

피봇을 기준으로 오른쪽 왼쪽이 다 정렬되면 피봇의 자리는 고정된다

    → 그렇기 때문에 분할-정복-분할-정복..의 과정이 반복되는 것이다.

즉, 피봇은 분할된 왼편이나 오른편 부분에 포함되지 않음

 

[의사코드]

QuickSort(A, left, right)
입력 : 배열 A[left] ~ A[right]
출력 : 정렬된 배열 A[left] ~ A[right]

1. if (left < right)
2. 피봇을 A[left} ~ A[right] 에서 선택// 선택하는 방법은 여러 가지 -> 제일 왼쪽, 
   1) 피봇값과 제일 왼쪽에 있는 값(A[left])을 swap한다. 
   2) 피봇값과 각각의 배열을 비교해서 
   피봇보다 작은 값 -> A[left] ~ A[p-1]으로 옮김(피봇보다 왼쪽에)
   피봇보다 큰 값 -> A[p+1] ~ A[right] < 서로 swap한다>
   피봇은 A[p]에 놓기 
3. QuickSort(A, left, p-1)
4. QuickSort(A, p+1, right)

 

수행과정

1. 피봇 선정
2. 맨 앞과 피봇과 자리 swap
3. 화살표 2개 준비(피봇보다 작은 것만 가리키는 것, 피봇보다 큰 것만 가리키는 것)
4. 작은 화살표는 제일 왼쪽을 , 큰 화살표는 전체 배열 보다 하나 큰 값으로 시작한다
5. 하나씩 화살표의 성격(피봇보다 작다, 피봇보다 크다)를 만족할 때까지 이동
6. 화살표의 성격에 맞지 않다면(피봇보다 작은 것만 가리켜야 하는데 피봇 보다 큰 것을 만나게 된다면 멈춘다. 반대의 화살표도 마찬가지로 진행)
7. 서로 멈추는 시점이 오면 서로의 값을 swap한다.
8. 이 과정은 작은 화살표와 큰 화살표의 위치가 서로 바뀌게 되면 정렬이 완료된 것이므로 멈춘다.
9. 그리고 원래 피봇이 있던 자리로 이동한다. (그 자리에 있던 값과 swap)

 

 

시간 복잡도

• 최악 = 전체 데이터에서 항상 가장 작은 것이 피봇으로 선택되는 경우시간복잡도 = (n-1) + (n-2) + (n-3) + (n-4) ... + 2 + 1 =n(n-1) / 2 = O(n^2)
• n-1번 비교해야 한다. n-2번 ....이다.

보통 최악의 경우를 고려하여 시간복잡도를 생각하지만 퀵 정렬은 그렇지 않는다

1. 최악의 경우가 발생할 경우 드물다
2. 랜덤하게 피봇을 선정한다면 최악의 경우가 나올 확률이 거의 없다. → 증명된 사실임

또한, 랜덤하게 피봇을 선정한다면 최선의 경우의 시간복잡도와 유사

 

최선 = 균등 분할
시간 복잡도 = O(n) * 층수 = O(n) * logn ⇒ O(nlogn)

 

 

피봇 선정 방법

  1) 랜덤하게 선정하는 방법

 

  2) Median of three   

     3개의 숫자의 중앙값으로 선정하는 방법 

     매번 피봇을 선택할 때마다 3개 중 중간값을 계산하여 피봇으로 선정

 

  3) Median of Medians

     전체 입력을 각각 3등분씩 나눈다.

     그리고 각각의 부분에서 Median값을 취한다. (가장 왼쪽, 가장 오른쪽, 중간 숫자 중 중간 숫자)

     다시 그 Median값들(중간 숫자들) 중에 가장 Median을 취한다.

     -> 매번 연산 과저잉 필요하기 때문에 경험적으로 랜덤한 방법을 선정하는 것이 좋음

 

성능 향상 방법

삽입정렬과 선택 정렬과 함께 사용하면 성능이 더 향상된다. 

예를 들어, 입력의 크기가 작아도 퀵정렬을 계속하게 되면 퀵정렬 자체가 문제를 작게 만들 때마다 계속 순환 호출을 하게 된다.

순환 호출은 메모리 스택에 쌓이고 호출하는 등의 부가적인 정보들이 쌓인다(메모리에서 나갔다가 들어왔다가 하는 것들)

 컴퓨터의 실행시간은 운영체제가 실행하는 시간과 CPU가 사용하는 시간이 있는데 실제 실행시간 이외에 다른 준비기간이 필요하다.

스케줄링, 메모리 입출력 등의 준비하는 시간들이 너무 많아지므로 입력이 작은 것에 대한 퀵정렬은 덜 효율적이다. 

 

 

장점

사이즈가 큰 입력에 대해서 성능이 가장 좋은 정렬 알고리즘이다.

 

퀵정렬의 소스코드

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 15
#define SWAP(x, y, t) ((t) = (x), (x) = (y), (y) = (t))

void makeList(int list[])
{
    for(int i = 0; i < SIZE; i++)
        list[i] =rand() % 100 + 1;
}

void printList(int list[])
{
    for(int i = 0; i < SIZE; i++)
        printf("%d ", list[i]);
    printf("\\n");    
}

int partition(int list[], int left, int right)
{
    int pivot, temp, low, high;
    
    pivot = list[left];
    low = left; high = right + 1;
    
    do
    {
        do
            low++;
        while (list[low] < pivot);
        
        do  
            high--;
        while (list[high] > pivot);
        
        /*
        for (int i = 0; i < SIZE; i++)	
			printf("%d ", list[i]);
		printf("\\nlow=%d, high=%d\\n", low, high);
        */
        
        if(low < high)
            SWAP(list[low], list[high], temp);
    
    } while (low < high);
    
    SWAP(list[left], list[high], temp);
    return high;
}

void quickSort(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 list[SIZE];
	srand(time(NULL));
    
    makeList(list);
    printList(list);
    
    quickSort(list, 0, SIZE - 1);
    printList(list);
}