[JAVA] 8. 필수 알고리즘 Ⅺ. 퀵솔트

최재원

Feb 13, 2025

원리 및 등장 이유

원리:

분할 정복 알고리즘으로, 하나의 기준(피벗)을 선택하여 배열을 두 부분(피벗보다 작은 부분과 큰 부분)으로 나눕니다.
각 부분 배열에 대해 재귀적으로 정렬을 수행하여 전체 배열을 정렬합니다.

등장 이유:

평균적으로 O(n log n)의 시간 복잡도를 가지며, 효율성과 성능 때문에 대규모 데이터 정렬에 많이 사용됩니다.

원리 다이어그램


초기 배열: [5, 3, 8, 4, 2]
피벗 선택: 2 (혹은 마지막 원소 등 선택 기준에 따라 달라짐)

1. 분할 과정:
   [5, 3, 8, 4, 2]
         |         ← 피벗 2 기준
   작은 값들: []          // 2보다 작은 값 (없음)
   큰 값들: [5, 3, 8, 4]   // 2보다 큰 값

2. 재귀적으로 정렬:
   배열이 분할되어, 각 부분에 대해 동일한 과정을 반복
   예: [5, 3, 8, 4] 에서 피벗 선택 후 재분할


초기 배열:       [5, 3, 8, 4, 2]
pivot:           2 (arr[high])
i:               -1 시작

for 루프:
  j=0: arr[0]=5 > pivot, skip
  j=1: arr[1]=3 > pivot, skip
  j=2: arr[2]=8 > pivot, skip
  j=3: arr[3]=4 > pivot, skip

끝난 후:         i = -1
피벗 swap:       arr[0] <-> arr[4] → [2, 3, 8, 4, 5]
return 0 (pivot 위치)

참고: 실제 구현에서는 피벗 선택 방식이 다양하며, 위 다이어그램은 기본 개념 이해를 위한 단순화된 예입니다.

자바코드 예시


public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // 마지막 원소를 피벗으로 선택
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // arr[i]와 arr[j] 교환
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 피벗을 올바른 위치로 이동
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }
    
    public static void main(String[] args) {
        int[] data = {5, 3, 8, 4, 2};
        quickSort(data, 0, data.length - 1);
        for (int num : data) {
            System.out.print(num + " ");
        }
    }
}

See more posts

[JAVA] 8. 필수 알고리즘 Ⅺ. 퀵솔트

원리 및 등장 이유

원리 다이어그램

More articles

[JAVA] 10. 클래스와 객체 Ⅰ. Circle 클래스

[JAVA] 9. 최종테스트(로또)

[JAVA] 8. 필수 알고리즘 Ⅹ. 버블정렬

[JAVA] 8. 필수 알고리즘 Ⅸ. 피보나치 수열