Sorting - (8)

Radix Sort

기수 정렬(radix sort)
: 두 값을 비교하지 않고, 각 자리수에 따라 비교하여 정렬하는 알고리즘
시간복잡도 - O(kn) , k=데이터의 자릿수

ex)
16 80 18 77 03 24 88 23

• 1의 자리 숫자 기준으로 데이터 저장
  list[0]={80}
  list[3]={03,23}
  list[4]={24}
  ...
• 순서대로(index=0 부터 pop) 10의 자리 숫자 기준으로 데이터 저장
• 다시 순서대로 pop 하면 정렬됨.
• 최대 데이터의 자릿수 만큼 진행해야 함.
  => 최대 수가 10000 이면, 5번 반복

수 정렬하기3(백준 10989번, 시간 제한: 3초)

문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

입력 예시
10
5
2
3
1
4
2
3
5
1
7

출력 예시
1
1
2
2
3
3
4
5
5
7

코드 예시

import sys
input = sys.stdin.readline
n=int(input())
arr=[0]*10001
for _ in range(n):
    arr[int(input())]+=1
for i in range(10001):
    k=arr[i]
    for j in range(k):
        print(i)

n의 최대 개수 10,000,000 이기 때문에 O(nlogn) 으로 문제를 접근 시, 시간 초과가 난다.
자릿수는 최대 5자리기이기 때문에 Radix sort나 Count Sort로 문제를 푸는 것이 좋다.

더 간단한 코드인 Count Sort 로 풀어보자.
list를 0~10000 까지 가지고 있고, input이 들어올때마다, list[input]++ 을 한다.
그 다음, list 0~10000 까지 돌면서, list[i] 개수만큼 i를 출력하면 된다.