[Algoritm] 초보자도 쉽게이해하는 기수정렬 알고리즘! 백준문제풀이, java

 

기수정렬(Radix Sort)

 

출처 :   https://herong.tistory.com/m/190?category=818669

 

 

기수정렬 개념, 기수정렬이란?

숫자의 각 자릿수(기수)를 기준으로 정렬하는 알고리즘으로 낮은자리(1의자리)부터 시작해 높은 자리 순으로 버킷에 분류하여 넣고 다시 합치는 방식으로 정렬한다.

실제로 숫자들간의 비교를 통해 정렬을 하는것이 아닌, 자리를 의미하는 0~9까지의 버킷이 있고 이 버킷에 자릿수를 넣어가며 분류한다.

 

기존의 정렬 순서가 유지되는 안정정렬이다.

 

 

 

그림으로 이해하기

출처 : https://velog.io/@cleangun/%EA%B8%B0%EC%88%98-%EC%A0%95%EB%A0%AC-Radix-Sort

 

 

시간 복잡도

최선/최악

• O(r*n) 
  • r : 숫자의 자릿수
  • n : 정렬될 수의 갯수

 

 

장단점 (사용하면 좋은/나쁜 상황)

장점

• 시간복잡도에서 엄청난 이점을 갖는다. 즉 속도가 빠르다
  • 이는 인자들을 비교하지않고 자릴수를 기준으로 정렬하기 때문이다.
  • 이론상 O(n log n)을 넘을 수 없는 알고리즘이다.
• 안정정렬이기에 기존에 정렬된 자릿수의 값이 같을 경우, 정렬이 바뀌지 않고 기존순서를 유지하게된다.

단점

• 추가적인 메모리 공간이 필요하다
• 데이터 타입이 한정적이다(부동 소수정실수와 같이 특수비교연산이 필요한 데이터는 적용할 수 없다.)

 

 

소스코드 예시와 설명 (백준 10989문제_ java)

백준 10989문제 기수정렬로 풀기

  문제 -  https://www.acmicpc.net/problem/10989

 

import java.io.*;

public class 기수정렬_10989 {
    public static void main(String[] args)throws Exception{
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        for(int i=0; i<N; i++){
            A[i]= Integer.parseInt(br.readLine());
        }
        br.close();
        radixSort(A,5);
        for(int i=0; i<N;i++){
            bw.write(A[i]+"\n");
        }
        bw.flush();
        bw.close();
    }
    public static void radixSort(int[] A, int max){
        int[] output = new int[A.length];
        int jarisu = 1;
        int count = 0;
        while(count!=max){
            int[] bucket = new int[10];
            for(int i=0;i<A.length;i++){
                bucket[(A[i]/jarisu)%10]++;
            }
            for(int i=1;i<10;i++){
                bucket[i] += bucket[i-1];
            }
            for(int i=A.length-1;i>=0;i--){
                output[bucket[(A[i]/jarisu)%10]-1] = A[i];
                bucket[(A[i]/jarisu)%10]--;
            }
            for(int i=0;i<A.length;i++) {
                A[i] = output[i];
            }
            jarisu = jarisu*10;
            count++;
        }
    }
}