[JAVA] 퀵정렬 알고리즘 구현하기

퀵정렬
기준값 아무거나 잡는다 (Pivot)

이 Pivot을 기준으로 왼쪽엔 작은값 오른쪽에 큰값을 배치한다
다시 Pivot을 정하고 이 과정을 반복한다.

최선은 NlogN
최악은 N^2

반복 작업을 할 때 매번 값을 반씩 나누어 줄이면 NlogN이 된다
하지만 퀵정렬의 경우 기준값을 매번 최소값을 결정하게 되면 매번 최대치만큼 반복하므로 N^2이 된다

 

이미지 출처 : https://www.youtube.com/watch?v=7BDzle2n47c

과

Start와 End를 정하고
start는 pivot보다 작은값을 무시하며 전진하고
end는 pivot보다 큰값을 무시하며 전진한다

start가 pivot보다 크거나 같은값을 만나면 해당위치에서 멈추고
end가 pivot보다 작거나 같은값을 만나면 해당위치에서 멈춘다
둘이 값을 교환한 후 start와 end를 한칸씩 전진시킨다

해당과정을 start와 end가 교차(start>=end)가 되면 멈춘다
현재 정렬 중인 배열의 크기가 0또는 1이 아니면 작은쪽과 큰쪽을 나누어 같은 과정을 반복한다
이과정을 partition이라고 한다

자바 코드

public class Main {
    public static void main(String[] args) {
        int[] arr = {3, 1, 6, 2, 4, 7, 11, 68, 5};
        
        //정렬 전 배열
        for (int a : arr) {
            System.out.print(a + ",");
        }
        System.out.println();
        
        //정렬
        sort(arr);
        
        // 정렬 후 배열
        for (int a : arr) {
            System.out.print(a + ",");
        }
    }

    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    public static void quickSort(int[] arr, int start, int end) {
        // 파티션을 나누고 오른쪽 파티션의 첫번째 자리
        // 즉 한번 정렬하고 start와 end가 교차된 후 start의 자리
        int part2start = partition(arr, start, end);
        //오른쪽 파티션의 시작점과 왼쪽파티션 크기를 비교하여 왼쪽파티션 크기가 2이상일때 다시 정렬
        if (start < part2start - 1) quickSort(arr, start, part2start - 1);
        // 오른쪽 파티션의 시작점과 배열의 끝의 크기가 1을 초과할 때 오른쪽도 정렬 
        if (end > part2start) quickSort(arr, part2start, end);
    }
    // 파티션 나누는 메서드
    public static int partition(int[] arr, int start, int end) {
        // 피벗은 배열의 중간으로 임의지정
        int pivot = arr[(start + end) / 2];
        
        // start와 end가 교차하기 전에는 계속 반복
        while (start <= end) {
            // arr의 start값이 pivot보다 큰값이 발견될 때까지 반복
            while (arr[start] < pivot) start++;
            // arr의 end 값이 pivot보다 작은 값이 발견될 때까지 반복
            while (arr[end] > pivot) end--;
            // 반복을 끝내고 start와 end가 교차했는지 확인
            if (start <= end) {
                //교차하지 않았으면 서로 자리를 바꾸고 start와 end를 한칸씩 전진
                swap(arr, start, end);
                start++;
                end--;
            }
        }
        // 교차를 했다면 start가 오른쪽 파티션의 시작점이 되니 start를 반환
        return start;
    }
    // 자리바꾸는 메서드
    public static void swap(int[] i, int start, int end) {
        int temp = i[start];
        i[start] = i[end];
        i[end] = temp;
    }
}