[자료구조] 정렬 #5 - 퀵정렬(Quick Sort)

퀵정렬이란?

: devide and conquer 알고리즘 중 하나

- 평균적으로 매우 빠른 속도

 

- devide : pivot 중심으로 균등하게 분할

- conquer : 부분배열을 정렬

- combine : 정렬된 부분 배열들을 합병

 

시간복잡도

Best: 나누어지는 부분의 배열의 크기가 n/2인 경우 O(nlogn)

Worst: 이미 정렬되어있는 경우(리스트가 불균형하게 나누어지기 때문) O(n^2)

 

구현 (오름차순)

void parition(int a[], int left, int right){
	int pivot = a[left];
    int i = left+1;
    int j = right;
    
    while(i<j){
    	while(pivot < a[j])
        	j--;
        while(pivot > a[i] && i<j)
        	i++;
        swap(a,i,j);
    }
    a[left] = a[i];
    a[i] = pivot;
    return i;
}

void quickSort(int a[], int left, int right) {
    if(left < right){
    	int pivotPos = partition(a, left, right); //분할(devide)
        quickSort(a, left, pivotPos-1);
        quickSort(a, pivotPos+1, right);
    }
}

 

출처

gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html