선택 정렬 (Selection Sort)은 가장 작은 원소를 한 개 찾아 맨 앞에 두고, 남은 원소 중 도 가장 작은 것을 찾아 두 번째에 두면서 계쏙 진행하여 결국 모든 원소들을 정렬하는 알고리즘이다.
맨 처음 N 개에서 원소를 찾고, 다음으로 N - 1 개에서, 다음은 N - 2 개의 순서로 원소를 찾는다.
O(N^2) 의 시간복잡도를 갖는다.
#include <iostream>
#include <vector>
void SelectionSort(std::vector<int>& _Arr)
{
int N = static_cast<int>(_Arr.size());
for (int i = N - 1; i > 0; --i)
{
int MaxIdx = 0;
for (int j = 0; j <= i; ++j)
{
if (_Arr[MaxIdx] < _Arr[j])
MaxIdx = j;
}
std::swap(_Arr[MaxIdx], _Arr[i]);
}
}
int main(void)
{
std::vector<int> Arr = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 };
SelectionSort(Arr);
for (int Num : Arr)
std::cout << Num << ' ';
return 0;
}
0 1 2 3 4 5 6 7 8 9
삽입 정렬 (Insertion Sort) 은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 부분과 비교하여
자신의 위치를 찾아 삽입하여 정렬하는 알고리즘이다. O(N^2)의 시간복잡도를 갖는다.
#include <iostream>
#include <vector>
void InsertionSort(std::vector<int>& _Arr)
{
int N = static_cast<int>(_Arr.size());
for (int i = 1; i < N; ++i)
{
int Temp = _Arr[i], j = 0;
for (j = i - 1; j >= 0; --j)
{
if (_Arr[j] <= Temp)
break;
_Arr[j + 1] = _Arr[j];
}
_Arr[j + 1] = Temp;
}
}
int main(void)
{
std::vector<int> Arr = { 6, 5, 3, 1, 8, 7, 2, 4 };
InsertionSort(Arr);
for (int Num : Arr)
std::cout << Num << ' ';
return 0;
}
1 2 3 4 5 6 7 8
버블 정렬(Bubble Sort) 은 맨 왼쪽 원소부터 바로 이웃한 오른쪽 원소와 비교해가며 큰 수가 오른쪽으로
가도록 교환하여 정렬하는 알고리즘이다. O(N^2)의 시간복잡도를 갖는다.
#include <iostream>
#include <vector>
void BubbleSort(std::vector<int>& _Arr)
{
int N = static_cast<int>(_Arr.size());
for (int i = N - 1; i > 0; --i)
{
for (int j = 0; j < i; ++j)
{
if (_Arr[j] > _Arr[j + 1])
std::swap(_Arr[j], _Arr[j + 1]);
}
}
}
int main(void)
{
std::vector<int> Arr = { 5, 2, 6, 1, 3, 7, 4 };
BubbleSort(Arr);
for (int Num : Arr)
std::cout << Num << ' ';
return 0;
}
1 2 3 4 5 6 7
병합 정렬 (Merge Sort) 이란 배열을 더 이상 쪼개지지 않을때까지 작은 크기로 분할하여, 작은 배열끼리 비교 하는 과정을 수행한 후 하나의 배열로 합치는 과정을 통해 정렬하는 알고리즘이다.
분할 정복 알고리즘을 이용하며, O(N*logN)의 시간복잡도를 갖는다.
#include <iostream>
#include <vector>
// 병합
void Merge(std::vector<int>& _Arr, int _Left, int _Right)
{
int Size = _Right - _Left + 1, Idx = 0;
std::vector<int> Temp(Size, 0);
int Mid = (_Left + _Right) / 2;
int L = _Left, R = Mid + 1;
while (L <= Mid && R <= _Right)
{
if (_Arr[L] <= _Arr[R])
Temp[Idx++] = _Arr[L++];
else
Temp[Idx++] = _Arr[R++];
}
int Remain = (L <= Mid) ? L : R;
while (Idx < Size)
Temp[Idx++] = _Arr[Remain++];
for (int i = _Left, k = 0; i <= _Right; ++i, ++k)
_Arr[i] = Temp[k];
}
// 분할
void Divide(std::vector<int>& _Arr, int _Left, int _Right)
{
if (_Left < _Right)
{
int Mid = (_Left + _Right) / 2;
Divide(_Arr, _Left, Mid);
Divide(_Arr, Mid + 1, _Right);
Merge(_Arr, _Left, _Right);
}
}
void MergeSort(std::vector<int>& _Arr)
{
Divide(_Arr, 0, _Arr.size() - 1);
}
int main(void)
{
std::vector<int> Arr = { 6, 5, 3, 1, 8, 7, 2, 4 };
MergeSort(Arr);
for (int Num : Arr)
std::cout << Num << ' ';
return 0;
}
1 2 3 4 5 6 7 8
퀵 정렬 (Quick Sort) 은 분할정복 패러다임을 기반으로한 정렬 알고리즘이다.
한 부분배열에서 pivot 을 정한 후 pivot 보다 작은 수를 왼쪽으로, 큰 수를 오른쪽으로 놓는 과정을 재귀적으로 수행하여 정렬한다.
퀵 정렬에서 대부분의 시간을 차지하는 것은 배열을 pivot 값을 기준으로 부분 배열로 나누는 과정이다.
퀵정렬의 경우 나눠지는 두 부분 배열이 비슷한 크기로 나눠진다고 보장할 수 없다.
따라서 만약 기준 값이 배열의 최소 또는 최대값일 경우 부분 배열의 크기가 1씩만 줄어드는 현상이 발생하고,
이런 최악의 경우 O(N^2) 의 시간 복잡도를 갖는다.
최악의 경우를 피하기위해 퀵 정렬은 중간값에 가까운 pivot 을 선택하는 방법을 적용하여 평균적으로 빠른
속도를 낼 수 있고, O(N*logN) 의 시간 복잡도를 갖는다.
또한 퀵 정렬은 같은 시간 복잡도를 갖는 다른 정렬 알고리즘에 비해 빠른 속도를 보이는데, 데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 병합정렬처럼 별도의 메모리 공간이 필요하지 않기 때문이다.
#include <iostream>
#include <vector>
void QuickSort(std::vector<int>& _Arr, int _Left, int _Right)
{
// 원소가 1개인 경우 반환
if (_Left >= _Right)
return;
int Pivot = _Left; // Pivot : 첫번째 원소
int L = _Left + 1, R = _Right;
while (L <= R)
{
// Pivot 보다 큰 값 찾기
while (L <= _Right && _Arr[L] <= _Arr[Pivot])
++L;
// Pivot 보다 작은 값 찾기
while (R > _Left && _Arr[R] >= _Arr[Pivot])
--R;
if (L > R) // 엇갈린 상태
std::swap(_Arr[R], _Arr[Pivot]);
else // 엇갈리지 않은 상태
std::swap(_Arr[L], _Arr[R]);
}
QuickSort(_Arr, _Left, R - 1);
QuickSort(_Arr, R + 1, _Right);
}
int main()
{
std::vector<int> Arr = { 38, 27, 43, 9, 3, 82, 10 };
QuickSort(Arr, 0, Arr.size() - 1);
for (int Num : Arr)
std::cout << Num << ' ';
return 0;
}
3 9 10 27 38 43 82
카운팅 정렬 (Counting Sort) 은 정렬할 수의 범위가 작은 경우 사용하는 정렬으로, 시간 복잡도가 O(N) 인
매우 빠른 정렬이다.
그러나 수의 범위가 커지면 사용하는 메모리도 그만큼 커지기 때문에 비효율적인 알고리즘에 되므로 수의 범위가 작은 경우에 효율적인 알고리즘이다.
카운팅 정렬의 원리는 간단하다. 정렬할 원소를 하나씩 살펴보고, 그 원소 값에 해당하는 배열에 카운트를
1 증가하면 된다.
#include <iostream>
#include <vector>
void CountingSort(const std::vector<int>& _Arr, std::vector<int>& _Count)
{
for (int Num : _Arr)
++_Count[Num];
}
int main()
{
std::vector<int> Arr = { 5, 2, 3, 1, 4, 2, 3, 5, 1, 7 };
std::vector<int> Count(10, 0);
CountingSort(Arr, Count);
for (int i = 0; i < static_cast<int>(Count.size()); ++i)
{
if (0 < Count[i])
{
for (int j = 0; j < Count[i]; ++j)
std::cout << i << ' ';
}
}
return 0;
}
1 1 2 2 3 3 4 5 5 7
기수 정렬 (Radix Sort) 은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘
으로, 자리수가 고정되어있으니 안정성이 있고, O(N) 의 시간 복잡도를 갖는다.
그러나 '버킷' 이라는 적지 않은 용량의 추가적인 메모리 공간이 필요하다는 단점이 있고, 버킷에 담고 빼는 과정도 양이 많아진다면 시간이 많이 필요하여 적용 범위가 한정적이다.
1의 자리수부터 진행. 배열의 각 원소에 대해 1의 자리수를 비교해 버킷에 삽입한 후 버킷의 왼쪽부터 오른쪽으로 모든 값들을 빼서 배열에 넣는다.
2의 자리수에대해 진행한 모습.
3의 자리수에대해 진행한 모습.
4의 자리수에대해 진행한 모습.
#include <iostream>
#include <vector>
#include <queue>
// 해당 자리수 구하기
int GetDigit(int _Num, int _Digit)
{
for (int i = 1; i < _Digit; ++i)
_Num /= 10;
return (_Num % 10);
}
void RadixSort(std::vector<int>& _Arr)
{
// 최대값 구하기
int MaxNum = 0;
for (int Num : _Arr)
{
if (MaxNum < Num)
MaxNum = Num;
}
// 최대 자리수 구하기
int MaxDigits = 0;
while (0 != MaxNum)
{
++MaxDigits;
MaxNum /= 10;
}
// queue 이용
std::queue<int> Q[10];
for (int i = 1; i <= MaxDigits; ++i)
{
for (int j = 0; j < static_cast<int>(_Arr.size()); ++j)
Q[GetDigit(_Arr[j], i)].push(_Arr[j]);
int ArrIdx = 0;
for (int j = 0; j < 10; ++j)
{
while (!Q[j].empty())
{
_Arr[ArrIdx++] = Q[j].front();
Q[j].pop();
}
}
}
}
int main()
{
std::vector<int> Arr = { 1592, 204, 368, 1, 72 };
RadixSort(Arr);
for (int Num : Arr)
std::cout << Num << ' ';
return 0;
}
1 72 204 368 1592