022 : 기수 정렬

import java.io.*;

public class Main {

    // Pre - Setup
    public static int[] F;
    public static long result;

    public static void main(String[] args) throws IOException {

        // ISC - L1
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int C = Integer.parseInt(br.readLine());

        // L2 ~
        F = new int[C];
        for (int i = 0; i < C; i++) {
            F[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        // Factory
        Radix_Sort(F, 5);

        // OSC
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < C; i++) {
            bw.write(F[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    // External Module : Radix sort
    public static void Radix_Sort (int[] F, int max_size) {
        int[] output = new int[F.length];
        int jarisu = 1;
        int count = 0;

        while (count != max_size) {
            int[] bucket = new int[10];
            
            // 현재 자릿수 기준으로 Bucket에 count
            for (int i = 0; i < F.length; i++) {
                bucket[F[i] / jarisu % 10]++;
            }

            // 합 배열 공식으로 bucket을 합 배열 형태로 변경하기
            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i-1];
            }
            
            // bucket 값 이용해 현재 기준 자릿수로 데이터를 정렬하기
            // output 배열에 저장하기
            for (int i = F.length-1; i >= 0; i--) {
                output[bucket[(F[i] / jarisu % 10) - 1]] = F[i];
                bucket[(F[i] / jarisu) % 10]--;
            }
            
            // 다음 자릿수로 넘어가기 전 배열에 output data 저장
            for (int i = 0; i < F.length; i++) {
                F[i] = output[i];
            }
            jarisu = jarisu*10;
            count++;
        }
    }
}