정렬 알고리즘
- 정렬(Sorting) 이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다.
- 일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
💡선택 정렬
-
처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
-
선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞에 보낸다.
-
구현 방식에 따라 사소한 오차가 있을 수있으나, 전체 연산 횟수는 다음과 같다.
N + (N-1) + (N-2) + ... + 2
이때, 가장 마지막 원소는 정렬을 수행하지 않아도 되므로 1은 더하지 않는다. 이 연산은 (N^2 + N - 2) / 2 로 표현할 수 있으므로, 시간 복잡도는 O(N^2) 이다.
#include <iostream>
using namespace std;
int n = 10;
int target[10] = { 7,5,9,0,3,1,6,2,4,8 };
int main() {
for (int i = 0; i < n; i++) {
int min_index = i;
for (int j = i + 1; j < n; j++) {
if (target[min_index] > target[j]) {
min_index = j;
}
}
swap(target[i], target[min_index]);
}
for (int i = 0; i < n; i++) {
cout << target[i] << ' ';
}
return 0;
}💡삽입 정렬
-
처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.
-
선택정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.
-
시간 복잡도는 O(N^2) 이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
-
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.
- 최선의 경우 O(N)의 시간 복잡도를 가진다.
#include <iostream>
using namespace std;
int n = 10;
int target[10] = { 7,5,9,0,3,1,6,2,4,8 };
int main() {
for (int i = 1; i < n; i++) {
for (int j = i; j > 0; j--) {
if (target[j] < target[j - 1]) {
swap(target[j], target[j - 1]);
}
else break;
}
}
for (int i = 0; i < n; i++) {
cout << target[i] << ' ';
}
return 0;
}💡퀵 정렬
-
기준 데이터를 설정하고, 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
-
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나
-
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
-
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
-
퀵 정렬이 빠른 이유: 이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(NlogN)을 기대할 수 있다.
- 너비 X 높이 = N * logN = NlogN
-
퀵 정렬은 평균의 경우 O(NlogN)의 시간 복잡도를 가진다.
-
최악의 경우 O(N^2)의 시간 복잡도를 가진다.
- 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 대해 퀵 정렬을 수행하는 경우가 해당한다. 이 경우 분할이 수행되는 횟수가 N과 비례하고, 매번 선형탐색을 수행하므로 O(N^2)이 되는 것이다.
#include <iostream>
using namespace std;
int n = 10;
int target[10] = { 7,5,9,0,3,1,6,2,4,8 };
void quickSort(int* target, int start, int end) {
if (start >= end) return;
int pivot = start;
int left = start + 1;
int right = end;
while (left <= right) {
while (left <= end && target[left] <= target[pivot]) left++;
while (right > start && target[right] >= target[pivot]) right--;
if (left > right)
swap(target[pivot], target[right]);
else
swap(target[left], target[right]);
}
quickSort(target, start, right - 1);
quickSort(target, right + 1, end);
}
int main() {
quickSort(target, 0, n - 1);
for (int i = 0; i < n; i++)
cout << target[i] << ' ';
return 0;
}💡계수 정렬
-
특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘
- 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능
-
데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때 최악의 경우에도 수행 시간 O(N+K) 를 보장한다.
-
계수 정렬의 시간 복잡도와 공간 복잡도는 모두 O(N+k) 이다.
-
계수 정렬은 때에 따라서 심각한 비효율성을 초래할 수 있다.
- 데이터가 0과, 999,999로 단 2개만 존재하는 경우가 그렇다.
-
계수 정렬은 동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다.
#include <iostream>
#define MAX_VALUE 9
using namespace std;
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];
int main() {
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 << ' ';
}
}
return 0;
}요약
- 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다.
| 정렬 알고리즘 | 평균 시간 복잡도 | 공간 복잡도 | 특징 |
|---|---|---|---|
| 선택 정렬 | O(N^2) | O(N) | 아이디어가 매우 간단 |
| 삽입 정렬 | O(N^2) | O(N) | 데이터가 거의 정렬되어 있을 때는 가장 빠름 |
| 퀵 정렬 | O(NlogN) | O(N) | 대부분의 경우에 가장 적합하며, 충분히 빠름 |
| 계수 정렬 | O(N+k) | O(N+k) | 데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만, 매우 빠르게 동작함 |
