정렬 2

Counting Sort

Radix Sort

STL sort

배열 정렬 시 인자로 포인터 2개, vector 정렬 시 인자로 iterator 2개를 넘겨준다.

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()); // 또는 sort(b.begin(), b.begin()+5)

Quick sort를 기반으로 하지만 리스트가 불균등하게 쪼개지는 상황이 반복되어 재귀에서의 깊이가 너무 깊어지면 $O(NlogN)$이 보장되는 정렬 알고리즘으로 나머지를 처리하기 때문에 최악의 경우에도 시간복잡도는 $O(NlogN)$로 보장된다. 다만, stable sort가 아니므로 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않을 수 있기 때문에 stable sort가 꼭 필요하다면 stable_sort 함수를 사용한다.

참고

pair와 tuple은 먼저 가장 앞에 있는 원소의 대소를 비교하고, 값이 같으면 그 다음 원소의 대소를 비교하는 방식이다. ex. 좌표 정렬 or 기타 여러 속성이 있는 원소 정렬

비교함수로 정렬 기준 정하기

int형을 5로 나눈 나머지가 작은 순으로, 나머지가 같다면 크기가 작은 순으로 정렬해보자

bool cmp(int a, int b){
	if(a % 5 != b % 5) return a % 5 < b % 5;
    return a < b;
}

int a[7] = {1, 2, 3, 4, 5, 6, 7}; // 오름차순으로 정렬된 상태
sort(a, a+7, cmp); // 비교함수를 인자로 넘겨준다.

// 결과 : 5(0), 1(1), 6(1), 2(2), 7(2), 3(3), 4(4)

• 비교함수가 true 반환할 경우 즉, a % 5 < b % 5이면 출력 순서는 a b
• 비교함수가 false 반환할 경우 즉, a % 5 > b % 5이면 출력 순서는 b a

주의 사항

1. 비교 함수는 두 값이 같을 때 (or 우선 순위가 같을 때)는 런타임 에러 방지를 위해 반드시 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(const string& a, const string& b){
	return a.back() < b.back();
}