[자료구조와 함께 배우는 알고리즘 입문] 6. 정렬 알고리즘(3)

6. 퀵 정렬

 

6-1. 퀵 정렬 살펴보기

퀵 정렬 알고리즘은 말 그대로 아주 빠른 정렬 알고리즘이다.

퀵 정렬은 배열 내에서 그룹을 나누는 기준인 '피벗'을 임의로 설정해서 피벗을 기준으로 그룹 내 정렬을 진행하고 또 각 그룹에 대해 피벗 설정, 그룹 나누기를 반복해 모든 그룹의 데이터가 1개가 되면 정렬을 마치게 된다.

 

6-2. 퀵 정렬 구현하기

퀵 정렬은 분할 정복 알고리즘에 해당되기 때문에 재귀를 이용하면 간단하게 구할 수 있다.

static void swap(int[] arr, int idx1, int idx2){
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
        
    }
    static void quickSort(int[] arr, int left, int right){
        int pl = left;
        int pr = right;
        int pivot = arr[(pl+pr) / 2];
        
        do {
            while (arr[pl] < pivot){
                pl++;
            }
            while (arr[pr]> pivot){
                pr--;
            }
            
            if(pl<=pr){
                swap(arr,pl++,pr--);
            }
        }while (pl<=pr);
        
        if(left<pr){
            quickSort(arr,left,pr);
        }
        if(pl<right){
            quickSort(arr,pl,right);
        }
    }

 

 

6-3. 시간 복잡도

퀵 정렬은 배열을 피벗을 기준으로 나눠 작은 문제를 해결하는 과정을 반복하기 때문에 O(n log n)이다.

배열의 초깃값이나 피벗 선택 방법에 따라 시간복잡도가 증가하게 되는 경우도 생기는데, 매번 단 하나의 데이터와 나머지 데이터로 나누면 시간복잡도는 O(n*n)이 된다.