241209 TIL - 퀵 정렬 (Quick Sort)

J_log·2024년 12월 9일
0

퀵정렬은 분활 정복 알고리즘을 기반으로 하는 정렬 알고리즘으로, 효율성과 간결함 때문에 자주 사용된다. 평균적으로 O(nlogn) 의 시간 복잡도를 가지며, 최악의 경우 O(N²)이 될 수 있지만 적절한 피벗 선택으로 최악의 경우를 피할 수 있다.


작동 원리

  1. 피벗 선택
    배열에서 하나의 원소를 피벗으로 선택한다. (일반적으로 첫 번째 원소, 마지막 원소, 혹은 중간 값 등 다양한 방식으로 선택 가능)
  2. 분할 (Partition)
    피벗을 기준으로, 배열을 두 그룹으로 나눈다. (피벗보다 작은 원소들, 피벗보다 큰 원소들)
  3. 재귀 호출
    분할된 두 그룹에 대해 동일한 과정을 재귀적으로 수행한다.
  4. 정렬 완료
    재귀 호출이 끝나면, 모든 원소가 정렬된 배열로 합쳐진다.

예시 코드

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;
    }

특징

  • 장점
    • 평균적으로 매우 빠르다. (O(nlogn))
    • 추가 메모리 사용이 적어 공간 효율적이다.
  • 단점
    • 피벗 선택에 따라 최악의 경우 성능이 저하될 수 있다. (O(N²))

0개의 댓글