퀵정렬(Quick Sort)

퀵정렬(Quick Sort)

개념

분할정복 방식으로 고안된 정렬방법으로 먼저 임의의 기준을 선택하여 그 기준보다 작은 값은 왼쪽에, 큰 값을 오른쪽에 위치시킨 후 다시 임의의 기준을 선택하여 왼쪽과 오른쪽을 반복하여 나누어 가며 정렬하는 방법

재귀호출을 사용

로직

1. 배열에서 임의의 원소 pivot을 선택한다.
2. 남아 있는 원소들은 pivot보다 큰 것과 작은 것의 두 가지로 구분된다.
3. 각 리스트는 다시 스스로를 정렬하는 메소드를 호출한다.

결론적으로 리스트는 pivot에 의해 작은 원소들과 큰 원소들로 정렬된다.

코드

QuickSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        quickSort(0, N - 1, arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void quickSort(int start, int end, int[] arr) {
        if (start >= end)
            return;

        int left = start + 1, right = end;
        int pivot = arr[start];

        while (left <= right) {
            while (left <= end && arr[left] <= pivot)
                left++;
            while (right > start && arr[right] >= pivot)
                right--;

            if (left <= right) {
                swap(arr, left, right);
            } else {
                swap(arr, start, right);
            }
        }
        quickSort(start, right - 1, arr);
        quickSort(right + 1, end, arr);
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

console

정렬 전: [34, 1, 6, 10, 42, 24, 0, 30, 10, 78]
정렬 후: [0, 1, 6, 10, 10, 24, 30, 34, 42, 78]

시간복잡도

원소들은 두 개의 리스트로 분리하는 시간 복잡도는 $O(N)$이고 각각의 재귀 호출은 각 리스트의 숫자의 절반의 횟수가 발생한다. 그래서 이 알고리즘의 시간 복잡도는 $O(NlogN)$이다. 이건 평균적인 성능이다.

최악의 경우에는 $O(N^2)$이다.

정렬하고자 하는 배열의 상태와 pivot을 결정하는 방법에 따라 재귀 호출의 횟수가 최대 $N$번이 발생할 수 있기 때문이다.

pivot을 선택하는 방법(난수 분할, 중위값 선택)에 따라 어느정도 개선은 가능하다.

장점

1. 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 $O(NlogN)$를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠릅니다.
2. 정렬을 위한 추가적인 메모리 공간을 필요로 하지 않는다.

단점

1. 불안정 정렬이다.
2. 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 $O(N^2)$의 시간복잡도를 갖는다.