실전 알고리즘 0x0F강 - 정렬2

정렬2

[ Counting Sort ] O(N+K)

- 필요한 공간이 한정되어 있는 경우에만 쓰는것이 좋다. 이론적으로 1억까지 사용 가능하나 1000만까지 쓴다고 생각!

 

[ Radix Sort ] O(D(N+K))

- 기수 정렬

- 자리수를 이용한 정렬으로 Counting Sort의 응용이다.

- 1의 자리수를 0~9까지 배열에 넣고 순서대로 꺼내어 정렬해주고 다음에는 10의 자리수를 0~9까지 배열에 넣고 순서대로 꺼내는 과정을 반복한다.

- 최악의 경우 숫자들이 배열의 한 인덱스에 몰릴 수 있어서 공간낭비가 심하다. 그래서 vector와 같은 동적 배열, 연결 리스트로 만들어야 하는데 STL이 없으면 구현이 까다롭고 STL을 쓸 수 있으면 STL sort를 사용하면 된다.

 

- Comparison Sort : 버블 소트, 머지 소트, 퀵 소트

- Non-comparison Sort : 카운팅 소트, 라딕스 소트

 

[ STL sort ]

- 코딩테스트에서 정렬을 직접 짜고있으면 흑우다.

int a[5] = {1, 4, 5, 2, 7};
sort(a, a+5);

vector<int> b = {1, 4, 5, 2, 7};
sort(b.begin(), b.end()); // or sort(b.begin(), b.begin()+5);

- 퀵 소트를 기반으로 하고 깊이가 깊어지면 O(N logN)이 보장되는 정렬로 처리한다.

- stable sort가 아니다. 필요하면 stable_sort 함수를 사용한다. (사용방법 동일)

- pair, tuple는 앞의 원소를 비교하고 값이 같으면 다음 원소의 대소를 비교한다.

- 5로 나눈 나머지 순으로 같으면 크기 순으로 정렬할 수 있다.

bool cmp(int a, int b){
	if(a%5 != b%5) return a%5 < b%5;
    retrun a < b;
}
int a[7] = {1, 2, 3, 4, 5, 6, 7};
sort(a, a+7, cmp);

- 주의사항

1. 비교 함수는 두 값이 같을 때(혹은 우선순위가 같을 때) false를 반환한다.

bool cmp(int a, int b){
	if(a >= b) return true;
    return false;
} // 두 값이 같을 때 런타임에러 발생

bool cmp(int a, int b){
	return a > b;
} // 수정 후

2. 비교 함수의 인자로 STL 혹은 클래스 객체 전달시 reference를 사용한다.

bool cmp(string a, string b){
	return a.back() < b.back();
} //함수로 인자를 불러오면서 불필요한 복사를 하므로 답은 맞지만 시간이 더 소요된다.

bool cmp(const string& a, const string& b){
	retunr a.back() < b.back();
} // 수정 후

 

[ 정렬의 응용 ]