[실전 알고리즘] 정렬2(코테용)

Counting Sort

 

수의 범위가 어느 정도 한정적일 때에만 Counting Sort를 쓸 수 있음

수의 범위가 대략 1000만 이하일때에는 카운팅 소트를 쓰고 그렇지 않을 경우에는 카운팅 소트를 쓰지 못한다고 생각하기

1부터 차례로 나온 횟수만큼 적으면 끝

1이 2번 나왔으니 1을 2개 쓰고, 2는 1번이니 1개 쓰고, 이런식으로 하면 너무나 쉽게 정렬이 가능

 

 

[백준 15688] 수 정렬하기 5 (tistory.com)

 

Radix Sort

자릿수를 이용해서 정렬을 수행하는 알고리즘

 

Comparison Sort, Non-comparison Sort

 

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

원소들끼리 크기 비교 과정 있음

 

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

원소들끼리 크기 비교하지 않고 정렬 수행

 

 

STL 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);

 

다만, sort 함수는 stable sort가 아니기 때문에 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않을 수 있다. stable sort가 필요하면  stable_sort 함수를 사용하면 된다.

 

또한 pair, tuple에서는 이미 대소 관계가 우리에게 익숙한대로 먼저 제일 앞의 원소의 대소를 비교하고, 값이 같으면 그 다음 원소의 대소를 비교하는 방식으로 정해져있음

ex) pair에서 {2, 5} < {3, -2}고 tuple에서 {2, 1, 0} > {2, -2, 6}

 

그래서 좌표를 정렬하거나 기타 여러 속성이 있는 원소를 정렬할 때 별도로 구조체를 둘 필요가 없고 pair나 tuple 등을 이용하면 됨

 

 

하지만 내가 원하는 대로 비교 함수를 정해서 넘겨줄 수 있음!

예를 들어 int형을 크기 순으로 정렬하고 싶으면 위의 코드와 같이 하면 되는데 int형을 5로 나눈 나머지 순으로, 5로 나눈 나머지가 같다면 크기 순으로 정렬하고 싶다면?

이렇게 하면 배열 a가 5, 1, 6, 2, 7, 3, 4로 정렬됨

비교 함수 cmp(int a, int b)는 a가 b의 앞에 와야할 때 true를, 그렇지 않을 때에는 false를 반환함

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);

a가 b의 앞에 와야할 때 true, 그렇지 않을 때 false

 

 

STL sort 연습문제 : 

[백준 1431] 시리얼 번호 (tistory.com)

 

 

정렬의 응용

[백준 11652] 카드 (tistory.com)

 

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x0F강 - 정렬 II (encrypted.gg)