Java의 Arrays.sort는 듀얼피봇 퀵정렬(Dual-Pivot QuickSort)을 사용한다.
듀얼 피봇 퀵정렬은 피봇을 2개를 두고 3개의 구간을 만들어 퀵정렬을 진행한다는 것이다.
이 방식은 하나의 피봇으로 진행하는 퀵 정렬에 비해 좋은 성능을 낸다고 알려진다.
그 이유는 퀵 정렬의 경우 최악의 경우의 피봇을 잡았을 때 (오름차순에서 가장 작은 수 or 내림차순에서 가장 높은 수) 버블정렬과 같은 시간 복잡도가 나온다.
때문에 평균은 O(nlog₂n)로 준수한 시간 복잡도를 갖지만 최악의 경우 O(n²)가 나온다. 때문에 두개의 피봇을 두고 퀵 정렬을 한다.
그렇기에 그 기본이 되는 퀵 정렬에 대해 공부해 보았다.
퀵정렬의 정렬 방식
- 피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽에 위치시키고 피벗보다 큰 요소는 오른쪽에 위치시킨다.
- 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트 각각을 다시 정렬한다.
- 분할된 서브 리스트에 대해서는 순환 호출을 이용하여 정렬을 반복한다.
- 서브 리스트에서도 재차 피벗을 정하고 이를 기준으로 2개의 서브 리스트로 다시 나누어 주는 과정을 반복한다.
- 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
- 리스트의 크기가 0이나 1이 될 때까지 반복한다.
퀵정렬 애니메이션
퀵정렬의 단계
- 분할: 배열을 pivot을 기준으로 2개의 서브 리스트 (pivot을 중심으로 왼쪽: pivot보다 작은 요소들, 오른쪽: pivot보다 큰 요소들)로 분할.
- 정복: 나누어진 두 개의 공간을 정렬한다. 서브 리스트의 크기가 하나가 남을 때까지 재귀 호출을 이용하여 다시 분할 정복해 나간다.
- 결합: 정렬된 부분 배열들을 하나의 배열에 합병한다.
아래는 타 블로거의 자료를 참고하여 적어 보았다.(감사합니다)
참조 :https://innovation123.tistory.com/84
[JAVA] 퀵 정렬 (Quick Sort)
퀵 정렬 (Quick sort) 퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 시간복잡도가 비교적 빠르기 때문에 코딩테스트에서
innovation123.tistory.com
퀵 정렬 예제
예제 배열
예제 1 : 첫 번째 반복
위와 같은 정렬되지 않은 배열이 있다.
- 중간값을 pivot으로 선정한다. (5)
- start와 end인덱스를 지정한다.
start < pivot의 경우 start를 한 칸씩 오른쪽으로 이동한다. ( pivot보다 큰 값을 찾을 때까지 이동 )
end > pivot의 경우 end를 한 칸씩 왼쪽으로 이동한다. (pivot보다 작은 값을 찾을 때까지 이동 )
start와 end 포인트를 더 이상 움직일 수 없는 경우(원하는 값을 찾은 경우) 두 데이터를 swap 한다.( 2와 9 swap )
swap을 하고 나서 start, end 포인트를 한 칸씩 옮겨준다.
다시 위의 과정을 반복해, start, end 포인트가 멈출 때까지 이동시킨다. ( start=7, end=1)
찾은 두 값을 swap 하고, 포인트를 한 칸씩 옮겨준다.
여기서 5의 위치는 start 포인트이면서 동시에 pivot 값이다.
start(5)는 5보다 작지 않기 때문에 움직이지 않는다.
0은 5보다 작으므로 움직이지 않는다. ( 0과 5 swap )
0과 5를 swap 하고, 포인트를 각각 움직여준다.
start와 end가 반복문의 조건에 맞지 않게 된다. (start <= end)
따라서 이 루프는 종료하고, start가 가리키고 있는 5를 기준으로 전체 배열을 나눈다. (파티션)
그렇게 되면 5는 오른쪽 파티션의 첫 번째 인덱스가 되고, 배열은 아래와 같이 나뉘게 된다.
이렇게 하나의 루프가 종료되면 pivot 값이었던 5는 전체 배열에서의 알맞은 위치를 찾게 된다.
이후, 두 개로 나뉜 파티션에서 위의 과정을 반복한다.
각각 중간값(pivot), start, end 포인트를 정하는 등..
두 번째 파티션에 대하여 한 번의 루프를 더 돌아보겠다.
예제 2 : 두 번째 반복
이제 start=5, pivot=6, end=9로 지정하여 새로 시작한다.
start는 pivot보다 큰 값이 나올 때까지, end는 pivot보다 작은 값이 나올 때까지 이동한다.
( end > pivot일 때 움직이므로 end포인트는 6에서 멈춘다)
두 값을 swap 하고, 한 칸씩 움직인다.
움직이면 start <=end 조건을 만족하지 못하기 때문에 해당 루프는 끝난다.
import java.util.Arrays;
import java.util.Scanner;
public class QuickSort {
static int[] arr;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
quickSort(0, n-1);
System.out.println(Arrays.toString(arr));
}
static void quickSort(int start, int end) {
//배열이 더이상 나누어지지 않으면 재귀를 빠져나간다.
if(start>= end) return;
//pivot 의 index를 중간값으로 설정
int mid = start + (end - start) / 2;
//pivot 의 값
int midValue = arr[mid];
//비교 되는 범위 값
int left = start;
int right = end;
// 왼쪽의 비교값이 오른쪽보다 커지지 않을때까지만 반복문 실행
while (left <= right) {
//pivot 을 기준으로 왼쪽과 오른쪽으로 나누어 확인
// 왼쪽의 값을 pivot 과 비교하여 작으면 그대로 두고 크거나 같을때 까지 왼쪽 index 의 값을 올림
// (크면 pivot 을 기준으로 오른쪽으로 옮기고 아니면 그대로 두겠다)
while (arr[left] < midValue) {
left++;
}
// 위와 정 반대
while (arr[right] > midValue) {
right--;
}
// 왼쪽 인덱스와 오른쪽 인덱스가 pivot 을 기준으로 반대편으로 넘어가지 않았다면 서로 바꾼다
if (left <= right) {
swap(left, right);
//바꾸고 또 비교해야함으로 왼쪽과 오른쪽 인덱스를 반대쪽으로 하나씩 옮겨준다
left++;
right--;
}
}
/*
* 빠져나온 후엔 다시 둘로 쪼개서 탐색 및 정렬
* pivot , pivot + 1로 넣을 수도 있겠지만
* 아래와 같이 하면 pivot 이 정중앙의 숫자라면 재귀에 포함시키기 않는다
* */
quickSort(start, right);
quickSort(left, end);
}
static void swap(int left, int right) {
int temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
}
