[알고리즘] 퀵 정렬(Quick Sort) - 랜덤 피벗

https://jjunsu.tistory.com/187

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

https://jjunsu.tistory.com/188

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

https://jjunsu.tistory.com/189

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

퀵 정렬 랜덤 피벗

이제까지 피벗을 중앙, 처음, 마지막으로 잡았을 경우를 풀어보았다.

마지막으로 피벗을 랜덤으로 잡았을 때를 알아보자.

 

랜덤 피벗일 때의 규칙을 보면,

• arr[left] <= arr[pivot]이라면 left를 증가시켜준다.
• arr[right] >= arr[right]이라면 right를 감소시켜준다.
• left와 right가 조건을 충족시켰을 때 left < right면 두 위치의 값을 바꿔준다.
• 반복문을 나왔을 때 arr[left] < arr[pivot]이면 left와 pivot의 값을 바꿔준다.
• left가 start보다 크다면 start부터 left -1까지 분할을 한다.
• left가 end보다 작다면 left부터 end까지 분할을 한다.

이제 랜덤 피벗을 이용한 퀵 정렬의 과정을 보자.

위와 같은 배열이 있고 랜덤 피벗이 6으로 설정되었다 하자.

left와 right를 조건이 충족될 때까지 움직이면 다음과 같다.

이 때 left가 right보다 크므로 반복문을 탈출하게 되고 재귀를 이용해 분할을 한다.

left가 end와 같으므로 quickSort(arr, start, left - 1) 앞 부분만 분할을 해주면 된다.

이번에는 랜덤 피벗이 4가 되었다고 하자.

left는 5로 이미 4보다 크고, right는 2로 이미 4보다 작으므로 이동시킬 필요가 없다.

이를 swap하고, left, right를 이동시키자.

이처럼 과정들을 계속해서 반복하면 정렬된 배열이 나오게 된다.

퀵 정렬 랜덤 피벗 코드

import java.util.concurrent.ThreadLocalRandom;

public class quickSortRandomPivot {
    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) {
        int pivot = ThreadLocalRandom.current().nextInt(end - start + 1) + start;
        int left = start;
        int right = end;
        while(left < right) {
            while(left < right && arr[left] <= arr[pivot]) left++;
            while(left < right && arr[right] >= arr[pivot]) right--;
            if(left < right) swap(arr, left, right);
        }
        if(arr[left] < arr[pivot]) swap(arr, left, pivot);
        if(left > start) quickSort(arr, start, left - 1);
        if(left < end) quickSort(arr, left, end);
    }
    public static void swap(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}