[알고리즘 공부] 실전 알고리즘 15강-정렬2

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

Counting Sort

시간복잡도는 O(n)이며 수의 범위가 제한되어 있을때는 counting sort을 통해 구현을 할만하다.

#include <bits/stdc++.h>
using namespace std;

int arr[2000002];
int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, num;
	cin >> n;
	
	for(int i = 0; i < n; ++i)
	{
		cin >> num;
		arr[num + 1000000]++;
	}

	for (int i = 0; i < 2000002; ++i)
	{
		while(arr[i]--) 
			cout << i - 1000000 << ' ';
	}
}

Radix Sort

1의자리 비교.. 10의자리 비교.. 100의자리 비교.. 10^n-1자리 비교.. 해서 정렬하는 방식
시간복잡도는 O(n)

---

merge, quick, bubble vs counting radix

Comparison Sort vs Non-comparision Sort

Comparison Sort인 merge, quick, bubble은 원소들끼리 크기를 비교하는 과정이 있었는데
Non-comparision Sort인 counting, radix은 비교하는 과정이 없다

---

STL sort

STL sort는 quick sort 기반이면 최악의 경우에도 O(nlogn)을 보장한다.

vector<int> a = {1, 5, 4, 3, 2};
sort(a.begin(), a.end()); 

동일한 우선순위를 가진 원소들의 순서를 기존 순서로 정렬할때는 stable sort를 사용하면 된다.