아래 내용은 부스트코스 <자바로 구현하고 배우는 자료구조> 강의를 들으며 정리한 것입니다.
퀵 정렬 (quick sort)
정렬 알고리즘 중 하나인 퀵 정렬은 중심점 - 피벗(Pivot Point)을 임의로 고른 후 이 중심점보다 작은 수를 한 쪽으로 분류하고 큰 수들은 다른 쪽으로 분류하여 정렬하는 방법이다. 매우 빠른 수행 속도를 가지는 정렬 방식이다.
퀵 정렬은 in-place 정렬로 추가로 메모리 공간을 필요로하지 않으며 중복 숫자의 순서를 보장할 수 없는 불안정 정렬이다.
퀵 정렬 과정(순서)

1) 피벗(pivot)을 선택한다. (주로 리스트의 중간에 있는 숫자 혹은 마지막에 있는 숫자 - 중간 값일 확률이 높음)
2) 마지막 요소와 피벗의 위치를 바꿔 피벗을 리스트의 가장 끝으로 보낸다.
3) 2개의 카운터를 사용하여 리스트의 처음부터 탐색한다.
- 첫 번째 카운터에는 피벗보다 큰 숫자의 위치를 저장, 두 번째 카운터에는 현재 탐색하고 있는 위치를 저장
4) 탐색하며 피벗보다 작은 숫자를 발견하면 첫 번째 카운터의 숫자 위치와 바꿔준다.
5) 3, 4 과정을 반복하면 피벗보다 큰 수와 피벗보다 작은 수가 나눠진다.
6) 다시 피벗을 선택하여 앞의 과정을 반복
피벗의 왼쪽에 있는 숫자들은 오른쪽에 있는 숫자들과 비교할 필요가 없으므로, 평균적인 경우에 퀵 정렬의 시간 복잡도는 O(n logn)이 된다.
퀵 정렬: Worst case

앞에서 보았듯 퀵 정렬은 평균적인 상황에서 전체 데이터의 반씩만 비교해나가기 때문에 O(n logn)의 시간 복잡도를 갖는다.
퀵 정렬의 Worst case는 계속해서 최소인 지점을 피벗 포인트로 지정할 경우로, (n-1) + (n-2) + (n-3) + (n-4) .... 의 대소 비교를 거치게 된다. 즉, 최악의 경우 퀵 정렬의 시간 복잡도는 O(n^2)이다.
퀵 정렬 : 코드
public class QuickSort <E> {
E[] array;
// 제너릭 생성자
public E[] sort(E[] array) {
this.array = array;
quicksort(0, array.length - 1);
return array;
}
// 위치를 바꿔주는 함수
public void swap(int from, int to) {
E tmp = array[from];
array[from] = array[to];
array[to] = tmp;
}
// 퀵 정렬
public void quicksort(int from, int to) { // from, to: 정렬해야 할 배열의 범위
// 정렬 종료
if (from >= to) return; // 리스트에 요소가 하나 존재: 이미 정렬됨
// value: 중심점(Pivot Point)으로 배열의 마지막에 있는 숫자를 선택
E value = array[to];
// 중심점보다 큰 값을 가리킬 카운터를 가장 앞으로 지정
int counter = from;
// 피벗의 바로 앞까지 탐색
for (int i=from; i < to; i++) {
// 중심점보다 작은 값을 발견하면 중심점보다 큰 값(counter)과 SWAP
if (((Comparable<E>) array[i].compareTo(value) <= 0) {
swap(i, counter);
counter++;
}
}
// 중심점이 중간에 오게 SWAP
swap(counter, to);
// 피벗으로 나뉜 배열의 왼쪽과 오른쪽을 정렬
// 카운터의 위치는 맞는 자리이므로 더 이상 옮길 필요X
quicksort(from, counter - 1);
quicksort(counter + 1, to);
}
'Programming > java 자료구조' 카테고리의 다른 글
| 8-7) 정렬 요약 표 (0) | 2022.10.01 |
|---|---|
| 8-6) 기수 정렬 (0) | 2022.10.01 |
| 8-4) 정렬 - 합병 정렬 (0) | 2022.09.24 |
| 8-3) 정렬 - 셸 정렬 (0) | 2022.09.24 |
| 8-2) 정렬 - 삽입 정렬 (0) | 2022.09.24 |