int main()
{
vector<int> v;
srand(static_cast<unsigned int>(time(NULL)));
for (int i = 0; i < 10; i++)
v.push_back(rand() % 100);
BubbleSort(v);
SelectionSort(v);
InsertSort(v);
ShellSort(v);
HeapSort(v);
MergeSort(v, 0, v.size() - 1);
QuickSort(v, 0, v.size() - 1);
std::sort(v.begin(), v.end(), [=](int a, int b) -> bool {return a > b; });
}
1. Bubble Sort
- 서로 인접한 두 데이터를 비교하여 정렬하는 알고리즘
- 코드 구현이 단순하고 쉽지만 느림
- 시간 복잡도 : O(n2)
void BubbleSort(vector<int>& v)
{
const int size = v.size();
for (int i = 0; i < size - 1; i++)
for (int j = 0; j < size - 1 - i; j++)
// j와 j + 1의 데이터 비교해서 큰 값이 나오면 교환
if (v[j] > v[j + 1])
std::swap(v[j], v[j + 1]);
}
2. Selection Sort
- 가장 작은 값의 데이터들로 부터 차례대로 선택하여 위치를 교환하는 알고리즘
- 코드 구현이 단순하고 버블 정렬 및 삽입 정렬보다 교환 횟수가 적음
- 시간 복잡도 : O(n2)
void SelectionSort(vector<int>& v)
{
const int size = v.size();
for (int i = 0; i < size - 1; i++)
{
int idx = i;
for (int j = i + 1; j < size; j++)
// idx와 j의 데이터를 비교하여 작은 값이 나오면 idx에 저장
if (v[idx] > v[j]) idx = j;
std::swap(v[i], v[idx]);
}
}
3. Insert Sort
- 배열의 앞에서부터 차례대로 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬하는 알고리즘
- 코드 구현이 단순하고 대부분 이미 정렬이 되어있을 경우 매우 효율적임
- 대부분 이미 정렬되어 있는 경우 시간 복잡도 : O(n)
- 배열이 역순으로 정렬되어 있는 경우 시간 복잡도 : O(n2)
void InsertSort(vector<int>& v)
{
const int size = v.size();
for (int i = 1; i < size; i++)
for (int j = i; j > 0; j--)
if (v[j] < v[j - 1]) std::swap(v[j], v[j - 1]);
}
4. Shell Sort
- 삽입정렬을 보완한 알고리즘
- 데이터 삽입 위치가 현재 위치에 멀리 떨어진 곳이면 많은 이동을 해야함
- 삽입 정렬과 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬X
- 삽입 정렬과 다르게 간격(gap)을 사용
- 초기값은 간격의 절반, 간격은 홀수, 간격이 0이 되면 종료
- 평균 시간 복잡도 : O(n1.5)
void InsertGapSort(vector<int>& v, int gap)
{
const int size = v.size();
for (int i = gap; i < size; i = i + gap)
for (int j = i; j > 0; j = j - gap)
if (v[j] < v[j - gap]) std::swap(v[j], v[j - gap]);
}
void ShellSort(vector<int>& v)
{
int gap = v.size();
while (gap) // 0이 되면 종료
{
// gap - 홀수
gap = (gap % 2 == 0) ? (gap / 2) + 1 : (gap / 2);
// 부분 리스트의 개수는 gap과 같음
for (int i = 0; i < gap; i++)
InsertGapSort(v, gap); // 삽입 정렬 + gap
}
}
5. Heap Sort
- 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
- 시간 복잡도가 좋고, 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 유용
- 시간 복잡도 : O(nlog2n)
void HeapSort(vector<int>& v)
{
priority_queue<int, vector<int>, greater<int>> pq;
for (auto number : v) pq.push(number);
v.clear();
while (pq.empty() == false) { v.push_back(pq.top()); pq.pop(); }
}
6. Merge Sort
- 분할 정복 알고리즘
- 문제를 작은 2개의 문제로 분리하고 각각을 해결, 결과를 모아서 원래의 문제를 해결하는 전략
- 순환 호출 사용
- 안정 정렬
- 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일
- 시간 복잡도 : O(nlog2n)
void Merge(vector<int>& v, int left, int mid, int right)
{
int Left = left;
int Right = mid + 1;
vector<int> temp;
while (Left <= mid && Right <= right)
{
// 크기 비교
if (v[Left] <= v[Right]) temp.push_back(v[Left++]);
else temp.push_back(v[Right++]);
}
while (Left <= mid) { temp.push_back(v[Left++]);} // 남은 left값 추가
while (Right <= right) { temp.push_back(v[Right++]);} // 남은 right값 추가
for (int i = 0; i < temp.size(); i++) v[left + i] = temp[i]; // vector 초기화
}
void MergeSort(vector<int>& v, int left, int right)
{
if (left >= right) return;
int mid = (left + right) / 2; // 분할
MergeSort(v, left, mid); // 정복
MergeSort(v, mid + 1, right); // 정복
Merge(v, left, mid, right); // 합병
}
7. Quick Sort
- 불안정 정렬 및 비교 정렬
- 분할 정복 알고리즘
- 매우 빠른 속도 및 비균등 분할
- 추가 메모리 공간을 필요로 하지 않으나 정렬된 리스트에 대해 수행시간이 더 오래 걸림
- 최선의 경우 시간 복잡도 : O(nlog2n)
- 최악의 경우 시간 복잡도 : O(n2)
- 하나의 리스트를 pivot을 기준으로 두 개의 비균등한 크기로 분할
- 정렬할 리스트의 가장 왼쪽 데이터 → pivot
- low, high를 이용하여 리스트를 두 개의 부분 리스트로 나눔
- low 값이 올라가면서 pivot보다 큰 데이터가 있으면 멈춤
- high 값이 내려가면서 pivot보다 작은 데이터가 있으면 멈춤
- low, high 값을 교환 → low < high 일때 까지 반복
int Partition(vector<int>& v, int left, int right)
{
int pivot = v[left];
int low = left + 1;
int high = right;
while (low <= high)
{
while (low <= right && pivot >= v[low]) { low++; }
while (high >= left + 1 && pivot <= v[high]) { high--; }
if (low < high) std::swap(v[low], v[high]);
}
std::swap(v[left], v[high]);
return high;
}
void QuickSort(vector<int>& v, int left, int right)
{
if (left >= right) return;
int pivot = Partition(v, left, right); // 분할
QuickSort(v, left, pivot - 1); // 정렬
QuickSort(v, pivot + 1, right); // 정렬
}
8. Radix Sort
- 낮은 자리수부터 비교하여 정렬하는 알고리즘
- 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요
이름 | 최선 | 평균 | 최악 | 공간 |
버블 정렬 | O(n2) | O(n2) | O(n2) | O(n) |
선택 정렬 | O(n2) | O(n2) | O(n2) | O(n2) |
삽입 정렬 | O(n2) | O(n) | O(n2) | O(n2) |
셀 정렬 | O(n1.5) | O(n1.5) | O(n1.5) | O(n) |
힙 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(nlogn) |
합병 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(nlogn) |
퀵 정렬 | O(nlogn) | O(nlogn) | O(n2) | O(nlogn) |
기주 정렬 | O(dn) | O(dn) | O(dn) | - |
'C++ Algorithm & Study > C++ & Algorithm Strategies' 카테고리의 다른 글
[Programmers] 디펜스 게임 (0) | 2022.12.15 |
---|---|
[C++] 14 - 기초 문법 공부 일지(Smart Pointer) (0) | 2022.12.11 |
[C++] 12 - 기초 문법 공부 일지(STL) (0) | 2022.12.06 |
[C++] 11 - 기초 문법 공부 일지(MAP) (0) | 2022.12.06 |
[C++] 10 - 기초 문법 공부 일지(Tree) (0) | 2022.12.05 |