Quick Sort(퀵 정렬)

배열: [4, 3, 9, 8, 5, 7, 1, 2] ↑ pivot 특정 범위의 가장 왼쪽 원소를 피벗으로 선택

목표: pivot(4)를 기준으로 분할 - 왼쪽: 4보다 작은 수들 (순서는 섞여도 됨) - 오른쪽: 4보다 큰 수들 (순서는 섞여도 됨)

초기 상태: [4, 3, 9, 8, 5, 7, 1, 2]

원본: [1, 3, 2, 4, 5, 7, 8, 9] ←----- pivot보다 작은수들 pivot pivot보다 큰 수들 ----→ (순서는 섞여도 됨) (순서는 섞여도 됨)

왼쪽 부분: [1, 3, 2] → pivot으로 다시 분할 오른쪽 부분: [5, 7, 8, 9] → pivot으로 다시 분할

1단계: a는 오른쪽으로, b는 왼쪽으로 이동 [4, 3, 9, 8, 5, 7, 1, 2] ↑ ↑ a(9>4 발견) b(2<4 발견)

2단계: 9와 2를 교환 [4, 3, 2, 8, 5, 7, 1, 9] ↑ ↑ a b 3단계: 계속 진행 [4, 3, 2, 1, 5, 7, 8, 9] ↑ ↑ b a (엇갈림!)

최종: pivot(4)과 b위치(1) 교환 [1, 3, 2, 4, 5, 7, 8, 9] ↑ pivot 최종 위치

#include <iostream> int vect[10] = { 4,3,9,8,5,7,1,2 }; int n = 8; void quicksort(int start, int end) { if (start >= end) return; int pivot = start; // 첫 번째 원소를 피벗으로 int a = start + 1; // 왼쪽에서 시작 int b = end; // 오른쪽에서 시작 while (true) { // a: pivot보다 큰 원소를 찾을 때까지 오른쪽으로 이동 while (a <= end && vect[a] <= vect[pivot]) a++; // b: pivot보다 작은 원소를 찾을 때까지 왼쪽으로 이동 while (b >= start && vect[b] > vect[pivot]) b--; // a와 b가 엇갈렸으면 종료 if (a > b) break; // 찾은 원소들을 교환 std::swap(vect[a], vect[b]); } // pivot을 올바른 위치(b)로 이동 std::swap(vect[pivot], vect[b]); // 재귀 호출로 좌우 부분 정렬 quicksort(start, b - 1); // 왼쪽 부분 quicksort(b + 1, end); // 오른쪽 부분 } int main() { quicksort(0, n - 1); // 결과 출력 for (int i = 0; i < n; i++) { std::cout << vect[i] << " "; } return 0; }

#include <iostream> int vect[10] = { 4,3,9,8,5,7,1,2 }; int n = 8; void quicksort(int left, int right) { int i = left, j = right; int pivot = vect[(left + right) / 2]; // 중간값을 피벗으로 /* partition */ while (i <= j) { // 왼쪽에서 피벗보다 큰 값 찾기 while (vect[i] < pivot) i++; // 오른쪽에서 피벗보다 작은 값 찾기 while (vect[j] > pivot) j--; // 교환 조건 만족시 교환 if (i <= j) { std::swap(vect[i++], vect[j--]); } } /* recursion */ if (left < j) quicksort(left, j); // 왼쪽 부분 재귀 if (i < right) quicksort(i, right); // 오른쪽 부분 재귀 } int main() { quicksort(0, n - 1); return 0; }

초기 배열: [4, 3, 9, 8, 5, 7, 1, 2] 1차 분할 후: [1, 3, 2, 4, 5, 7, 8, 9] ←--left--→ ↑ ←--right--→ pivot(4) 2차 분할: 왼쪽 [1, 3, 2]: pivot=1 → [1, 2, 3] 오른쪽 [5, 7, 8, 9]: 이미 정렬됨 3차 분할: [2, 3]: pivot=2 → [2, 3] 최종 결과: [1, 2, 3, 4, 5, 7, 8, 9]

이미 정렬된 배열: [1, 2, 3, 4, 5] 첫 번째 원소를 피벗으로 선택하면: - 왼쪽: [] (빈 배열) - 오른쪽: [2, 3, 4, 5] (거의 모든 원소) 이런 불균형 분할이 계속되면 O(n²)

void optimizedQuickSort(int arr[], int low, int high) { if (low < high) { // 작은 배열은 삽입정렬 사용 if (high - low < 10) { insertionSort(arr, low, high); return; } // Median-of-3 피벗 선택 int mid = (low + high) / 2; if (arr[mid] < arr[low]) swap(arr[mid], arr[low]); if (arr[high] < arr[low]) swap(arr[high], arr[low]); if (arr[high] < arr[mid]) swap(arr[high], arr[mid]); int pi = partition(arr, low, high); optimizedQuickSort(arr, low, pi - 1); optimizedQuickSort(arr, pi + 1, high); } }