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 - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
중앙, 첫번째 피벗을 할 때도 배열을 예로 들어보자.
마지막 원소인 7을 피벗으로 잡을 것이다.
left는 첫번째 위치, right는 end-1로 한다.
arr[left]이 arr[pivot]보다 큰 값이 나올 때까지 left를 증가시켜주고,
arr[right]가 arr[pivot]보다 작은 값이 나올 때까지 right를 감소시킨다.
따라서 left, right는 다음과 같은 위치에 있을 것이다.
![[알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
피벗을 마지막으로 잡았을 때 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 - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
오른쪽 배열은 길이가 1이라 start와 end가 같으므로 저대로 놔두면 된다.
왼쪽 배열을 다시 한번 위와 같은 과정을 거쳐보자.
left와 right를 조건에 맞게 옮겨보면 다음과 같이 된다.
![[알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
left가 right보다 왼쪽에 있다.
따라서 swap(arr, left, right)를 해준다.
![[알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
또 다시 left, right를 움직여보자.
![[알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](http://t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png)
right < left이므로 swap(arr, left, pivot)을 해준 후 재귀를 통해 분할을 해준다.
이제 언제 어떠한 과정을 거쳐야 할지 알거라 생각하고 남은 모든 과정을 한번에 올리겠다.
![[알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗 [알고리즘] 퀵 정렬(Quick Sort) - 피벗을 맨 끝 값으로 잡았을 때 - undefined - 퀵 정렬 - 마지막 피벗](https://blog.kakaocdn.net/dna/XQJI8/btrzkyuRfBU/AAAAAAAAAAAAAAAAAAAAAI3RKLkklkduTahs4NJkUyfB76s_g3UJKpsKKBqsaxqj/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1753973999&allow_ip=&allow_referer=&signature=%2B9RIbag790Nu6QnidDBo7%2BlIBPs%3D)
결론적으로 오름차순 정렬이 이루어진다.
코드를 보면 좀 더 이해하는데 도움이 될 것이다.
퀵 정렬 - 마지막 피벗
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;
}
}
'Algorithm' 카테고리의 다른 글
[알고리즘] 그래프 탐색(Graph Search) /BFS, DFS (1) | 2022.06.02 |
---|---|
[알고리즘] 퀵 정렬(Quick Sort) - 랜덤 피벗 (0) | 2022.04.14 |
[알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 첫 값으로 잡았을 때 (0) | 2022.04.13 |
[알고리즘] 퀵 정렬(Quick Sort) - pivot(피벗)을 중앙으로 잡았을 때 (2) | 2022.04.10 |
[알고리즘] 마스터 정리(도사 정리) (0) | 2022.04.09 |
댓글