정렬2 : Counting Sort, Radix Sort, STL sort, 정렬의 응용

계수 정렬 : Counting Sort

• 미리 큰 테이블을 만들어두고, 각 수에 해당하는 인덱스의 값을 1씩 증가시켜 등장 횟수를 저장한 뒤, 작은 수부터 차례대로 등장 횟수만큼 출력하면 된다.
• freq 배열에 입력값 N개를 한 번씩 확인하며 값을 증가시키고 정렬된 순서로 출력하기 위해 freq 배열 전체인 K개의 수를 확인해야 하므로 시간 복잡도는 $O(N+K)$이다.
• 값의 범위인 K가 너무 클 경우 공간 낭비가 크므로, 수의 범위가 10,000,000 이하일 경우에만 사용하는 것이 효율적이다.

기수 정렬 : Radix Sort

• 자릿수를 이용하여 정렬을 수행하는 알고리즘
• Counting sort를 응용한 알고리즘
• 각 자릿수마다 자릿수의 최대 개수인 D번만큼 Conting Sort를 하므로 $O(D(N+K))=O(DN+DK)$이지만 K는 N보다 훨씬 작기 때문에 무시해도 된다. 따라서 시간 복잡도는 $O(DN)$이다.

과정

1. 0부터 9까지 10개의 리스트를 만든다.
2. 1의 자리 기준으로 각 자릿수에 맞게 리스트에 수를 넣는다.
3. 0번 리스트부터 보면서 수를 꺼내 수열을 재배열한다. 단, 1의 자리가 같은 수끼리는 원래 수열의 순서를 유지한다.
4. 재배열한 수열을 10의 자리 기준으로 다시 재배열한다.
5. 재배열한 수열을 100의 자리 기준으로 다시 재배열하면 정렬이 완료된다.

• A가 B보다 크다는 것은 더 큰 자리인 왼쪽 자리부터 비교했을 때 A의 자릿수가 B의 자릿수보다 큰 경우가 먼저 생긴다는 의미이다.
• 따라서 언젠가는 A가 B보다 앞선 상태로 정렬이 되고 그 상대적인 위치 관계가 유지된 채로 정렬 과정이 종료된다.

코드

코드를 입력하세요

Comparison Sort vs Non-comparision Sort

STL sort