[정렬]Quick Sort

퀵 정렬(Quick Sort)

pivot을 기준으로 두 구역을 분리하면서 (왼쪽은 pivot보다 작은 값, 오른쪽은 pivot보다 큰 값) 정렬하는 unstable한 정렬 기법

시간복잡도

O(nlogn)

pivot 위치, 정렬 상태에 따라 시간복잡도의 차이가 큼

예시 코드

다음 예시는 pivot이 자료의 중앙에 위치시킨 예시

#include <cstdio>

void quickSort(int* arr, int start, int end){
    if(end - start < 2)	   return;
    
    int pivot = (start + end) / 2;
    int temp = arr[pivot];
    arr[pivot] = arr[start];
    arr[start] = temp;
    
    pivot = start;
    for(int i = start + 1; i < end; i++){
    	if(arr[start] > arr[i]){
            temp = arr[++pivot];
            arr[pivot] = arr[i];
            arr[i] = temp;
        }
    }
    temp = arr[start];
    arr[start] = arr[pivot];
    arr[pivot] = temp;
    
    quickSort(arr, start, pivot);
    quickSort(arr, pivot + 1, end);
}

int main(){
    int arr[10] = {5, 26, 4, 1, 3, 12, -8, 9, 11, 44};
    
    quickSort(arr, 0, 10);
    
    return 0;
}