퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

퀵 정렬 이란?

• 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다
• 불안정 정렬 이다
• 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다

---

Process

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다
   • 피벗을 고르는 방법은 여러가지가 있지만,이 글에서는 맨 오른쪽 원소를 피벗으로 잡는다
   • 피벗을 어떻게 고르느냐에 따라 속도 차이가 많이 난다
2. 피벗보다 작은 원소는 모두 왼쪽, 큰 원소는 모두 오른쪽으로 오게하고, 배열을 분할한다
3. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다
4. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다
   • 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다

---

Java Code

public class Main {

    public static void main(String[] args) {
        int[] arr = {43, 51, 76, 60, 73, 82, 36, 98,10,23,1,100};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr, int l, int r){
        if(l < r){
            int p = partition(arr, l, r); // 분할

            quickSort(arr, l, p-1);
            quickSort(arr, p+1, r);
        }
    }

    public static int partition(int[] arr, int l, int r){

        int pivot = arr[r];
        int i = (l-1); // i는 pivot보다 작은 원소의 개수이다

        for(int j=l;j<=r-1;j++){
            if(arr[j] <= pivot){
                i++;
                swap(arr, i, j); // pivot보다 작은 원소를 왼쪽으로 이동
            }
        }

        swap(arr,i+1, r); // pivot 위치 교환
        return (i+1); 
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

---

Quick Sort GIF

---

시간복잡도

평균적인 경우 : O(nlog₂n)

• 비교 횟수 : O(log₂n)
• 재귀적으로 호출 하므로 재귀 호출의 깊이는 O(log₂n)
• 각 재귀 호출 단계의 비교 연산 : O(n)
• 따라서 시간복잡도는 재귀 호출의 깊이 * 각 재귀 호출 단계의 비교 연산 = O(nlog₂n)

최악의 경우 : O(n^2)

언제인가?

• 피벗을 항상 최댓값 또는 최솟값으로만 잡는 경우
• 정렬하고자 하는 배열이 이미 정렬 되어 있는 경우

  계산

• 비교 횟수 : O(N)
• 각 재귀 호출 단계의 비교 연산 : O(n)
• 따라서 시간복잡도는 재귀 호출의 깊이 * 각 재귀 호출 단계의 비교 연산 = O(n^2)

---

장점

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다

단점

• 불안정 정렬(Unstable sort)이다
  • 불안정 정렬 : 입력한 순서가 보장 되지 않는 정렬
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히여 수행시간이 더 많이 걸린다

---

참고

• 퀵 정렬