퀵 정렬( Quick sort ) 알고리즘

퀵 정렬 알고리즘?

불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.

분할 정복 알고리즘 

병합 정렬( Merge sort )과는 다르게 리스트를 비 균등하게 분할한다.

 

정렬 절차

• 분할(Divide): 입력 배열을 피벗을 기준으로 비 균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
• 정복(Conquer): 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 병합한다.

기준값인 피벗(pivot) 과 high, low 인덱스로 비교 및 교환 진행한다.

루틴이 한번 돌때마다 피벗은 제 위치를 찾아나간다.

 

특징

장점

• 속도가 빠르다.
• 추가 메모리 공간이 불필요하다.

단점

• 정렬된 리스트의 경우 특성상(불균형 분할) 오히려 수행 시간이 더 많이 걸린다.

퀵 정렬의 불균형 분할을 방지하기 위한 피벗을 설정하자. how?

 

구현

public static void quickSort( int[] target ){
    quickSort(target,0,1, target.length - 1 );
}

public static void quickSort( int[] target, int pivotIndex, int lowIndex, int highIndex ){
    if( lowIndex > highIndex ){
        return;
    }

    int pivot = target[pivotIndex];
    int lowMax = lowIndex;
    int highMax = highIndex;
    while ( lowIndex < highIndex ){

        // LOW 는 피벗 보다 큰값이 나오면 멈춤
        while( lowIndex <= highMax && target[lowIndex] < pivot ){
            lowIndex++;
        }

        // HIGH 는 피벗 보다 작은 값이 나오면 멈춤
        while( highIndex >= lowMax && target[highIndex] > pivot ){
            highIndex--;
        }

        if( lowIndex < highIndex ){
            // LOW 와 HIGH 교환
            int tmp = target[lowIndex];
            target[lowIndex] = target[highIndex];
            target[highIndex] = tmp;
        }
    }

    // 피벗 과 HIGH 교환
    int tmp = target[pivotIndex];
    target[pivotIndex] = target[highIndex];
    target[highIndex] = tmp;

    // 재귀
    quickSort( target, lowMax - 1, lowMax,highIndex - 1 ); // 왼쪽 재귀
    quickSort( target, highIndex + 1, highIndex + 2, highMax ); // 오른쪽 재귀
}

 

시간 복잡도

최상, 평균 : nlogn

최악 : n^2

---

참고
https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog