Quick sort(퀵 정렬)
원칙1: pivot을 고른다.(주로 첫번째 또는 마지막 값을 선정하는 편이다.)
원칙2: pivot값을 기준으로 작은쪽, 큰쪽으로 나누어 서로간의 swap으로 위치를 교환한다.(증가될 수 없는 배열이라고 가정....)
원칙3: swap이 끝나면 그 나눈 중심에 pivot을 두고 작은쪽, 큰쪽을 각각 퀵소트한다.
Best case: O(n)
Average case: O(
Worst case: O(
# 재귀함수로 구현한 Quick sort
public class QuickSort implements ISort {
@Override
public void sort(Comparable[] array) {
quickSort(array, 0, array.length - 1);
}
private void quickSort(Comparable[] array, int startIndex, int endIndex) {
if (startIndex >= endIndex) {
return;
}
final Comparable pivot = array[startIndex];
int left = startIndex + 1;
int right = endIndex;
do {
while (array[left].compareTo(pivot) < 0 && left < endIndex) {
left++;
}
while (array[right].compareTo(pivot) > 0 && startIndex < right) {
right--;
}
if (left < right) {
swap(array, left, right);
}
} while (left < right && left < endIndex && startIndex < right);
swap(array, startIndex, right);
quickSort(array, startIndex, right - 1);
quickSort(array, right + 1, endIndex);
}
private void swap(Comparable[] array, int i, int j) {
Comparable temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
Reference:
- https://en.wikipedia.org/wiki/Quicksort
'Algorithms > Sorting' 카테고리의 다른 글
| Merge sort(병합 정렬) (0) | 2017.02.08 |
|---|---|
| Selection sort(선택 정렬) (0) | 2017.02.08 |
| Insertion sort(삽입 정렬) (0) | 2017.02.06 |
| Bubble sort(거품? 정렬) (0) | 2017.02.06 |
) == Worst case: O(
) : 정렬이 거의 다 되어있는 상태에서...