[Algorithm] Quick Sort (퀵정렬)

1. Quick Sort (퀵정렬)

 

퀵 정렬은 병합 정렬과 같은 divide and conquer 기반의 알고리즘이다. 정렬시에 한 요소를 pivot으로 지정하고 pivot을 기준으로 배열을 두 부분으로 나눈다. 이때 pivot을 선택하는 방법은 여러가지가 있다.

• 첫번째 요소를 pivot으로 지정한다.
• 마지막 요소를 pivot으로 지정한다.
• 랜덤하게 pivot을 지정한다.
• 중간에 위치한 요소를 pivot으로 지정한다.

퀵 정렬은 정렬 알고리즘 중 가장 빠른 알고리즘으로 알려져 있지만, 배열의 정렬 상태와 pivot 선택 방법에 따라 worst case에 O(N^2)의 시간 복잡도를 가질 수 있다.

 

퀵 정렬의 핵심은 pivot을 중심으로 partition을 나누는 과정이다. pivot으로 지정된 요소의 값을 기준으로 작은 값은 왼쪽에 큰 값들은 오르쪽에 위치하도록 배열을 정렬한다. 이렇게 나뉘어진 왼쪽과 오른쪽의 partiton을 대상으로 정렬을 반복한다.

 

 

2. Quick Sort 구현

 

배열에서 하나의 원소를 pivot으로 정한다. pivot을 기준으로 작은 값은 배열에서 왼쪽, 큰 값들은 오른쪽으로 오도록 자리를 바꿔가면서 정렬한다. 정렬이 완료되면 pivot을 기준으로 왼쪽과 오른쪽으로 나뉘어지는데, 이렇게 나뉘어진 부분들을 대상으로 재귀적으로 정렬을 반복한다. 나뉘어진 배열의 크기가 0이거나 1이 될 때까지 반복한다.

 

- Java를 이용한 Quick Sort 구현

import java.util.Arrays;

import Algorithm.Sorting.Sort;

public class QuickSort implements Sort {

    private int[] array;

    public QuickSort(int[] array) {
        this.array = Arrays.copyOf(array, array.length);
    }

    @Override
    public int[] sort() {
        int N = array.length;
        quickSort(array, 0, N - 1);
        return array;
    }

    private void quickSort(int[] arr, int left, int right) {
        if(right <= left)
            return ;
        
        // pivot을 기준으로 partition을 진행한다.
        int pivot = partition(arr, left, right);
        
        // pivot의 위치를 기준으로 left, right에 대해서 재귀적으로 정렬을 반복한다.
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    private int partition(int[] arr, int left, int right) {
        // pivot으로 대상 구간의 가장 오른쪽 원소를 선택한다.
        int pivot = arr[right];

        // 대상 구간의 left, right 인덱스를 가지고 정렬을 진행한다.
        int l = left;
        for(int r = left; r < right; r++) {
            // pivot 보다 작은 값의 경우 left에 있는 값과 자리를 바꾼후 l을 한칸 오른쪽으로 옮긴다. (오름차순 기준)
            if(arr[r] < pivot) {
                int temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
                l++;
            }
        }

        int temp = arr[l];
        arr[l] = pivot;
        arr[right] = temp;
        return l;
    }
    
}

- source code: https://github.com/rmk1075/CS/blob/main/Algorithm/Sorting/QuickSort/QuickSort.java

 

 

3. Quick Sort 복잡도

- 시간 복잡도

• average case: O(N log N)
• worst case: O(N^2)
• worst case를 피하기 위해서 중위법을 사용하는 경우 평균적으로 정렬의 성능을 높일 수 있다.

- 공간 복잡도: O(log N)

 

 

[reference]

- https://www.geeksforgeeks.org/quick-sort/

- https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC