정렬 알고리즘(선택, 삽입, 버블, 합병, 힙, 퀵)

void selectionSort(std::vector<int>& arr) { int n = arr.size(); // 배열의 처음부터 끝에서 두 번째까지 반복 // (마지막 원소는 자동으로 정렬되므로 n-1까지만) for (int i = 0; i < n - 1; i++) { int minIndex = i; // 현재 위치를 최솟값 인덱스로 초기화 // 현재 위치 다음부터 배열 끝까지 순회하며 최솟값 찾기 for (int j = i + 1; j < n; j++) { if (arr[j] < arr[minIndex]) { minIndex = j; // 더 작은 값을 발견하면 인덱스 갱신 } } // 최솟값이 현재 위치가 아니라면 교환 // (이미 최솟값이 현재 위치에 있다면 불필요한 교환 방지) if (minIndex != i) { std::swap(arr[i], arr[minIndex]); } } }

void insertionSort(std::vector<int>& arr) { // 두 번째 원소부터 시작 (첫 번째 원소는 이미 정렬된 것으로 간주) for (int i = 1; i < arr.size(); i++) { int key = arr[i]; // 현재 삽입할 원소를 key에 저장 int j = i - 1; // 정렬된 부분의 마지막 인덱스 // key보다 큰 원소들을 한 칸씩 뒤로 이동 // j가 0 이상이고, arr[j]가 key보다 크면 계속 이동 while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; // 한 칸 뒤로 이동 j--; // 왼쪽으로 이동하며 계속 비교 } // while 루프가 종료된 위치(j+1)에 key 삽입 arr[j + 1] = key; } }

void bubbleSort(std::vector<int>& arr) { int n = arr.size(); // 외부 루프: 배열 크기만큼 반복 for (int i = 0; i < n - 1; i++) { // 내부 루프: 아직 정렬되지 않은 부분만 비교 // 매 회전마다 가장 큰 원소가 뒤로 가므로 비교 범위가 줄어듭니다 for (int j = 0; j < n - 1 - i; j++) { // 인접한 두 원소 비교 if (arr[j] > arr[j + 1]) { // 순서가 잘못되었으면 교환 std::swap(arr[j], arr[j + 1]); } } } }

void bubbleSortOptimized(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; // 교환 발생 여부를 추적 for (int j = 0; j < n - 1 - i; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); swapped = true; // 교환이 발생했음을 표시 } } // 한 번의 전체 순회에서 교환이 없었다면 이미 정렬된 상태 if (!swapped) { break; // 조기 종료 } } }

#include <iostream> #include <vector> using namespace std; int vect[5] = { 6, 1, 3, 8, 5 }; int result[5]; void run(int start, int end) { int mid = (start + end) / 2; if (start >= end) return; run(start, mid); run(mid + 1, end); // 두 영역 합치기 (result에 결과저장) int a = start; // 영역은 start ~ mid 까지 int b = mid + 1; // 영역은 mid + 1 ~ end 까지 int t = 0; while (1) { if (a > mid && b > end) break; if (a > mid) //a 영역이 끝났으면 b영역값을 등록 result[t++] = vect[b++]; else if (b > end) //b 영역이 끝났으면 a 영역값을 등록 result[t++] = vect[a++]; else if (vect[a] <= vect[b]) // vect[a] 와 vect[b] 비교해서 작은것을 result에 넣기 result[t++] = vect[a++]; else result[t++] = vect[b++]; } // result에 있는 정렬된 배열을 vect에 적용 for (int i = 0; i < t; i++) { vect[start + i] = result[i]; } } int main() { run(0, 4); // 정렬된 결과 출력 for (int num : vect) { cout << num << " "; } cout << endl; return 0; }

포인터 → [6] [1, 3] ← 포인터 ↑ ↑ 1단계: 6 vs 1 → 1이 작음 → result = [1] 2단계: 6 vs 3 → 3이 작음 → result = [1, 3] 3단계: 6 vs 없음 → 6 추가 → result = [1, 3, 6]

void mergeSort(int start, int end) { // 원소가 10개 이하면 삽입정렬 사용 if (end - start < 10) { insertionSort(vect, start, end); return; } // 나머지는 기존 병합정렬 로직... }

// 왼쪽 부분의 마지막 원소가 오른쪽 부분의 첫 원소보다 작거나 같으면 // 이미 정렬되어 있으므로 병합 불필요 if (vect[mid] <= vect[mid + 1]) { return; }

#include <vector> #include <queue> #include <iostream> void heapSort(std::vector<int>& arr) { // 1단계: 모든 원소를 우선순위 큐(최대 힙)에 삽입 // std::priority_queue는 기본적으로 최대 힙으로 동작합니다 std::priority_queue<int> maxHeap; for (int i = 0; i < arr.size(); i++) { maxHeap.push(arr[i]); // 힙에 원소 삽입 - 각 삽입은 O(log n) } // 2단계: 힙에서 최댓값을 하나씩 꺼내어 배열에 저장 // 최댓값부터 꺼내므로 내림차순으로 정렬됩니다 for (int i = 0; i < arr.size(); i++) { arr[i] = maxHeap.top(); // 힙의 루트 (최댓값) 가져오기 maxHeap.pop(); // 힙에서 루트 제거 - O(log n) } } int main() { std::vector<int> arr = {5, 2, 9, 1, 5, 6}; heapSort(arr); // 정렬된 결과 출력 (내림차순) for (int num : arr) { std::cout << num << " "; // 출력: 9 6 5 5 2 1 } std::cout << std::endl; return 0; }

// 최소 힙 사용 std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

for (int i = arr.size() - 1; i >= 0; i--) { arr[i] = maxHeap.top(); maxHeap.pop(); }

// 특정 노드를 루트로 하는 서브트리를 힙으로 만드는 함수 void heapify(std::vector<int>& arr, int n, int rootIdx) { int largest = rootIdx; // 루트를 가장 큰 값으로 초기화 int leftChild = 2 * rootIdx + 1; // 왼쪽 자식 인덱스 int rightChild = 2 * rootIdx + 2; // 오른쪽 자식 인덱스 // 왼쪽 자식이 존재하고 루트보다 크면 if (leftChild < n && arr[leftChild] > arr[largest]) { largest = leftChild; } // 오른쪽 자식이 존재하고 현재 가장 큰 값보다 크면 if (rightChild < n && arr[rightChild] > arr[largest]) { largest = rightChild; } // 가장 큰 값이 루트가 아니면 교환하고 재귀적으로 힙 속성 유지 if (largest != rootIdx) { std::swap(arr[rootIdx], arr[largest]); heapify(arr, n, largest); // 영향받은 서브트리 재귀 처리 } } void heapSort(std::vector<int>& arr) { int n = arr.size(); // 1단계: 최대 힙 구성 (Build Max Heap) // 마지막 비단말 노드부터 역순으로 heapify 수행 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]); // 힙 크기를 1 줄이고 루트에 대해 heapify 수행 heapify(arr, i, 0); } }

int main() { std::vector<int> arr = {5, 3, 1, 8, 7, 2, 4}; std::cout << "정렬 전: "; for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; heapSort(arr); std::cout << "정렬 후: "; for (int num : arr) { std::cout << num << " "; } std::cout << std::endl; return 0; }