퀵 정렬은 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복하여 정렬하는 알고리즘 입니다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간복잠도는 O(nlogn)이며 최악의 경우 O(n²)이 됩니다.
정렬 과정
- 데이터를 분할하는 pivot을 설정(그림의 경우 가장 오른쪽 끝을 pivot로 설정)
- pivot을 기준으로 다음 과정을 거쳐 데이터를 2개의 집합으로 분리
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동
- end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 1칸 이동
- start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동
- start와 end가 만날 때가지 1~3번 반복
- start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot를 가리키는 데이터가 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터를 삽입
- 분리 집합에서 각각 다시 pivot를 선정
- 분리집합이 1개 이하가 될때 까지 1~3번 반복
소스 코드
public void quickSort(int[] arr, int left, int right) {
// base condition
if (left >= right) {
return;
}
int pivot = arr[right];
int sortedIndex = left;
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
swap(arr, i, sortedIndex);
sortedIndex++;
}
}
swap(arr, sortedIndex, right);
quickSort(arr, left, sortedIndex - 1);
quickSort(arr, sortedIndex + 1, right);
}
private void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
'Algorithm > 이론' 카테고리의 다른 글
기수 정렬 (Radix Sort) - JAVA (0) | 2023.05.17 |
---|---|
병합 정렬 (Merge Sort) - JAVA (0) | 2023.05.17 |
삽입 정렬 (Insertion Sort) - JAVA (0) | 2023.05.17 |
선택 정렬 (Selection Sort) - JAVA (0) | 2023.05.17 |
버블 정렬 (Bubble Sort) - JAVA (0) | 2023.05.17 |