퀵 정렬(Quick Sort)에 대해 알아보자

알고리즘 공부를 하면서 여러 정렬에 대한 이해가 필요한데, 그중에서도 퀵정렬에 대해 알아보고자 먼저 글을 정리해보았다.

1. 퀵 정렬(Quick Sort)의 이해

  - 퀵 정렬(Quick Sort)는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘입니다.

  - 퀵 정렬은 분할 정복(divide-and-conquer) 전략을 사용하는 재귀 알고리즘 입니다.

  - 퀵 정렬 단계

  ① 리스트의 여러 요소 중 하나의 *pivot을 골라 pivot보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 보내 분할합니다. 

       * pivot은 정렬의 기준값이 된다.

  ② 이후 분할된 리스트들을 재귀적으로 정복합니다.

  ③ 재귀적으로 정렬이 끝났다면 결합된 상태로 정렬되었습니다.

퀵 정렬(Quick Sort)

난수열에 대해 퀵 정렬을 실행한 그림.  수평선은 피벗 값을 가리킨다.
분류	정렬 알고리즘
자료 구조	배열
최악 시간복잡도	$$ O ( n 2 ) {\displaystyle O(n^{2})}
최선 시간복잡도	$$ O ( n log ⁡ n ) {\displaystyle O(n\log n)}
평균 시간복잡도	$$ O ( n log ⁡ n ) {\displaystyle O(n\log n)}

               (출처 : 위키백과 : 퀵정렬)

2. 퀵정렬의 특징

  - 병합 정렬(Merge Sort)과 분할 정복하는 전략에서는 비슷하지만, 병합 정렬은 결합단계에서 중요한 작업들이 이루어 지지만, 

    퀵 정렬(Quick Sort)는  분할단계에서 중요한 작업들이 이루어 집니다.

  - 병합 정렬과 비슷한 성능 (O(n log n)) 을 보이지만 빅오표기법에서 상수가 괜찮기 때문에 퀵 정렬을 조금 더 선호합니다.

  

3. 퀵정렬의 구현

#include <stdio.h>
 
int number = 10;
int data[] = {8,7,4,3,2,5,1,6,9,10};
 
void print() {
    for(int i=0; i<number; i++) {
        printf("%d", data[i]);
    }
} 
void quickSort(int* data, int start, int end) {
    // 원소가 1개인 경우 종료한다.
    if(start >= end) {
        return;
    }
    int pivot =start; // pivot은 첫번째 요소로 정한다. 
    
    int low=start+1; // pivot 다음 요소를 low값으로 설정한다. 
    int high=end; // 배열의 끝 요소를 high 값으로 설정한다. 
    int temp; // 데이터 교환 시 필요한 임시 저장 변수이다. 
    
    while(low<=high) { // 시작점과 끝점이 서로 엇갈릴 때 까지 반복하는 조건. 
    
        while(low<=end && data[low]<=data[pivot]) { // pivot 값보다 큰값을 만날때까지 low값을 증가시킨다. 
            low++;
        }
        while(high>start && data[high] >= data[pivot]) { // pivot 값보다 작은 값을 만날 떄 까지 high값을 감소시킨다. 
            high--;
        }
        if(low>high) { // 서로 엇가린다면 pivot 값과 data[high]값을 교체한다. 
            temp = data[high];
            data[high] = data[pivot];
            data[pivot] = temp;
        } else { // 엇갈리지 않는 상태라면 data[low]값과 data[high]값을 교체한다. 
            temp = data[low];
            data[low] = data[high];
            data[high] = temp;
        }
    }
    quickSort(data, start, high-1);
    quickSort(data, high+1, end);
}
 
int main(void) {
    quickSort(data, 0, number-1);
    print();
    return 0;
}

** 위키백과를 참조하였습니다.