목록ComputerScience (34)
Nagie's DevStory
퀵 정렬(Quick Sort)은 토니 호어가 1960년에 개발한 평균적으로 빠른 속도를 가지는 정렬 알고리즘으로 분할 정복(Divide and Conquer) 방법을 사용하며, 배열을 피벗 기준으로 작은 요소들과 큰 요소들로 나누어 각각을 정렬 후 최종적으로 정렬된 부분을 합치는 방식을 사용한다. template int partition(std::vector& data, int left, int right) { T pivot = data[left]; int i = left + 1; int j = right; while (true) { while (data[i] left) { j--; } if (i < j) { std::swap(data[i], data[j]); } else { break; } } std:..
병합 정렬(Merge Sort)은 1945년 존 폰 노이만이 제안한 분할 정복(Divide and Conquer) 알고리즘의 일종으로, 정렬되지 않은 리스트를 반으로 나눈 후 각 부분을 재귀적으로 정렬하고, 정렬된 부분을 병합하여 전체 리스트를 정렬하는 방식을 취한다. 이 과정은 리스트의 길이가 1이 되거나 비어있을 때까지 반복되며, 안정적이면서 효율적인 정렬 방법으로 널리 사용된다. template void merge(std::vector& data, int left, int mid, int right) { int size = right - left + 1; std::vector buff(size); int i = left, j = mid + 1, k = 0; while (i
삽입 정렬(Insertion Sort)은 현재 위치에서 그 보다 앞(혹은 더 작은 값)의 원소들과 비교하여 자신이 들어갈 위치를 찾아 삽입하는 방식으로 동작하며, 정렬되지 않은 부분의 원소를 하나씩 정렬된 부분으로 삽입하면서 정렬이 완료된다. template void insertion_sort(std::vector& data) { //최악 O(n^2) int n = data.size(); for (int i = 1; i = 0 && data[j] > key) { data[j + 1] = data[j]; j--; } data[j + 1] = key; } } 특징 1. 안정성 : 동일한 키 값을 가진 원소 간..
선택 정렬(Selection Sort)은 리스트를 순회하면서 가장 작은 값을 찾아 리스트의 앞으로 옮기는 방식으로 동작한다. template void selection_sort(std::vector& data) { // O(n^2) int n = data.size(); for (int i = 0; i < (n - 1); i++) { int idx = i; for (int j = (i + 1); j < n; j++) { if (data[j] < data[idx]) { idx = j; } } std::swap(data[i], data[idx]); } } 특징 1. 간단한 구현 : 버블정렬과 같이 간단하게 구현할 수 있는 정렬 알고리즘이며, 반복문을 사용해 작은 값을 선택 후 앞으로 옮기는 방식으로 동작한다...
버블 정렬(Bubble Sort)은 리스트를 반복적으로 훑어가며 인접한 두 원소를 비교 후, 조건에 맞게 원소를 재배치해 정렬하는 알고리즘이다. 이 과정은 리스트가 정렬될 때까지 반복되며 더 작은 원소가 리스트의 위쪽으로 "거품처럼" 올라가는 모습에서 버블정렬이라고 이름을 지었다고 한다. template void bubble_sort(std::vector& data) { // O(n^2) int n = data.size(); for (int i = 0; i i; j--) { if (data[j] < data[j - 1]) { std::swap(data[j],data[j - 1]); } } } } 특징 1. 간단한 구현 : 버블..