정렬 알고리즘 4 (기수 정렬, Arrays.sort)

• 기수 정렬 (Radix sort)

  기수 정렬은 정렬 알고리즘 3에 나온 도수 정렬과 같이 데이터를 비교, 교환하지 않는 알고리즘이다. 기수란 데이터를 구성하는 기본 요소로 10진수에서는 0 ~ 9, 2진수에서는 0과 1, 알파벳 소문자의 경우 a ~ z가 기수가 된다. 기수 정렬에서는 기수의 개수만큼 Queue를 만들어 데이터들의 낮은 자릿수부터 높은 자릿수까지 순서대로 기준을 잡아 정렬하는 방법이 있다. (문자열은 가장 오른쪽 문자부터 왼쪽 문자의 순서로 기준을 잡음) 이것이 기수 정렬의 가장 전형적인 방법으로 필요에 따라 기준을 잡는 순서를 바꾸는 방법들도 있다. 하지만 우리는 처음 배우는 것이므로 앞에서 말한 전형적인 방법인 가장 작은 자릿수부터 높은 자릿수로 기준을 잡는 LSD(Least Significant Digit)정렬 방법을 알아 볼 것이다. (가장 큰 자릿수부터 낮은 자릿수로 기준을 잡는 MSD(Most Significant Digit)은 구현의 난이도가 높으며 중간에 데이터를 확인해야 하는 단점이 있다) 

 

  10진수 중에서 100의 자리수 5개 123, 423, 855, 392, 863을 통해 기수 정렬의 진행과정을 살펴보자. a = { 123, 423, 855, 392, 863 }을 기수 정렬하기 위해 일단 기수의 개수만큼 큐를 생성한다. 그리고 각각의 큐에 가상의 이름을 붙이는데 10진수는 0 ~ 9의 기수가 있으므로 큐도 이름을 0 ~ 9로 짓는다. 그리고 우리는 LSD를 구현하는 법을 배우고 있으므로 첫번째 정렬 기준은 일의 자리가 된다. 그러면 a의 요솟값들을 기준에 맞게 정렬해보자. 우선 123의 일의 자리 수는 3이다. 그러면 이 값을 이름이 3인 큐에 집어넣는다. 423도 이름이 3인 큐에 넣고 855는 이름이 5인 큐, 392는 이름이 2인 큐, 863은 이름이 3인 큐에 넣는다. 그리고 큐 0번부터 큐 9번까지 큐 안에 있는 수를 전부 빼서 a에 집어넣는다. 큐 0, 1번은 안에 없고 큐 2번에 392, 큐 3번에 123, 423, 863 ... 큐 5번에 855를 빼고 큐 6번 ~ 큐 9번은 안에 아무것도 없으니 패스한다. 따라서 a = { 392, 123, 423, 863, 855 }로 1차적인 정렬이 끝난다. 두번째도 같은 방법으로 기준만 십의자리로 잡고 정렬하면 a = { 123, 423, 855, 863, 392 }가 되고 마지막으로 백의 자리를 기준으로 정렬하면 a = { 123, 392, 423, 855, 863 }이 되고 정렬이 종료된다. 이를 코드로 구현해보면 다음과 같다.

static void radix(int[] a, int n, int qn, int m) {
    // n = 배열의 크기  qn = 큐의 크기  m = 기준의 개수(자릿수)
    // 기수의 개수만큼의 Queue배열 생성
    Queue<Integer>[] q = new LinkedList[qn];
    for(int i=0; i<qn;i++){
        q[i] = new LinkedList<>();
    }
    int f = 1;
    // 기준에 맞게 정렬을 자릿수만큼 반복한다.
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++)
            q[(a[j]/f)%10].add(a[j]); // 배열 a의 값을 큐에 넣기
        for(int j=0, k=0 ; j<qn; j++){
            while(!q[j].isEmpty())
                a[k++]=q[j].poll();  // 큐에 있는 값을 빼서 배열 a에 저장
        }
        f*=10;
    }
}

 radix 메서드에 넣기전에 정렬하고 싶은 데이터의 기수를 파악하여 큐의 크기 qn(기수의 개수)을 정하고 정렬하고 싶은 데이터의 자릿수를 파악해 m을 정한다. 그리고 radix 메서드에 들어가면 Queue배열을 qn크기로 만들고 배열 a의 값을 Queue배열에 분류해서 넣고 다시 a로 값을 꺼내고 하는 과정을 m번(자릿수 만큼) 반복해 정렬을 끝낸다. 

 

  기수 정렬은 앞에서 말했듯이 비교, 교환과정이 없어 굉장히 빨라질 수도 있는 알고리즘이다. 하지만 좋은 점이 있으면 나쁜 점도 있는 법이다. 기수 정렬을 사용하려면 추가적인 메모리가 필요하고 기수와 데이터의 자릿수 등을 미리 파악해야하며, 정렬할 수 있는 데이터 타입이 제한된다.( 부동소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없고, 10진수, 2진수, 16진수, 소문자 알파벳 문자열 등에는 적용이 되지만 위의 알고리즘으로 정렬을 하려면 모든 데이터의 길이가 같아야한다 / 특정 알고리즘을 적용하면 길이가 다른 데이터까지 정렬 가능) 동일한 데이터의 순서가 정렬 후에도 변함이 없으므로 안정적인 알고리즘이고 시간 복잡도는 자릿수의 크기를 m 데이터 개수를 n이라 했을때 O(k*n)이 된다.

 

• Arrays.sort 

  배열은 Arrays.sort를 이용한 정렬이 가능하다. 기본 자료형으로 이루어진 배열 a를 Arrays.sort(a)를 이용해 정렬하면 퀵  정렬 알고리즘을 이용해 a를 오름차순으로 정렬하고 Arrays.sort(a, i, j)를 이용해 정렬하면 퀵 정렬 알고리즘을 이용해 a[i] ~ a[j]의 값들을 오름차순으로 정렬해준다. (Arrays.sort(a, Collections.reverseOrder())를 이용하면 내림차순 정렬이 가능) 클래스 객체로 이루어진 배열 a를 Arrays.sort를 이용해 정렬할때 만약 클래스 객체가 자연스러운 순서를 갖고있다면 Arrays.sort(a)를 이용해 오름차순 정렬이 가능하다. 이때 Arrays.sort(a, i, j)의 방법도 사용이 가능하고 정렬시 병합 정렬 알고리즘이 사용된다. 사용 예시를 한번 보자.

import static java.util.GregorianCalendar.*;
import java.util.Arrays;
import java.util.GregorianCalendar;
public class Main {
    public static void main(String[] args){
        GregorianCalendar[] x = {
                new GregorianCalendar(2022, NOVEMBER, 1),
                new GregorianCalendar(1963, OCTOBER, 18),
                new GregorianCalendar(1985, APRIL, 5)
        };
        Arrays.sort(x);
        for(int i = 0; i < x.length; i++){
            System.out.printf("%04d년 %02d월 %02d일\n",x[i].get(YEAR),x[i].get(MONTH)+1,x[i].get(DATE));
        }
        //실행 결과 
        //1963년 10월 18일
        //1985년 04월 05일
        //2022년 11월 01일
    }
}

다음과 같이 GregorianCalender 객체 배열 x를 만들고 Arrays.sort(x)를 하면 아래와 같이 연도 오름차순으로 정렬이 완료된다. 이는 GregorianCalender클래스 내부에서 Comparable 인터페이스와 compareTo메서드가 구현되어있기 때문에 자연스러운 순서를 갖고있기 때문이다. 그러면 Comparable, Comparator 인터페이스가 구현되어있지 않은 클래스들, 즉 자연스러운 순서가 없는 클래스 객체 배열의 정렬은 어떻게 해야될까? 이럴 때는 Comparator 인터페이스를 implements한 클래스를 따로 만들어 그 클래스의 객체 c를 만들고 Arrays.sort(x,Comparator<? super T> c)를 해주면 된다. 이때 자연스러운 순서의 기준은 c에서 정한 내용이 적용되고 이에 따라 병합 정렬이 이루어진다. 코드로 한 번 확인해보자. 

import java.util.Arrays;
import java.util.Comparator;
public class Main {
    // 정적 중첩 클래스 Physcdata
    static class PhyscData{
        String name;
        int height;
        double vision;
        // 생성자
        PhyscData(String name, int height, double vision){
            this.name = name; this.height = height; this.vision = vision;
        }
        // 클래스 메서드
        public String toString(){
            return name + " " + height + " " + vision +"\n";
        }
        // 정적 중첩 클래스 안의 정적 중첩 클래스로 HeightOrderComparator 생성
        private static class HeightOrderComparator implements Comparator<PhyscData>{
            public int compare(PhyscData d1, PhyscData d2){
                return (d1.height > d2.height) ? 1 : (d1.height < d2.height) ? -1 : 0;
            }
        }
        // Comparator를 상속한 클래스인 HeightOrderComparator의 객체 HEIGHT_ORDER 생성
        static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();

    }
    public static void main(String[] args){
        PhyscData[] x = {
                new PhyscData ("강민하", 162, 0.3),
                new PhyscData ("김찬우", 173, 0.7),
                new PhyscData ("박준서", 175, 2.0),
                new PhyscData ("유서범", 171, 1.5),
                new PhyscData ("이수연", 168, 0.4),
                new PhyscData ("장경오", 174, 1.2),
                new PhyscData ("황지안", 169, 0.8),
        };
        Arrays.sort(x,PhyscData.HEIGHT_ORDER);
        for(int i = 0; i < x.length; i++){
            System.out.printf(x[i].toString());
        }
        //실행 결과
        //강민하 162 0.3
        //이수연 168 0.4
        //황지안 169 0.8
        //유서범 171 1.5
        //김찬우 173 0.7
        //장경오 174 1.2
        //박준서 175 2.0
    }
}

학생들의 이름, 키, 시력의 data를 담을 수 있는 PhyscData라는 정적 중첩 클래스를 만든다. 그리고 그 클래스 안에 이름, 키, 시력을 출력하는 toString 메서드를 만들고, Comparator를 상속한 HeightOrderComparator 정적 중첩 클래스를 만들어 HeightOrderComparator의 객체 HEIGHT_ORDER를 만든다. 이제 PhyscData는 원래 자연스러운 순서를 갖고 있지 않은 클래스였지만 Comparator를 상속한 HeightOrderComparator의 객체 HEIGHT_ORDER를 갖고 있으므로 Arrays.sort를 이용해 정렬이 가능해 졌다. 따라서 x라는 PhyscData의 배열을 만들고 Arrays.sort(x, PhyscData.HEIGHT_ORDER)를 이용행 정렬을 하면 HeightOrderCompartor에서 정한 규칙대로 정렬이 완성된다. 그리고 메서드 x[i].toString를 통해 다음과 같은 결과를 확인할 수 있다.