Quick Sort

조상원·2025년 8월 2일

목록 보기

6/11

Divide&Conquer
- 리스트를 피벗을 중심으로 2개의 부분 리스트로 비균등 분할
- 각각의 부분 리스트를 다시 퀵정렬(재귀호출)
- 피벗은 보통 첫번째 데이터 이용하나 정해진건 아님
평균적으로 가장 빠른 방법

각 부분리스트에서 피벗을 선택

public static void quickSort(int[] numbers, int left, int right) {
        //분할할 부분이 남아 있는 경우
        if(left<right){
            //pivot을 기준으로 배열을 분할하고 pivot의 위치를 반환
            int pivotIndex = partition(numbers, left, right);

            //pivot을 기준으로 왼쪽 부분 배열 정렬
            quickSort(numbers, left, pivotIndex-1);

            //pivot을 기준으로 오른쪽 부분 배열 정렬
            quickSort(numbers, pivotIndex+1, right);
        }
    }

private static int partition(int[] numbers, int left, int right) {
        //배열의 마지막 요소를 피벗으로 지정
        int pivot =  numbers[right];

        //pivot보다 작은 값을 가지는 요소들의 시작 인덱스
        int i = left - 1;

        int temp;

        //배열을 탐색하면서 pivot보다 작은 요소를 왼쪽으로 이동시킨다
        for(int j = left; j < right; j++){
            if(numbers[j] < pivot){
                i++;

                temp = numbers[i];
                numbers[i] = numbers[j];
                numbers[j] = temp;
            }
        }

        //pivot을 올바른 위치로 이동
        temp = numbers[i+1];
        numbers[i+1] = numbers[right];
        numbers[right] = temp;

        //pivot의 최종 위치 반환
        return i+1;
    }