[알고리즘]자연정렬

본문은 "자료구조와 함께 배우는 알고리즘 입문-자바편(Bohyoh Shibata 지음, 강민 옮김)"을 참고하여 작성되었습니다(p.124).

[텍스트1.txt, 텍스트2.txt, 텍스트10.txt, 텍스트21.txt, 텍스트100.txt]는 두 가지의 방식으로 정렬가능하다.
1) 문자열 정렬: [텍스트1.txt, 텍스트10.txt, 텍스트100.txt, 텍스트2.txt, 텍스트21.txt]로 정렬가능하다. 컴퓨터의 문자열 정렬은 동일한 위치에 있는 문자의 대소 비교를 통해 정렬하기 때문에 앞선 결과를 도출한다.
2) 자연정렬: [텍스트1.txt, 텍스트2.txt, 텍스트10.txt, 텍스트21.txt, 텍스트100.txt]로 정렬가능하다. 사람에게는 이와 같은 정렬이 보다 '자연'스럽다.
위 두 가지 졍렬을 자바의 Arrays클래스 메소드 sort를 이용하여 구현해보자

자연졍렬이 필요한 배열

// 요소의 대소 관계를 비교하여 정렬한다요소의 대소 관계를 비교하여 정렬한다.
static void sort(Object[] a)
static void sort(Object[] a, int fromIndex, int toIndex`

import java.util.Arrays;
import java.util.GregorianCalendar;
import static java.util.GregorianCalendar.*;

class SortCalendar {
	public static void main(String[] args) {
    	GregorianCalendar[] x = {
            new GregorianCalendar(2017, NOVEMBER, 1), // 2017년 11월 1일
            new GregorianCalendar(1963, OCTOBER, 18), // 1963년 10월 18일
            new GregorianCalendar(1985, APRIL, 5), // 1985년 4월 5일
        }
            
        Arrays.sort(x); // 배열 x를 정렬

        for (int i = 0; i < x.length; i++) {
            System.out.printf("%04d년 %02d월 %02일\n",
            	x[i].get(YEAR),
                x[i].get(MONTH)+1,
                x[i].get(DATE)
            );
        }
    }
}

결과

위의 결과대로 우리에게 자연스러운 연도 순으로 배열되었다.

자연정렬이 필요하지 않은 배열

// 요소의 대수 관계를 비교할 때 comparator c를 사용하여 정렬합니다.
static <T> void sort(T [] a, Comparator<? super T> c)
static <T> void sort(T [] a, int fromIndex, int toIndex, Comparator<? super T> c)

import java.util.Arrays;
import java.util.Scanner;
import java.util.Comparator;

public class PhyscExamSort {
    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;
        }

        static final Comparator<PhyscData> HEIGHT_ORDER = new 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;
            }
        }
    }

    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        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);
        System.out.println("-신체검사 리스트-");
        for (int i = 0; i < x.length; i++) {
            System.out.printf("%-8s%3d%5.2f\n", x[i].name, x[i].height, x[i].vision);
        }
    }
}

결과

PhyscData의 객체 중 키(height)를 기준으로 나열되었다(HeightOrderComparator).