[알고리즘] 퀵 정렬 (Quick Sort)

퀵 정렬 (Quick Sort)

• 분할 정복(Divide and Conquer) 방식을 사용하여 정렬을 수행하는 알고리즘
• 임의의 값(pivot)을 선택하고 피벗을 기준으로 배열을 분할한다.
• 분할된 부분 배열은 피벗을 기준으로 작은 값들과 큰 값들로 구분되며 각 부분 배열에 대해 동일한 과정을 반복하여 재귀적으로 정렬을 수행한다.
  • 왼쪽/오른쪽/중앙을 고른다.
  • 최솟값 또는 최댓값을 기준 값으로 정하지 않기 위해서 3개의 값을 임의로 정해서 그 중 중앙값을 고른다.
    
    
• 시간복잡도 : 기준 값이 최솟값 또는 최댓값으로 지정되는 경우는 O(n^2) 이지만 평균적으로는 O(nlogn) 이다.
• 공간복잡도 : O(nlogn)

장점

• 속도가 빠르다.
  • 평균적으로 O(nlogn)의 시간 복잡도를 가지며, 다른 일반적인 정렬 알고리즘들과 비교했을 때 빠른 속도를 보인다.
    
    
• 추가 메모리 공간을 필요로 하지 않는다.
  • 퀵 정렬은 주어진 배열 안에서 정렬을 수행하므로, 별도의 추가적인 메모리 공간이 필요하지 않다.

단점

• 불안정한 정렬이다.
  • 동일한 값에 대해 상대적인 순서가 보장되지 않을 수 있다.
    
    
• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 피벗 선택에 따른 성능에 영향을 받는다.
  • 퀵 정렬의 성능은 피벗 선택에 크게 의존한다. 따라서 피벗을 무작위로 선택하거나 3개의 값을 임의로 정해서 그 중 중앙값을 고르는 방식을 사용하여 이러한 문제를 완화할 수 있다.

퀵 정렬 구현

  public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // 피벗을 기준으로 분할하여 피벗의 인덱스를 얻는다.
            int pivotIndex = partition(array, low, high);
            
            // 피벗을 기준으로 왼쪽 부분 배열을 재귀적으로 정렬한다.
            quickSort(array, low, pivotIndex - 1);
            
            // 피벗을 기준으로 오른쪽 부분 배열을 재귀적으로 정렬한다.
            quickSort(array, pivotIndex + 1, high);
        }
    }
    
    public static int partition(int[] array, int low, int high) {
        // 피벗을 마지막 원소로 선택한다.
        int pivot = array[high];
        
        // 피벗보다 작은 값들을 피벗의 왼쪽으로 이동시킨다.
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        
        // 피벗을 올바른 위치로 이동시킨다.
        swap(array, i + 1, high);
        
        // 피벗의 최종 인덱스를 반환한다.
        return i + 1;
    }
    
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }