Quick sort (퀵 정렬)

퀵 정렬

    - 분할 정복 알고리즘

    - 배열의 요소들을 Pivot이라는 요소와 비교하여 비균등하게 2개의 배열로 분할해서 정렬

 

 

 

동작

    - 정렬할 배열에서 첫 요소를 Pivot으로 선택

    - i는 i가 가리키는 요소가 Pivot보다 크거나 같을 때까지 그리고 배열의 오른쪽 끝일 때까지 이동

    - j는 j가 가리키는 요소가 Pivot보다 작거나 같을 때까지 그리고 배열의 왼쪽 끝+1일 때까지 이동

    - i와 j가 멈추면, 두 요소를 교환

    - i와 j가 엇갈릴 때까지 반복

    - i와 j가 엇갈리면, Pivot과 j를 요소를 교환하고 Pivot을 제외한 2개의 배열에서 위 과정 반복

        * Pivot이 j의 위치로 이동하고 2개의 배열이 생성

        * Pivot을 기준으로 왼쪽은 Pivot보다 작은 값들이 모임

        * Pivot을 기준으로 오른쪽은 Pivot보다 큰 값들이 모임

    - 나누어진 배열의 크기가 0 또는 1일 때까지 반복

 

    - 예시 : 전체 과정 예시

 

 

 

 

 

 

구현

    - 부분 배열의 첫 번째 요소를 Pivot으로 할 때

void quickSort(int list[], int left, int right) {
    
    // 부분 배열의 크기가 0 또는 1이면 멈춤  
    if(start >= end)
        return;
    
 
    int i = left + 1;
    int j = right;
    int pivot = left;
    int tmp;
    
    // 엇갈리지 않을 때까지 반복  
    while(i<=j){
        
        // 아래 조건에 맞을 때까지 i와 j를 이동  
        while(i<=right && list[i] <= list[pivot]) i++;
        while(j>left && list[j] >= list[pivot]) j--;
        
        // 이동 후, 엇갈렸다면, pivot과 교체  
        if(i > j){
            tmp = list[j];
            list[j] = list[pivot];
            list[pivot] = tmp;
            
        // 엇갈리지 않았다면, i와 j를 교환  
        } else {
            tmp = list[j];
            list[j] = list[i];
            list[i] = tmp;
        }
        
    }
    
    quickSort(list, left, j-1);
    quickSort(list, j+1, right);
}

 

    - 부분 배열의 가운데 있는 요소를 Pivot으로 할 때

void quickSort(int list[], int left, int right) {
    
      int i = left, j = right;
      int pivot = list[(left + right) / 2];
      int tmp;
      
      do {
        while (list[i] < pivot) i++;
        while (list[j] > pivot) j--;
        
        if (i<= j)
        {
            tmp = list[i];
            list[i] = list[j];
            list[j] = tmp;
            
            i++;
            j--;
        }
      } while (i <= j);
 
 
    // 왼쪽 부분 배열의 크기가 1 이상인 경우 
    if (left < j) quickSort(list, left, j);
    // 오른쪽 부분 배열의 크기가 1 이상인 경우  
    if (i < right) quickSort(list, i, right);
}
 

 

 

 

 

특징

    - 불안정 정렬

    - 같은 시간복잡도( O(N * logN) )을 갖는 정렬 알고리즘보다 일반적으로 빠름

    - 합병 정렬과 다르게 비균등하게 배열을 분할

 

    - Pivot을 선택하는 방법은 여러가지

        * 처음 값, 가운데 값

 

    - 시간 복잡도 : O(N * logN)

 

    - 최악의 경우, 시간복잡도 O(N^2)

        * 최악의 의미 : Pivot이 항상 맨 끝에 위치함, skewed tree

 

    - 퀵 정렬이 병합 정렬보다 빠른 이유

        + 퀵 정렬은 배열 복사를 할 필요가 없기 때문이다.

        + 퀵 정렬이 Locality를 더 잘 활용하기 때문이다. 아래의 그림을 보면서 설명하겠습니다. 정렬을 하기 위해서 cache에 정렬할 것들이 올라가야 합니다. 그런데 병합 정렬이 이루어질 때, cache에 올라가는 범위는 점점 커집니다. 이에 반해, 퀵 정렬은 제한된 범위 내에서 정렬이 이루어 집니다. 애니메이션을 보면, 병합 정렬의 범위는 점점 커지지만, 퀵 정렬은 제한된 범위 내에서만 움직입니다. 범위가 점점 커진다는 의미는 cache에 정렬할 데이터를 계속 바꾸어 주어야 한다는 것 입니다. 계속 바꿔주면 시간이 더 오래 걸립니다. 제한된 범위의 의미는 cache에 이미 올라가 있는 데이터에서 정렬을 수행하면 되기 때문에 데이터를 바꿔주는데 시간을 소비할 필요가 없습니다. 즉, cache hit가 높습니다.

 

병합 정렬

 

https://imgur.com/gallery/omL5k

퀵 정렬

https://imgur.com/gallery/omL5k

 

 

 

참조

    - 블로그 1

    - 블로그 2

    - 블로그 3

    - 블로그 4

    - 위키피디아

    - 정렬 알고리즘 시뮬레이터