RadixSort 기수 정렬 java

기수 정렬이란?

기수 정렬(radix sort)은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니, 안정성이 있고(이때 데이터들 간의 상대적 순서는 보존되어야 한다.) 시간 복잡도는 ${\displaystyle O(dn)}$이다.(${\displaystyle d}$는 가장 큰 데이터의 자리수)

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 ${\displaystyle O(dn)}$이어서, 정수와 같은 자료의 정렬 속도가 매우 빠르다. 하지만, 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

출처: https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC (위키백과)

위키백과에 위와 같은 내용으로 정의되어있다. 이 기수정렬을 처음 알았을 때는 정말 신기하였다. 이렇게 자릿수마다 비교하고서 마지막에는 정렬된 상태가 나오기 때문이다. 도대체 이걸 생각한 사람도 대단하다고 느꼈다.  기수정렬의 원리는 아래 그림과 같다. 

그림을 보면 data 배열을 만들고서 그 안에는 앞으로 정렬할 데이터를 입력합니다.  Bucket에는 0~9까지 index를 중심으로 data를 입력합니다. 위의 그림을 보면 231,152,675,442 4개의 숫자를 정렬해보았습니다. 이 숫자들의 일의 자리, 십의 자리, 백의 자리 순으로 정렬하는 것이 이 정렬의 원리입니다. 

처음에 일의 자리로 정렬하였더니 

231 에서 일의 자리인 1을 bucket의 index 주소 1의 자리에다가 추가합니다.

152 에서 일의 자리인 2를 bucket의 index 주소 2의 자리에다가 추가합니다.

675 에서 일의 자리인 5를 bucket의 index 주소 5의 자리에다가 추가합니다.

442 에서 일의 자리인 2를 bucket의 index 주소 2의 자리에다가 추가합니다.

그리고서 위의 자리에서부터 숫자를 data[] 배열에 입력합니다. 

그러면 data[]배열의 index안에는 231,152,442,675 값이 입력됩니다. 이런 식으로 십의 자리, 백의 자리까지 한다면 마지막으로 152,231,442,675 로 정렬된 상태가 됩니다.  아래는 제가 직접 짠 소스입니다. 

import java.io.*;
import java.util.StringTokenizer;
 
/**
 * on 31/12/2016.
 */
 
class Bucket {
    int data;
    Bucket node;
 
    public Boolean isEmpty() {
        if (this.node == null) {
            return true;
        }
        return false;
    }
 
    public int getData() {
        return data;
    }
 
    public void setData(int data) {
        this.data = data;
    }
 
    public Bucket getNode() {
        return node;
    }
 
    public void setNode(Bucket node) {
        this.node = node;
    }
 
    Bucket(int data) {
        this.data = data;
    }
 
    Bucket(Bucket node) {
        this.node = node;
    }
}
 
public class RadixSort {
 
    Bucket[] bucketArr = new Bucket[10];
    Bucket[] data;
 
    void inputNumber() throws IOException {
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
         StringTokenizer st = new StringTokenizer(br.readLine().trim());
        int n = Integer.parseInt(st.nextToken());//숫자 갯수 입력
//        int n = 4;
        data = new Bucket[n];//숫자 저장소
//        data[0] = new Bucket(231);
//        data[1] = new Bucket(152);
//        data[2] = new Bucket(675);
//        data[3] = new Bucket(442);
 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine().trim());
            data[i] = new Bucket(Integer.parseInt(st.nextToken()));
        }
 
    }
 
    void sort() throws IOException {
        inputNumber();
        // display();
 
 
        Boolean keepGoing = true;
        int cnt = 1;
        int bucketNum = 0;
        int index = 0;
        while (keepGoing) {
            keepGoing = false;
 
            for (int i = 0; i < data.length; i++) {
                //Bucket에 Data 넣기
                int num = data[i].getData();
                for (int k = 0; k < cnt; k++) {
                    //자릿수
                    bucketNum = num % 10;
                    num /= 10;
                }
                if (bucketNum != 0) {
                    keepGoing = true;
                }
                //Number number = new Number(data[i].getNum());
                if (bucketArr[bucketNum] == null) {
                    bucketArr[bucketNum] = data[i];
                } else {
 
                    Bucket temp = data[i];
                    Bucket head = bucketArr[bucketNum];
                    while (head.node != null) {
                        head = head.node;
                    }
                    head.node = temp;
                }
            }
            //Bucket에 순서대로 빼기
            index = 0;
            for (int i = 0; i < bucketArr.length; i++) {
                if (bucketArr[i] != null) {
                    Bucket temp = bucketArr[i];
                    do {
                        data[index] = temp;
                        temp = temp.node;
                        data[index++].node = null;//data[]에 들어가면 링크 삭제
                    } while (temp != null);
                }
            }
            bucketInit();
            cnt++;
        }
        display();
 
    }
 
    void bucketInit() {
        //bucketArr 초기화
        for (int i = 0; i < bucketArr.length; i++) {
            bucketArr[i] = null;
        }
 
    }
 
    void display() throws IOException {
 
//        for (int i = 0; i < data.length; i++) {
//            System.out.print(data[i].getData() + " ");
//        }
//        System.out.println();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < data.length; i++) {
            bw.write(String.valueOf(data[i].getData()) + "\n");
        }
        bw.close();
 
    }
 
 
    public static void main(String[] args) throws IOException {
        new RadixSort().sort();
    }
}