1/*
2 * 정렬 알고리즘 (Sorting Algorithms)
3 * Bubble, Selection, Insertion, Merge, Quick, Heap, Counting, Radix
4 *
5 * 다양한 정렬 알고리즘의 구현과 비교입니다.
6 */
7
8#include <iostream>
9#include <vector>
10#include <algorithm>
11#include <queue>
12#include <cmath>
13
14using namespace std;
15
16// =============================================================================
17// 1. 버블 정렬 - O(n²)
18// =============================================================================
19
20void bubbleSort(vector<int>& arr) {
21 int n = arr.size();
22 for (int i = 0; i < n - 1; i++) {
23 bool swapped = false;
24 for (int j = 0; j < n - i - 1; j++) {
25 if (arr[j] > arr[j + 1]) {
26 swap(arr[j], arr[j + 1]);
27 swapped = true;
28 }
29 }
30 if (!swapped) break; // 최적화
31 }
32}
33
34// =============================================================================
35// 2. 선택 정렬 - O(n²)
36// =============================================================================
37
38void selectionSort(vector<int>& arr) {
39 int n = arr.size();
40 for (int i = 0; i < n - 1; i++) {
41 int minIdx = i;
42 for (int j = i + 1; j < n; j++) {
43 if (arr[j] < arr[minIdx]) {
44 minIdx = j;
45 }
46 }
47 swap(arr[i], arr[minIdx]);
48 }
49}
50
51// =============================================================================
52// 3. 삽입 정렬 - O(n²)
53// =============================================================================
54
55void insertionSort(vector<int>& arr) {
56 int n = arr.size();
57 for (int i = 1; i < n; i++) {
58 int key = arr[i];
59 int j = i - 1;
60 while (j >= 0 && arr[j] > key) {
61 arr[j + 1] = arr[j];
62 j--;
63 }
64 arr[j + 1] = key;
65 }
66}
67
68// =============================================================================
69// 4. 병합 정렬 - O(n log n)
70// =============================================================================
71
72void merge(vector<int>& arr, int left, int mid, int right) {
73 vector<int> L(arr.begin() + left, arr.begin() + mid + 1);
74 vector<int> R(arr.begin() + mid + 1, arr.begin() + right + 1);
75
76 size_t i = 0, j = 0;
77 int k = left;
78
79 while (i < L.size() && j < R.size()) {
80 if (L[i] <= R[j])
81 arr[k++] = L[i++];
82 else
83 arr[k++] = R[j++];
84 }
85
86 while (i < L.size()) arr[k++] = L[i++];
87 while (j < R.size()) arr[k++] = R[j++];
88}
89
90void mergeSort(vector<int>& arr, int left, int right) {
91 if (left < right) {
92 int mid = left + (right - left) / 2;
93 mergeSort(arr, left, mid);
94 mergeSort(arr, mid + 1, right);
95 merge(arr, left, mid, right);
96 }
97}
98
99// =============================================================================
100// 5. 퀵 정렬 - O(n log n) 평균
101// =============================================================================
102
103int partition(vector<int>& arr, int low, int high) {
104 int pivot = arr[high];
105 int i = low - 1;
106
107 for (int j = low; j < high; j++) {
108 if (arr[j] <= pivot) {
109 i++;
110 swap(arr[i], arr[j]);
111 }
112 }
113 swap(arr[i + 1], arr[high]);
114 return i + 1;
115}
116
117void quickSort(vector<int>& arr, int low, int high) {
118 if (low < high) {
119 int pi = partition(arr, low, high);
120 quickSort(arr, low, pi - 1);
121 quickSort(arr, pi + 1, high);
122 }
123}
124
125// 3-way 퀵소트 (중복 원소에 효율적)
126void quickSort3Way(vector<int>& arr, int low, int high) {
127 if (low >= high) return;
128
129 int lt = low, gt = high;
130 int pivot = arr[low];
131 int i = low + 1;
132
133 while (i <= gt) {
134 if (arr[i] < pivot) {
135 swap(arr[lt++], arr[i++]);
136 } else if (arr[i] > pivot) {
137 swap(arr[i], arr[gt--]);
138 } else {
139 i++;
140 }
141 }
142
143 quickSort3Way(arr, low, lt - 1);
144 quickSort3Way(arr, gt + 1, high);
145}
146
147// =============================================================================
148// 6. 힙 정렬 - O(n log n)
149// =============================================================================
150
151void heapify(vector<int>& arr, int n, int i) {
152 int largest = i;
153 int left = 2 * i + 1;
154 int right = 2 * i + 2;
155
156 if (left < n && arr[left] > arr[largest])
157 largest = left;
158 if (right < n && arr[right] > arr[largest])
159 largest = right;
160
161 if (largest != i) {
162 swap(arr[i], arr[largest]);
163 heapify(arr, n, largest);
164 }
165}
166
167void heapSort(vector<int>& arr) {
168 int n = arr.size();
169
170 // 힙 구성
171 for (int i = n / 2 - 1; i >= 0; i--) {
172 heapify(arr, n, i);
173 }
174
175 // 하나씩 추출
176 for (int i = n - 1; i > 0; i--) {
177 swap(arr[0], arr[i]);
178 heapify(arr, i, 0);
179 }
180}
181
182// =============================================================================
183// 7. 계수 정렬 - O(n + k)
184// =============================================================================
185
186void countingSort(vector<int>& arr) {
187 if (arr.empty()) return;
188
189 int maxVal = *max_element(arr.begin(), arr.end());
190 int minVal = *min_element(arr.begin(), arr.end());
191 int range = maxVal - minVal + 1;
192
193 vector<int> count(range, 0);
194 vector<int> output(arr.size());
195
196 for (int x : arr) {
197 count[x - minVal]++;
198 }
199
200 for (int i = 1; i < range; i++) {
201 count[i] += count[i - 1];
202 }
203
204 for (int i = arr.size() - 1; i >= 0; i--) {
205 output[count[arr[i] - minVal] - 1] = arr[i];
206 count[arr[i] - minVal]--;
207 }
208
209 arr = output;
210}
211
212// =============================================================================
213// 8. 기수 정렬 - O(d × (n + k))
214// =============================================================================
215
216void countingSortForRadix(vector<int>& arr, int exp) {
217 int n = arr.size();
218 vector<int> output(n);
219 vector<int> count(10, 0);
220
221 for (int x : arr) {
222 count[(x / exp) % 10]++;
223 }
224
225 for (int i = 1; i < 10; i++) {
226 count[i] += count[i - 1];
227 }
228
229 for (int i = n - 1; i >= 0; i--) {
230 output[count[(arr[i] / exp) % 10] - 1] = arr[i];
231 count[(arr[i] / exp) % 10]--;
232 }
233
234 arr = output;
235}
236
237void radixSort(vector<int>& arr) {
238 if (arr.empty()) return;
239
240 int maxVal = *max_element(arr.begin(), arr.end());
241
242 for (int exp = 1; maxVal / exp > 0; exp *= 10) {
243 countingSortForRadix(arr, exp);
244 }
245}
246
247// =============================================================================
248// 테스트
249// =============================================================================
250
251void printVector(const vector<int>& v) {
252 cout << "[";
253 for (size_t i = 0; i < v.size(); i++) {
254 cout << v[i];
255 if (i < v.size() - 1) cout << ", ";
256 }
257 cout << "]";
258}
259
260int main() {
261 cout << "============================================================" << endl;
262 cout << "정렬 알고리즘 예제" << endl;
263 cout << "============================================================" << endl;
264
265 vector<int> original = {64, 34, 25, 12, 22, 11, 90};
266
267 // 1. 버블 정렬
268 cout << "\n[1] 버블 정렬" << endl;
269 vector<int> arr1 = original;
270 bubbleSort(arr1);
271 cout << " 결과: ";
272 printVector(arr1);
273 cout << endl;
274
275 // 2. 선택 정렬
276 cout << "\n[2] 선택 정렬" << endl;
277 vector<int> arr2 = original;
278 selectionSort(arr2);
279 cout << " 결과: ";
280 printVector(arr2);
281 cout << endl;
282
283 // 3. 삽입 정렬
284 cout << "\n[3] 삽입 정렬" << endl;
285 vector<int> arr3 = original;
286 insertionSort(arr3);
287 cout << " 결과: ";
288 printVector(arr3);
289 cout << endl;
290
291 // 4. 병합 정렬
292 cout << "\n[4] 병합 정렬" << endl;
293 vector<int> arr4 = original;
294 mergeSort(arr4, 0, arr4.size() - 1);
295 cout << " 결과: ";
296 printVector(arr4);
297 cout << endl;
298
299 // 5. 퀵 정렬
300 cout << "\n[5] 퀵 정렬" << endl;
301 vector<int> arr5 = original;
302 quickSort(arr5, 0, arr5.size() - 1);
303 cout << " 결과: ";
304 printVector(arr5);
305 cout << endl;
306
307 // 6. 힙 정렬
308 cout << "\n[6] 힙 정렬" << endl;
309 vector<int> arr6 = original;
310 heapSort(arr6);
311 cout << " 결과: ";
312 printVector(arr6);
313 cout << endl;
314
315 // 7. 계수 정렬
316 cout << "\n[7] 계수 정렬" << endl;
317 vector<int> arr7 = original;
318 countingSort(arr7);
319 cout << " 결과: ";
320 printVector(arr7);
321 cout << endl;
322
323 // 8. 기수 정렬
324 cout << "\n[8] 기수 정렬" << endl;
325 vector<int> arr8 = {170, 45, 75, 90, 802, 24, 2, 66};
326 cout << " 원본: ";
327 printVector(arr8);
328 cout << endl;
329 radixSort(arr8);
330 cout << " 결과: ";
331 printVector(arr8);
332 cout << endl;
333
334 // 9. 복잡도 비교
335 cout << "\n[9] 정렬 알고리즘 복잡도 비교" << endl;
336 cout << " | 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 |" << endl;
337 cout << " |------------|-----------|-----------|-----------|-------|------|" << endl;
338 cout << " | 버블 | O(n) | O(n²) | O(n²) | O(1) | O |" << endl;
339 cout << " | 선택 | O(n²) | O(n²) | O(n²) | O(1) | X |" << endl;
340 cout << " | 삽입 | O(n) | O(n²) | O(n²) | O(1) | O |" << endl;
341 cout << " | 병합 | O(n log n)| O(n log n)| O(n log n)| O(n) | O |" << endl;
342 cout << " | 퀵 | O(n log n)| O(n log n)| O(n²) | O(log)| X |" << endl;
343 cout << " | 힙 | O(n log n)| O(n log n)| O(n log n)| O(1) | X |" << endl;
344 cout << " | 계수 | O(n+k) | O(n+k) | O(n+k) | O(k) | O |" << endl;
345 cout << " | 기수 | O(d(n+k)) | O(d(n+k)) | O(d(n+k)) | O(n+k)| O |" << endl;
346
347 cout << "\n============================================================" << endl;
348
349 return 0;
350}