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

https://jjunsu.tistory.com/187

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

퀵 정렬 왼쪽 피벗

저번에는 피벗을 중앙으로 잡았을 때를 알아봤었다.

이번에는 피벗을 맨 왼쪽으로 잡았을 때를 알아보도록 하자.

 

맨 앞의 원소를 pivot으로 하고, left를 pivot의 한칸 뒤 원소로 잡는다. 또한 right는 맨 뒤의 원소로 잡는다.

이제 left가 pivot보다 클 때까지 증가시키고, right는 pivot보다 작아질 때까지 감소시킨다.

6은 pivot보다 크므로 left가 멈춘다. 또한 2는 pivot보다 작으므로 right가 멈춘다.

 

swap을 할 때 두가지 경우가 있는데,

1. left가 right보다 크거나 같을 때 -> swap(arr, right, pivot)

2. left가 right보다 작을 때 -> swap(arr, left, right)

 

이번엔 left < right이므로 swap(arr, left, right)이다.

swap을 한 후 이어서 left와 right를 탐색한다.

이번 경우는 left > right이다.

따라서 swap(arr, right, pivot)을 한다.

right가 left보다 커졌기 때문에 반복문을 종료하고 right를 기준으로 start ~ right-1, right+1 ~ end의 두 배열로 분할한다.

두 배열에도 똑같이 원래 배열에서 했던 방식을 돌려준다.

이 때 오른쪽 배열인 6, 7을 보면 right가 더 작은 값을 찾기 위해 왼쪽으로 가는데, 끝에 마주치게 된다.

이 때 swap(arr, right, pivot)이 일어나는데, 배열에 변화가 없다.

따라서 왼쪽 배열만을 보면 된다.

이번에도 left > right가 되었으므로, start ~ right-1, right+1 ~ end의 두 배열로 분할시킨다.

이 때 {2, 1}, {3}, {4}의 배열로 나눠지게 된다.

3, 4는 배열의 크기가 1이므로 신경쓰지 않아도 된다.

{2, 1} 배열을 보자.

위는 left와 right가 같은 위치에 있다.

그렇다면 swap(arr, right, pivot)이 일어난다.

결론적으로 정렬된 배열 형태가 된다.

퀵 정렬 왼쪽 피벗 코드

public class quickSortLeftPivot {
    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 4, 9, 3, 2, 7, 8};
        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 = start;
        int left = start + 1;
        int right = end;
        while(left <= right) {
            while(left <= end && arr[left] < arr[pivot]) left++;
            while(right > start && arr[right] >= arr[pivot]) right--;
            if(left >= right) swap(arr, right, pivot);
            else swap(arr, left, right);
        }
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }
    public static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}