정렬 알고리즘
버블 정렬(Bubble sort)
버블 정렬 또는 거품 정렬은 정렬 알고리즘 중 하나이다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.
#include <iostream>
#include <vector>
#include <algorithm> // std::swap
using namespace std;
// 버블 정렬: 인접한 두 수를 비교해가며 큰 수를 뒤로 보냄
void bubble_sort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
// 마지막 i개는 이미 정렬되어 있으므로 n-1-i까지만 비교
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr[j], arr[j + 1]);
}
}
}
}선택정렬(Selection sort)
선택 정렬은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.
- 주어진 리스트 중에 최소값을 찾는다.
- 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
- 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.
선택 정렬은 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다.
#include <iostream>
#include <vector>
#include <algorithm> // std::swap
using namespace std;// 선택 정렬: 매번 가장 작은(또는 큰) 값을 찾아 현재 위치에 배치
void selection_sort(vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n - 1; i++) {
int min_idx = i;
// i 이후의 요소 중 최소값 찾기
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
swap(arr[i], arr[min_idx]);
}
}
삽입정렬(Insertion Sort)
삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.
선택 정렬이 버블 정렬과 같은 O(n2) 알고리즘에 비교하여 빠르며, 안정 정렬이고 in-place 알고리즘이다
#include <iostream>
#include <vector>
#include <algorithm> // std::swap
using namespace std;
// 삽입 정렬: 앞에서부터 하나씩 정렬된 위치에 삽입
void insertion_sort(vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// 정렬된 영역에서 key보다 큰 값들은 뒤로 밀기
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// key를 적절한 위치에 삽입
arr[j + 1] = key;
}
}
Quick Sorting 퀵 정렬
퀵 정렬(Quicksort)은 범용 정렬 알고리즘이다.
다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.
퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고(그 이유는 메모리 참조가 지역화되어 있기 때문에CPU캐시의 히트율이 높아지기 때문이다.), 대부분의 실질적인 데이터를 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계하는 것이 가능하다. 또한 매 단계에서 적어도 1개의 원소가 자기 자리를 찾게 되므로 이후 정렬할 개수가 줄어든다. 때문에 일반적인 경우 퀵 정렬은 다른 O(n log n) 알고리즘에 비해 훨씬 빠르게 동작한다. 이러한 이유로 퀵소트(빠른정렬)라는 이름의 기원이 되었다. 그리고 퀵 정렬은 정렬을 위해 평균적으로 O(log n)만큼의 memory를 필요로한다. 이는 재귀적 호출로 발생하는 것이며, 최악의 경우 O(n)의 공간복잡도를 보인다.
원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있어 불안정 정렬에 속한다.
#include <iostream>
#include <vector>
#include <algorithm> // std::swap
using namespace std;
// 파티션 함수: 피벗을 기준으로 정렬
int partition(vector<int>& list, int left, int right) {
int pivot = list[left];
int low = left + 1;
int high = right;
while (low <= high) {
while (low <= right && list[low] < pivot) low++;
while (high >= left && list[high] > pivot) high--;
if (low < high) {
swap(list[low], list[high]);
}
}
swap(list[left], list[high]);
return high;
}
// 퀵 정렬 함수
void quick_sort(vector<int>& list, int left, int right) {
if (left < right) {
int pivotIndex = partition(list, left, right);
quick_sort(list, left, pivotIndex - 1);
quick_sort(list, pivotIndex + 1, right);
}
}
int main() {
vector<int> list = {5, 3, 8, 4, 9, 1, 6, 2, 7};
quick_sort(list, 0, list.size() - 1);
for (int num : list) {
cout << num << '\n';
}
return 0;
}
5. Merge Sorting 병합 정렬
알고리즘
병합 정렬은 정렬 대상을 2개의 배열로 쪼갠 다음, 각각 정렬시킨 다음 큰 정렬된 배열로 다시 합치는 것을 말한다. 이때 배열을 쪼개어 정렬한 뒤 합치는 작업을 재귀적으로 수행한다면, 최종적으로 배열이 정렬된다는 것이다. 크기가 N인 배열을 정렬하는데 NlogN이 소요된다.
재귀적으로 구현한다는 것은 분할정복 패러다임 (문제를 잘게 쪼개어 각 부분을 해결한뒤 다시 전체 문제를 해결)을 사용한다는 것이다. 아래에서 살펴보겠지만, 분할정복은 다시 하향식 (top-down)으로 구현하는 방법과, 상향식 (bottom-up)으로 구현방법이 나뉜다.
하향식 병합 정렬 (Top-Down Merge Sort)
- 재귀(Recursion)를 이용하여 배열을 계속 반으로 나눈 뒤, 병합(Merge)하는 방식입니다.
- 재귀 호출이 많아 스택 메모리를 추가로 사용합니다.
#include <iostream>
using namespace std;
// 두 개의 정렬된 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // 왼쪽 부분 배열 크기
int n2 = right - mid; // 오른쪽 부분 배열 크기
int L[n1], R[n2]; // 임시 배열 생성
// 데이터 복사
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
// 병합 과정
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
// 남은 요소 복사
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 하향식 병합 정렬 함수 (재귀)
void mergeSortTopDown(int arr[], int left, int right) {
if (left >= right) return; // 배열 크기가 1 이하이면 종료
int mid = left + (right - left) / 2; // 중앙값 찾기
mergeSortTopDown(arr, left, mid); // 왼쪽 부분 정렬
mergeSortTopDown(arr, mid + 1, right); // 오른쪽 부분 정렬
merge(arr, left, mid, right); // 정렬된 두 부분 병합
}
// 테스트 코드
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "정렬 전: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
mergeSortTopDown(arr, 0, n - 1);
cout << "정렬 후: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}
상향식 병합 정렬 (Bottom-Up Merge Sort)
- 반복문(Iteration)을 사용하여 작은 부분 배열부터 병합해 나가는 방식입니다.
- 재귀 호출을 사용하지 않아 스택 메모리를 절약할 수 있습니다.
상향식 병합 정렬 C++ 코드
#include <iostream>
using namespace std;
// 두 개의 정렬된 부분 배열을 병합하는 함수
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2];
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int i = 0; i < n2; i++) R[i] = arr[mid + 1 + i];
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 상향식 병합 정렬 함수 (반복문 사용)
void mergeSortBottomUp(int arr[], int n) {
for (int size = 1; size < n; size *= 2) { // 부분 배열 크기를 1, 2, 4, 8... 배로 증가
for (int left = 0; left < n - size; left += 2 * size) {
int mid = left + size - 1;
int right = min(left + 2 * size - 1, n - 1);
merge(arr, left, mid, right);
}
}
}
// 테스트 코드
int main() {
int arr[] = {38, 27, 43, 3, 9, 82, 10};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "정렬 전: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
mergeSortBottomUp(arr, n);
cout << "정렬 후: ";
for (int i = 0; i < n; i++) cout << arr[i] << " ";
cout << endl;
return 0;
}
하향식 vs. 상향식 비교
| 비교 항목 | 하향식 (Top-Down) | 상향식 (Bottom-Up) |
| 방식 | 재귀(Recursion) | 반복문(Iteration) |
| 메모리 사용 | 추가적인 재귀 호출 스택 사용 | 추가 스택 사용 없음 |
| 구현 난이도 | 상대적으로 쉬움 | 상대적으로 어려움 |
| 시간 복잡도 | O(n log n) | O(n log n) |
| 공간 복잡도 | O(n) (추가 배열 필요) | O(n) (추가 배열 필요) |
| 특징 | DFS(깊이 우선 탐색) 방식 | BFS(너비 우선 탐색) 방식 |
재귀 호출이 이해하기 쉽다면 하향식(Top-Down)을 사용하는 것이 좋습니다.
스택 메모리 사용을 줄이고 싶다면 상향식(Bottom-Up)을 고려하는 것이 좋습니다.
📌 실무에서는 일반적으로 하향식이 더 많이 사용됩니다.
힙정렬(Heap Sort)
완전 이진트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬 방식으로 불안정 정렬에 속한다.
최대 힙의 루트가 원소의 최댓값이라는 점을 활용하여 정렬을 수행하는 방법이다.
루트를 제외한 힙이 재정렬되는 과정이 반복되면서 정렬이 이루어진다.
성능이 좋고 가장 큰 값이나 가장 작은 값을 구할 때 유용하다.
하지만 데이터의 상태에 따라 같은 O(nlogn) 시간 복잡도 라도 조금 느리고 불안정 정렬이다.
시간복잡도는 최선, 평균, 최악 모두 O(n log n) 공간 복잡도는 O(n) 이다.
int arr[1000000];
void swap(int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void makeheap(int root, int n){
int temp = arr[root]; // 해당 부모 노드
int child = root * 2; // 왼쪽 자식 노드
while(child <= n){
// 더 큰 자식 노드 찾기
if(child<n && arr[child] < arr[child+1])
child++;
if(temp < arr[child]){ // 자식 노드가 더 클 경우
arr[child/2] = arr[child];
child *=2; // 레벨 낮추기
}
else break;
}
arr[child/2] = temp;
}
void heapsort(int n){
// 최대 힙 구성
for(int i = n / 2; i > 0; i--){
makeheap(i, n);
}
int temp;
for(int i = n; i > 0; i--){
swap(1, i);
makeheap(1, i - 1);
}
}
