퀵 정렬(Quicksort) 알고리즘

분할 정복 Divide & Conquer

Quicksort 퀵 정렬

퀵 정렬은 병합 정렬처럼 분할 정복 알고리즘 기법으로 만들어진 정렬 방법입니다.

퀵 정렬에서는 pivot이라는 기준을 하나 정하고, 왼쪽은 기준보다 작은 값, 그리고 더 큰 값은 기준 오른쪽으로 옮기면서 배열을 둘로 분할한 후 정렬합니다. 보통 pivot은 맨 앞이나, 맨 뒤, 혹은 중간에 위치한 값을 선택합니다.

나뉘어진 하위 배열에 대해 재귀적으로 퀵 정렬을 호출하여, 모든 배열이 기본 배열(요소가 하나뿐인 배열)이 될 때까지 반복하면 정렬이 완료됩니다.

💡 퀵 정렬 과정

1) 배열 맨 앞에 있는 수를 pivot으로 설정한다. 그리고 배열의 길이가 n일 때, 배열의 시작점은 0이 되고 도착점은 n -1이 된다.
2) pivot 값을 기준으로 시작점에서부터 검사해서 큰 값을, 도착점에서부터 작은 값을 찾는다.
3) 두 값을 바꾸고, 같은 과정을 수행한다.
4) 큰 값의 index와 작은 값의 index가 교차하는 경우 ,작은 값과 pivot 값을 바꾼다. 이렇게 하면 pivot값을 기준으로 왼쪽은 pivot보다 작은 값들, 오른 쪽은 pivot보다 큰 값들로 분할된다.
5) 분할된 영역에서 맨 앞에 있는 수를 pivot으로 설정하고 같은 과정을 수행한다. 

퀵 정렬 gif를 통해 이해하기

퀵 정렬 시간 복잡도

퀵 정렬의 성능은 어떻게 pivot 값을 선택하느냐에 따라 크게 달라질 수 있습니다.

pivot 값을 기준으로 동일한 개수의 작은 값들과 큰 값들이 분할되면 **O(NlogN)**의 시간 복잡도를 가지게 됩니다.

하지만, pivot 값을 기준으로 분할했을 때 값들이 한 편으로 크게 치우치게 되면, 퀵 정렬의 성능은 저하되고,

한편으로만 모든 값이 몰리면 **O(N^2)**의 시간 복잡도를 가지게 됩니다.

추가로 이미 배열이 정렬되어 있고 pivot이 항상 그 배열의 최솟값 혹은 최댓값인 경우에는 최악의 시간 복잡도를 가집니다.

이때, 분할이 N만큼 진행되다 보니 최악의 시간 복잡도는**O(N^2)**이 됩니다.

퀵 정렬은 다른 정렬 알고리즘 보다 훨씬 더 효율적인 방법입니다.

퀵 정렬의 장단점

✅ 장점

• O(NlogN)의 시간 복잡도를 가지므로 다른 정렬 알고리즘보다 빠르다
• 정렬하고자 하는 배열 안에서 교환하는 방식(in-place)이므로, 다른 메모리 공간을 필요로 하지 않는다

✅ 단점

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

퀵 정렬 실습

import java.util.Arrays;

public class QuickSort {
    public void sort(int[] arr){
        // 비었거나 길이가 1 이하라면 정렬할 필요가 없다.
        if (arr == null || arr.length <= 1){
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }
    private void quickSort(int[] arr, int low, int high){
        if (low < high){
            // quicksort 후 나눠진 index를 반환받는다.
            int pivot = partition(arr, low, high);
            // 해당 index를 기준으로 좌우에 대하여 다시
            // quicksort를 호출한다.
            quickSort(arr, low, pivot - 1);
            quickSort(arr,pivot + 1, high);
        }
    }
    // pivot을 정하고, pivot을 기준으로 좌우 배열의 원소들을 교환한 뒤
    // pivot이 최종적으로 위치하는 곳을 반환하는 메소드
    private int partition(int[] arr, int low, int high){
        // 오른쪽 끝이 pivot
        int pivot = arr[high];
        // 작은원소가 들어갈 위치를 지정하는 i
        int i = low - 1;
        // j == low부터 j == high - 1까지 반복(pivot 제외 전부 대조)
        for (int j = low; j < high; j++) {
            // 현재 원소의 값이 pivot 보다 작은 경우
            if (arr[j] <= pivot){
                i++;
                // 왼쪽 끝으로 보낸다.
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 이 과정이 끝나면 arr[i]에는 pivot 보다 작은 원소가,
        // i + 1 ~ high - 1의 모든 원소는 pivot 보다 큰 원소가 담겨있다.
        // i + 1과 pivot의 위치를 교환하면, i + 1을 기준으로
        // 왼쪽은 pivot보다 작은 값이
        // 오른쪽은 pivot 보다 큰 값이 위치한다.
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        // 마지막으로 pivot에 위치를 반환한다.
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {9, 3, 1, 7, 4, 8, 6, 2, 5};
        new QuickSort().sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

출력 결과

[1, 2, 3, 4, 5, 6, 7, 8, 9]