[정렬 #3] 퀵 정렬(Quick Sort) w.Java

퀵 정렬은 pivot을 기준으로 partitioning을 하여 다른 원소와의 비교를 통해 정렬을 수행하는 비교 정렬에 속하는 정렬이다.

1. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 pivot이라고 한다.

2. pivot 앞에는 pivot 보다 값이 작은 모든 원소들이 오고, pivot 뒤에는 pivot 보다 값이 큰 모든 원소들이 오도록 pivot을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 pivot은 더이상 움직이지 않는다.

3. 분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.

 

특징 및 장점

• 분할 정복 알고리즘이다.
• 비교 정렬이다. 
• in place 정렬이다. 
• 잘 구현되면(nlogn), merge sort 보다 빠르다. 

 

단점

• 불안정 정렬이다. (경우에 따라 시간 복잡도가 크게 차이남)
• 최악의 경우 n2의 시간이 걸린다. 
• pivot에 따라 성능차이가 심하다. 

 

Java로 구현

public void quickSort(int[] arr, int left, int right){
	int i, j, pivot, tmp = 0;
    
    if(left < right){
    	i = left;
        j = right;
        
        // 1. divide
        while(i < j){
            while(arr[j] > pivot) j--;
            while((i < j) && (arr[i] < pivot)) i++;
            
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        
        // 2. sort
        quickSort(arr, left, i-1);
        quickSort(arr, i+1, right);
    }
}

 

시간 복잡도

최악: n^2 -> pivot이 partition 내에서 가장 크거나 가장 작은 값이 되는 경우

평균: nlogn

최선: nlogn

 

Reference

https://ko.wikipedia.org/wiki/퀵_정렬

https://coding-factory.tistory.com/615