Algorithm

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

JunsuKim 2022. 4. 13.
728x90

https://jjunsu.tistory.com/187

 

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

퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로 평균적으로 매우 빠른 수행 속도를 자랑한다. 시간복잡도는 평균적으로 O(nlogn)이고, 추...

jjunsu.tistory.com

https://jjunsu.tistory.com/188

 

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

https://jjunsu.tistory.com/187 [알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 퀵 정렬 퀵 정렬은 합병 정렬과 마찬가지로 분할 정복을 알고리즘이다. 가장 훌륭한 알고리즘 중 하나로...

jjunsu.tistory.com

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

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

 

퀵 정렬 - 마지막 피벗

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

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

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

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

 

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

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

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

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

피벗을 마지막으로 잡았을 때 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);

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

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

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

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

 

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

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

left가 right보다 왼쪽에 있다.

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

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

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

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

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

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

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

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

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

퀵 정렬 - 마지막 피벗

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;
    }
}
728x90

댓글