Quicksort
과정
- 정렬할 배열이 주어진다
- 마지막 수를 기준
pivot으로 삼는다 - 기준보다 작은 수는 기준의 왼쪽에, 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다
- 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다
최악의 경우
O(n2)
최선의 경우
O(nlogn)
pivot의 선택
- 첫번째 값이나 마지막 값을 피봇으로 선택
- 이미 정렬된 데이터 혹은 거꾸로 정렬된 데이터가 최악의 경우
- 현실의 데이터는 랜덤하지 않으므로 거끄로 정렬된 데이터가 입력으로 들어올 가능성은 매우 높음
- 따라서 좋은 방법이라고 할 수 없음
- Median of Three
- 첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값
median을 피봇으로 선택 - 최악의 경우 시간복잡도가 달라지지는 않음
- 첫번째 값과 마지막 값, 그리고 가운데 값 중에서 중간값
- Randomized Quicksort
- 피봇을 랜덤하게 선택
- 평균 시간복잡도 O(nlogn)
퀵소트 구현코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package Algorithm.sort;
public class QuickSortExample {
public static void main(String[] args) {
int[] arr = {3,9,4,7,5,0,1,6,8,2};
printArray(arr);
quickSort(arr);
printArray(arr);
}
private static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length-1);
}
private static void quickSort(int[] arr, int start, int end) {
int part2 = partition(arr, start, end);
if (start < part2 - 1) {
quickSort(arr, start, part2 - 1);
}
if (part2 < end) {
quickSort(arr, part2, end);
}
}
private static int partition(int[] arr, int start, int end) {
int pivot = arr[(start + end) / 2];
while (start <= end) {
while (arr[start] < pivot) start++;
while (arr[end] > pivot) end--;
if (start <= end) {
swap(arr, start, end);
start++;
end--;
}
}
return start;
}
private static void swap(int[] arr, int start, int end) {
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
private static void printArray(int[] arr) {
for (int data : arr) {
System.out.print(data + ", ");
}
System.out.println();
}
}
