오늘은 정렬 알고리즘에 대해 알아보도록 하자.
내림차순은 비교하는 부분에서 부호만 바꿔주면 되기 때문에 오름차순을 기준으로 설명하려고 한다.
📌 선택 정렬 (Selection Sort)
선택 정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 두 번째 데이터와 바꾸고... 이런 과정을 반복해 정렬하는 방법이다.
#include "iostream"
using namespace std;
int main() {
int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 0; i < 9; i++) {
int minIdx = i;
for (int j = i + 1; j < 10; j++) {
if (arr[minIdx] > arr[j]) minIdx = j;
}
swap(arr[minIdx], arr[i]);
}
for (int i = 0; i < 10; i++) {
cout << arr[i] << " ";
}
}
📌 삽입 정렬 (Insertion Sort)
선택 정렬은 알고리즘 문제 풀이에 사용하기에는 느린 편이다. 삽입 정렬은 선택 정렬에 비해 실행 시간 측면에서 더 효율적인 알고리즘으로 알려져 있다. 특히, 필요할 때만 위치를 바꾸기 때문에 '데이터가 거의 정렬되어 있을 때' 훨씬 효율적이다.
삽입 정렬은 특정한 데이터를 적절한 위치에 삽입하는데, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다는 점이 특징이다.
#include "iostream"
using namespace std;
int main() {
int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
for (int i = 1; i < 10; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j-1]) swap(arr[j], arr[j-1]);
else break;
}
}
for(int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
}데이터가 거의 정렬되어 있는 최선의 경우 O(N)의 시간복잡도를 가지기 때문에 이 경우 퀵 정렬 알고리즘보다 더 강력하다.
📌 퀵 정렬 (Quick Sort)
퀵 정렬은 병합 정렬 알고리즘과 마찬가지로 가장 많이 사용되는 알고리즘 중 하나이다.
퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.
여기서 큰 숫자와 작은 숫자를 교환할 때 사용되는 기준을 피벗(Pivot)이라고 한다.
피벗을 설정하고 리스트를 분할하는 방법에 따라서 퀵 정렬을 여러가지 방식으로 구분하는데, 여기서는 호어 분할 방식(Hoare Partition)을 기준으로 설명한다.
- 리스트에서 첫 번째 데이터를 피벗으로 정한다.
- 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.
- 큰 데이터와 작은 데이터의 위치를 교환한다.
- 2, 3번을 반복하다가 큰 데이터의 인덱스가 작은 데이터의 인덱스보다 커지면(엇갈리면) 멈춘다.
- 작은 데이터와 피벗을 교환한다.
- 피벗을 기준으로 왼쪽과 오른쪽을 분할한다.
- 각 분할된 리스트마다 1~6을 반복한다. (재귀, 리스트의 데이터 개수가 1이면 종료)
#include "iostream"
using namespace std;
void quickSort(int* arr, int start, int end) {
if (start >= end) return;
int pivot = start;
int left = start + 1;
int right = end;
while (left <= right) {
while (left <= end && arr[left] <= arr[pivot]) left++;
while (right > start && arr[right] >= arr[pivot]) right--;
if (left > right) swap(arr[pivot], arr[right]);
else swap(arr[left], arr[right]);
}
quickSort(arr, start, right-1);
quickSort(arr, right+1, end);
}
int main() {
int arr[] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, 9);
for (int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
}호어분할 방식으로 했을 때의 퀵 정렬은 '이미 데이터가 정렬되어 있는 경우'에 매우 느리게 동작한다.
그래서 실제로 C++과 같이 퀵 정렬을 기반으로 작성된 정렬 라이브러리를 제공하는 프로그래밍 언어들은 최악의 경우에도 시간 복잡도가 O(NlogN)을 보장할 수 있도록 피벗값 설정 로직을 추가해 구현되어 있다.
📌 계수 정렬 (Count Sort)
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만, 매우 빠른 정렬 알고리즘이다.
'데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다.
계수 정렬이 이러한 특징을 가지는 이유는 '모든 범위를 단을 수 있는 크기의 리스트'를 선언해야 하기 때문이다.
#include "iostream"
#define MAX_VALUE 9
using namespace std;
int main() {
int n = 15;
int arr[15] = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
int cnt[MAX_VALUE + 1];
for (int i = 0; i < n; i++) {
cnt[arr[i]]++;
}
for (int i = 0; i <= MAX_VALUE; i++) {
for (int j = 0; j < cnt[i]; j++) {
cout << i << ' ';
}
}
}계수 정렬은 현존하는 정렬 알고리즘 중에서 기수 정렬(Radix Sort)와 더불어 가장 빠르다고 볼 수 있다.
하지만 계수 정렬은 때에 따라서 심각한 메모리 비효율성을 초래할 수 있다. 데이터가 0과 999,999만 있는 경우가 그 예이다. 따라서, 계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 적합하다.
📌 시간복잡도 비교
| Selection Sort | Insertion Sort | Quick Sort | Count Sort | |
| Normal | O(N^2) | O(N^2) | O(NlogN) | O(N+K) |
| Best | O(N^2) | O(N) | O(N+K) | |
| Worst | O(N^2) | O(N^2) | O(N^2) | O(N+K) |
