퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

개념

• 퀵 정렬은 분할 정복 방법을 통해 주어진 배열을 정렬한다.
  • 분할 정복(Divide and Conquer) : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
• 또한, Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.

로직

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소는 피벗(pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide)이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할 된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

• 분할(Divide) : 주어진 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다.(피벗을 중식으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들)
• 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 방법을 적용한다.

 private static void quickSort(int[] arr, int left, int right) {
        int L = left;
        int R = right;
        int pivot = arr[(left + right) / 2];
   			// 피벗을 배열의 가운데 위치한 요소로 설정.

        while (L <= R) {
          	// 피벗 왼쪽에는 피벗보다 작은 원소들이 위치해야 하고, 큰 원소가 있다면 반복문을 나온다.
            while (arr[L] < pivot) L++;
			
          	// 피벗 오른쪽에는 피벗보다 큰 원소들이 위치해야 하고, 작은 원소가 있다면 반복문을 나온다.
            while (pivot < arr[R]) R--;

          	// L과 R이 역전되지 않고, 같은 경우가 아니라면 두 원소의 위치를 교환한다.
          	// 이를 통해서 피벗 기준으로 왼쪽에는 작은 원소가, 오른쪽에는 큰 원소가 위치하게 된다.
            if (L <= R) {
                if (L != R) {
                    swap(arr, L, R);
                }
                L++;
                R--;
            }
        }

   	// L과 R이 역전된 후에 피벗의 왼쪽과 오른쪽에는 정렬되지 않은 부분 배열이 남아있을 수 있다.
   	// 이 경우, 남아 있는 부분 배열에 대해서 퀵 정렬을 수행한다.
        if (left < R) quickSort(arr, left, R);

        if (L < right) quickSort(arr, L, right);
    }

    // 입력 받은 원소의 자리를 교환해준다.
    private static void swap(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }

Qucik Sort 개선

위의 코드에서는 피벗을 배열의 가운데 원소로 지정함으로써 어느 정도 성능을 개선한 형태이다.

하지만, 피벗 값이 최소나 최대값으로 지정되면 피벗을 기준으로 원소들이 들어갈 값을 찾는데 오래 걸린다. O(N^2)의 시간 복잡도를 갖는다.

즉, 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있으면 O(N^2)의 시간복잡도를 가진다. 이때, 배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간 복잡도 O(N logN)으로 개선할 수 있다.

하지만, 이 방법으로 개선한다 하더라도 Quick Sort의 최악의 시간 복잡도가 O(N logN)이 되는 것은 아니다.

시간 복잡도

최선의 경우 : T(N) = O(N logN)

• 비교 횟수 : logN

레코드의 개수 N이 2의 거듭제곱이라고 가정했을 때(N = 2^k), N = 2^3의 경우

2^3 -> 2^2 -> 2^1 -> 2^0 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다.

이것을 일반화하면 N = 2^k의 경우, k = logN임을 알 수 있다.

[각 순환 호출 단계의 비교 연산] (N)

각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 N번 정도의 비교가 이루어진다.

따라서, 최선의 시간 복잡도는 순환 호출의 깊이(logn) x 각 순환 호출 단계의 비교 연산(n) = n logn이 된다.

이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

최악의 경우 : T(N) = O(N^2)

최악의 경우는 정렬하고자 하는 배열이 오름차순 혹은 내림차순 정렬되어 있는 경우이다.

• 비교 횟수 : (N)

레코드의 개수 N이 2의 거듭제곱이라고 가정했을 때(N = 2^k), 순환 호출의 깊이는 N임을 알 수 있다.

• 각 순환 호출 단계의 비교 연산

각 순환 호출에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 N번 정도의 비교가 이루어진다.

따라서 최악의 시간 복잡도는 순환 호출의 깊이 x 각 순환 호출 단계의 비교 연산 = N^2 이다.

이동횟수는 비교 횟수보다 적으므로 무시할 수 있다.

공간 복잡도

주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

장점

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

단점

• 불안정 정렬이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행 시간이 더 많이 걸린다.

결론

Quick Sort는 평균적으로 가장 빠른 정렬 알고리즘이다.

Java에서는 Arrays.sort()가 내부적으로 Dual Pivot Quick Sort로 구현되어 있을 정도로 효율적인 알고리즘이다.

또한, 기술 면접에서 빈번하게 나오므로 반드시 숙지해야 한다.

참고

• 퀵 정렬 (Quick Sort)