정렬 알고리즘

[8, 17, 18, 22, 50, 32, 33, 44, 29, 25]

void selecSort(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { int min = i; // 최소값의 인덱스를 현재 위치로 초기화 // i+1부터 끝까지 최소값 찾기 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[min]) { min = j; // 더 작은 값의 인덱스 저장 } } // 최소값과 현재 위치의 값 교환 if (min != i) { std::swap(arr[i], arr[min]); } } }

void insertSort(std::vector<int>& arr) { for (int i = 1; i < arr.size(); i++) { int key = arr[i]; // 현재 삽입할 원소 int j = i - 1; // 정렬된 부분의 마지막 인덱스 // key보다 큰 원소들을 한 칸씩 뒤로 이동 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // key를 적절한 위치에 삽입 } }

void bubbleSort(std::vector<int>& arr) // 🔧 bubleSort → bubbleSort 수정 { for (int i = 0; i < arr.size(); i++) { // 🔧 최적화: 매 패스마다 가장 큰 원소가 뒤로 가므로 범위 축소 for (int j = 0; j < arr.size() - 1 - i; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); } } } }

총 반복문 수 = (트리높이) × (16회 반복) = (log₂ N + 1) × (2N) = 2N log₂ N + 2N → O(n log n)

#include <vector> #include <iostream> std::vector<int> vect = {3, 5, 15, 26, 27}; // 전역 배열 std::vector<int> result(100); // 임시 배열 (추가 메모리) void run(int start, int end) { int mid = (start + end) / 2; // 기저 조건: 원소가 1개면 종료 if (start == end) { return; } // 분할 (Divide) run(start, mid); // 왼쪽 절반 정렬 run(mid + 1, end); // 오른쪽 절반 정렬 // 정복 (Conquer) - 병합 과정 int a = start; // 왼쪽 부분 배열 포인터 (start ~ mid) int b = mid + 1; // 오른쪽 부분 배열 포인터 (mid+1 ~ end) int idx = 0; // 결과 배열 인덱스 // 두 부분 배열을 비교하며 병합 while (true) { // 두 부분 배열을 모두 처리했으면 종료 if (a > mid && b > end) break; // 왼쪽 배열을 모두 처리한 경우 if (a > mid) result[idx++] = vect[b++]; // 오른쪽 배열을 모두 처리한 경우 else if (b > end) result[idx++] = vect[a++]; // 두 원소 비교하여 작은 것 선택 else if (vect[a] < vect[b]) result[idx++] = vect[a++]; else result[idx++] = vect[b++]; } // 임시 배열의 결과를 원본 배열로 복사 for (int i = 0; i < idx; i++) { vect[start + i] = result[i]; } } int main() { run(0, 4); // 0번 인덱스부터 4번 인덱스까지 정렬 return 0; }

[3, 5, 15, 26, 27] ↓ [3, 5] [15, 26, 27] ↓ ↓ [3] [5] [15] [26, 27] ↓ [26] [27]

[3] [5] → [3, 5] [26] [27] → [26, 27] [15] [26, 27] → [15, 26, 27] [3, 5] [15, 26, 27] → [3, 5, 15, 26, 27]

if (end - start < 10) { insertionSort(start, end); // 작은 부분은 삽입정렬 return; }

if (vect[mid] <= vect[mid + 1]) { return; // 이미 정렬되어 있으면 병합 생략 }

#include <vector> #include <queue> void heapSort(std::vector<int>& arr) { // 1단계: 모든 원소를 우선순위 큐(최대 힙)에 삽입 std::priority_queue<int> pq; // 기본적으로 최대 힙 for (int i = 0; i < arr.size(); i++) { pq.push(arr[i]); // 힙에 원소 삽입 O(logn) } // 2단계: 힙에서 최대값부터 꺼내어 배열에 저장 for (int i = 0; i < arr.size(); i++) { arr[i] = pq.top(); // 최대값 가져오기 pq.pop(); // 힙에서 제거 O(logn) } }

원본 배열: [5, 3, 1, 8, 7, 2, 4] ↓ 우선순위 큐에 삽입하면서 최대 힙 구성: 8 / \ 7 4 / \ / \ 5 3 2 1

1. pq.top() = 8 → arr[0] = 8, 힙에서 제거 2. pq.top() = 7 → arr[1] = 7, 힙에서 제거 3. pq.top() = 5 → arr[2] = 5, 힙에서 제거 4. pq.top() = 4 → arr[3] = 4, 힙에서 제거 5. pq.top() = 3 → arr[4] = 3, 힙에서 제거 6. pq.top() = 2 → arr[5] = 2, 힙에서 제거 7. pq.top() = 1 → arr[6] = 1, 힙에서 제거 결과: [8, 7, 5, 4, 3, 2, 1] (내림차순)

void heapify(std::vector<int>& arr, int n, int i) { int largest = i; // 루트를 가장 큰 값으로 초기화 int left = 2 * i + 1; // 왼쪽 자식 int right = 2 * i + 2; // 오른쪽 자식 // 왼쪽 자식이 루트보다 크면 if (left < n && arr[left] > arr[largest]) largest = left; // 오른쪽 자식이 현재 가장 큰 값보다 크면 if (right < n && arr[right] > arr[largest]) largest = right; // 가장 큰 값이 루트가 아니면 if (largest != i) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); // 재귀적으로 힙 속성 유지 } } void heapSort(std::vector<int>& arr) { int n = arr.size(); // 1단계: 최대 힙 구성 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 2단계: 힙에서 원소를 하나씩 추출 for (int i = n - 1; i >= 0; i--) { std::swap(arr[0], arr[i]); // 루트(최대값)를 끝으로 이동 heapify(arr, i, 0); // 힙 크기를 줄이고 다시 힙 구성 } }

void quickSort(std::vector<int>& arr) { if (arr.size() <= 1) return; std::stack<int> s; s.push(0); s.push(arr.size() - 1); while (!s.empty()) { int end = s.top(); s.pop(); int start = s.top(); s.pop(); int pivot = arr[end]; int i = start - 1; for (int j = start; j < end; j++) { if (arr[j] < pivot) { i++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[end]); int p = i + 1; if (p - 1 > start) { s.push(start); s.push(p - 1); } if (p + 1 < end) { s.push(p + 1); s.push(end); } } }