[알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때

https://jjunsu.tistory.com/187

[알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때

https://jjunsu.tistory.com/188

[알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때

pivot을 중앙값, 첫 값으로 잡았을 때는 위에서 보았다.

이제 pivot이 맨 오른쪽에 있을 때를 알아보도록 하자.

 

퀵 정렬 - 마지막 피벗

중앙, 첫번째 피벗을 할 때도 배열을 예로 들어보자.

마지막 원소인 7을 피벗으로 잡을 것이다.

left는 첫번째 위치, right는 end-1로 한다.

 

arr[left]이 arr[pivot]보다 큰 값이 나올 때까지 left를 증가시켜주고,

arr[right]가 arr[pivot]보다 작은 값이 나올 때까지 right를 감소시킨다.

따라서 left, right는 다음과 같은 위치에 있을 것이다.

피벗을 마지막으로 잡았을 때 swap을 어떻게 할지 그려보니

left > right일 때 swap(arr, left, pivot)

left < right일 때 swap(arr, left, right)를 하게 되었다.

 

현재 left가 right보다 오른쪽에 있으므로 swap(arr, left, pivot)을 해주는데,

left와 pivot 둘 다 7에 위치하므로 배열은 바뀌지 않는다.

 

또한 left가 right보다 커졌으므로 재귀를 통한 분할을 해줄 것이다.

quickSort(arr, start, left - 1);
quickSort(arr, left + 1, end);

따라서 다음과 같은 배열 형태가 될 것이다.

오른쪽 배열은 길이가 1이라 start와 end가 같으므로 저대로 놔두면 된다.

왼쪽 배열을 다시 한번 위와 같은 과정을 거쳐보자.

 

left와 right를 조건에 맞게 옮겨보면 다음과 같이 된다.

left가 right보다 왼쪽에 있다.

따라서 swap(arr, left, right)를 해준다.

또 다시 left, right를 움직여보자.

right < left이므로 swap(arr, left, pivot)을 해준 후 재귀를 통해 분할을 해준다.

이제 언제 어떠한 과정을 거쳐야 할지 알거라 생각하고 남은 모든 과정을 한번에 올리겠다.

결론적으로 오름차순 정렬이 이루어진다.

코드를 보면 좀 더 이해하는데 도움이 될 것이다.

퀵 정렬 - 마지막 피벗

public class quickSortRightPivot {
    public static void main(String[] args) {
        int[] arr = {5, 1, 6, 4, 3, 2, 7};
        System.out.println("정렬 전: ");
        for(int i=0; i<arr.length; i++) System.out.print(arr[i] + " ");
        System.out.println();
        quickSort(arr, 0, arr.length-1);
        System.out.println("정렬 후: ");
        for(int i=0; i<arr.length; i++) System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void quickSort(int[] arr, int start, int end) {
        if(start > end) return;
        int pivot = end;
        int left = start;
        int right = end - 1;
        while(left <= right) {
            while(left < end && arr[left] < arr[pivot]) left++;
            while(right >= start && arr[right] > arr[pivot]) right--;
            if(left > right) swap(arr, left, pivot);
            else swap(arr, left, right);
        }
        quickSort(arr, start, left-1);
        quickSort(arr, left + 1, end);
    }
    public static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}