목록전체 글 (158)
Nagie's DevStory
std::stable_sort는 C++ 표준 라이브러리(STL)에서 제공하는 정렬을 수행하는 함수이며, 헤더에 정의되어 있다. std::sort와 사용법은 동일하지만, std::stable_sort는 안정성을 유지하면서 정렬하기에 요소의 상대적인 순서가 중요하다면 std::sort 대신 std::stable_sort를 사용해야 한다. 다음은 std::stable_sort의 사용 예시이다. #include #include #include int main() { std::vector nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5}; std::stable_sort(nums.begin(), nums.end()); for (const auto& e : nums) { std::cout
std::sort는 C++ 표준 라이브러리(STL)에서 제공하는 정렬을 수행하는 함수이며, 헤더에 정의되어 있다. 기본적으로 오름차순 정렬을 하며, 퀵 정렬(Quick Sort)이나 병합 정렬(Merge Sort)과 같은 알고리즘으로 구현되어 있다. 기본적인 사용 방법은 다음과 같다. #include #include int main() { int arr[] = { 4, 2, 5, 1, 3 }; std::sort(arr, arr + 5); for (const auto& e : arr) { std::cout
퀵 정렬(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. 안정성 : 동일한 키 값을 가진 원소 간..