[ Algorithm ] Quick Sort(퀵 정렬)

Quick Sort#

퀵정렬은 실무에서 가장 널리 사용되는 정렬 알고리즘으로, 일반적이고 범용적인 상황에서 가장 빠른 성능을 보여준다. 이는 진정한 분할 정복 알고리즘의 대표적인 예시로, decrease-and-conquer와는 달리 모든 요소를 방문하는 특징이 있으며, 복잡도에 log가 포함된다는 점에서 이를 확인할 수 있다.¹

작동 원리#

퀵정렬의 핵심 원리는 피벗(pivot)이라 불리는 기준값을 선택하여 목록을 두 개의 하위 목록으로 나누는 것이다. 이때 나누는 기준은 피벗값보다 작은 요소들과 큰 요소들로 구분하는 것이며, 이 과정을 재귀적으로 반복한다. 재귀가 깊어질 때마다 새로운 피벗값을 선택하게 되는데, 피벗과의 교환이 균일하지 않게 이루어지고 인덱스도 고려해야 하므로 다소 복잡하게 느껴질 수 있다.

시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)#

평균 수행 시간: $O(NlogN)$
최악 수행 시간: $O(N^2)$
메모리(공간 복잡도): $O(logN)$
안정성: X

성능 면에서 퀵정렬은 평균적으로 $O(NlogN)$ 의 시간 복잡도를 보이지만, 최악의 경우 $O(N²)$ 까지 성능이 저하될 수 있습니다. 공간 복잡도는 $O(logN)$ 을 요구하며, 안정성을 보장하지 않는다는 특징이 있다.

코드#

구현한다면 아래와 같이 구현될 수 있고, 코드는 내 레포에 있다.

public class QuickSort implements Sort {  
    @Override  
    public int[] sort(int[] array) {  
        quickSort(array, 0, array.length - 1);  
        return array;  
    }  
  
    private void quickSort(int[] arr, int left, int right) {  
        if (left < right) {  
            int pi = partition(arr, left, right);  
            quickSort(arr, left, pi - 1);  
            quickSort(arr, pi + 1, right);  
        }  
    }  
  
    private int partition(int[] arr, int left, int right) {  
        int pivot = arr[right];  
        int i = (left - 1);  
  
        for (int j = left; j < right; j++) {  
            if (arr[j] <= pivot) {  
                i++;  
                swap(arr, i, j);  
            }  
        }  
        swap(arr, i + 1, right);  
        return i + 1;  
    }  
  
    private void swap(int[] arr, int i, int j) {  
        int temp = arr[i];  
        arr[i] = arr[j];  
        arr[j] = temp;  
    }  
}