[정렬]07.자바의 정렬 API

1. API를 이용한 정렬 처리

앞서 다양한 정렬 알고리즘을 배웠지만 막상 코드를 작성할 때 긴 정렬 알고리즘을 작성하고 있기에는 시간도 부족하고 아무래도 실수도 많이 발생하게 된다.

따라서 대부분의 언어에서는 미리 잘 작성된 정렬 알고리즘을 가지고 정렬을 처리할 수 있게 지원한다. 자바 역시 마찬가지이다.

자바에서는 배열의 경우 Arrays, Collection의 경우 Collections에서 관련 기능을 제공하는데 사용법은 거의 동일하다.

 

2. Arrays.sort(T[])

가장 먼저 Arrays.sort(T[]) 형태의 메서드를 살펴보자. 다음은 int []을 정렬하기 위한 Arrays의 소스이다.

public static void sort(int[] a) {
    DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}

내부적으로 DualPivotQuicksort라는 클래스의 메서드를 이용해서 정렬하고 있다. DualPivotQuicksort는 이름에서 풍기듯이 Pivot을 두개 이용해서 작성하는 Quicksort라고 이해하면 되겠다.

 

이 메서드를 이용해서 정렬해보자.

public void sortTest1() {
	Integer[] arr = { 5, 7, 3, 8, 2, 4, 9, 0, 1, 6 };
	Arrays.sort(arr);
	System.out.println(Arrays.toString(arr));
	
	String [] strs = {"Hulk", "IronMan", "C.A", "S.M"};
	Arrays.sort(strs);
	System.out.println(Arrays.toString(strs));
}

너무나 간단히 정렬된 결과를 볼 수 있다.

 

하지만 이 메서드는 "원래부터 정렬 가능한 자료들"에 대한 "오름차순 정렬"만 가능하다. 

 

2. 원래부터 정렬 가능한 자료

원래부터 정렬 가능한 자료들이란 무엇일까?

숫자, 문자, 문자열 처럼 누가 크고 누가 작은지 우리가 쉽게 알고 있는 것들이다.

숫자의 경우 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] , 문자열의 경우는 알파벳 순으로 [C.A, Hulk, IronMan, S.M]가 그 결과이다.

 

그럼 우리가 흔히 만드는 객체들은 어떻게 정렬이 가능할까? 아래와 같은 클래스를 생각해보자.

class Hero {
	private String name;
	private Integer power;

	public Hero(String name, Integer power) {
		super();
		this.name = name;
		this.power = power;
	}
	@Override
	public String toString() {
		return "[name=" + name + ", power=" + power + "]";
	}
}

Hero의 배열이 있다면 어떻게 정렬하는게 좋을까?

Hero[] heroes = { 
		new Hero("Hulk", 100),
		new Hero("C.A", 80),
		new Hero("IronMan", 90),
		new Hero("S.M", 85) 
};

숫자의 경우 크기에 따라 문자열의 경우 알파벳 순에 따라 정렬하면 될것 같은데 Hero의 경우 숫자도 있고 문자열도 있어서 어떤 데이터를 기준으로 정렬해야할 지가 애매하다. 실제로 heroes를 정렬해보면 정렬에 실패한다.

 

public void heroSortTest() {
	Hero[] heroes = { new Hero("Hulk", 100),
			new Hero("C.A", 80),
			new Hero("IronMan", 90),
			new Hero("S.M", 85) };
	
	Arrays.sort(heroes);
	System.out.println(Arrays.toString(heroes));
}

즉 Hero는 정렬 가능한 자료가 아니다.

 

그런데 오류 메시지를 살펴보면 약간 의외의 상황이다. 정렬을 못하겠어요라는 오류가 발생하는것이 아니라 java.lang.ClassCastException이 발생한다. 즉 형변환을 못하겠다는 말이다.

 

3. 정렬하고 싶다면 Comparable<T> 

정렬을 하라고 했더니  왜 느닷없이 형변환을 하고 있을까?

 

정렬에는 다양한 알고리즘들이 있지만 언제나 동일한것은 오름차순일 때 비교 대상 두개를 비교해서 작은것을 앞에, 큰것이 뒤로 위치이동 시키는 것이다. 어떤 알고리즘이 적용되느냐는 그 후의 문제이다. 이 비교에 대한 기능을 정의해놓은 인터페이스가 Comparable이다.

 

자바에서는 객체가 정렬되기 위해서는 반드시 Comparable 인터페이스를 구현한다. Comparable은 compareTo 메서드 하나만 override  해주면 된다. 

 

즉 자바에서 객체를 정렬하기 위해서는 Comparable로 형변환 해서 compareTo 메서드의 결과에 따라 정렬하게 된다.

public interface Comparable<T> {
    public int compareTo(T o);
}

compareTo 메서드는 현재 객체 자신과 파라미터로 들어온 T o 를 비교해서 선후관계를 정리하는 메서드이다.

이 메서드의 리턴 값은 크기는 필요 없고 양수/0/음수가 의미가 있다.

 

이제 Hero에 Comparable을 적용시켜 power를 기준으로 오름차순 정렬할 수 있도록 처리해보자.

class Hero implements Comparable<Hero> {
	private String name;
	private Integer power;

	public Hero(String name, Integer power) {
		super();
		this.name = name;
		this.power = power;
	}

	@Override
	public String toString() {
		return "[name=" + name + ", power=" + power + "]";
	}

	@Override
	// 현재 객체와 o를 비교 - 오름차순 정렬
	public int compareTo(Hero o) {
		if (this.power > o.power) {
			return 1;// 자리 바뀜: 뒤로 이동
		} else if (this.power < o.power) {
			return -1;// 자리 유지
		} else {
			return 0;// 자리 이동 없음
		}
	}
}

이제 power에 따라 자신의 power가 비교 대상보다 크면 양수가 리턴되고 이를 받은 자바 API는 미리 정의된 알고리즘에 의해 뒤로 이동시킨다.

그런데 우리가 비교하는 power 즉 숫자는 이미 크기의 비교가 가능하다. 따라서 위 코드는 Integer의 compare를 사용하면 다음과 같이 수정할 수 있다.

@Override
// 현재 객체와 o를 비교 - 오름차순으로 정렬
public int compareTo(Hero o) {
    return Integer.compare(this.power, o.power);
}

 

다시 한번 정렬 테스트 코드를 실행시켜보자.

public void heroSortTest() {
	Hero[] heroes = { new Hero("Hulk", 100),
			new Hero("C.A", 80),
			new Hero("IronMan", 90),
			new Hero("S.M", 85) };
	
	Arrays.sort(heroes);
	System.out.println(Arrays.toString(heroes));
}

 

예상대로 power의 오름차순으로 잘 정렬된 것을 볼 수 있다.

[[name=C.A, power=80], [name=S.M, power=85], [name=IronMan, power=90], [name=Hulk, power=100]]

 

이처럼 자바에서는 정렬이 필요한 객체들은 Comparable을 구현해야 한다. 사실 앞서 정렬해보았던 String 역시 이미 Comparable을 구현하고 있기 때문에 정렬 가능한 객체로 분류된다.

 

String 클래스의 선언부는 아래와 같다.

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    ...
}

앞서 이야기했듯이 String은 이미 Comparable을 구현하고 있기 때문에 알파벳 순서에 따라 오름차순의 정렬이 가능하다. 이것이 String 클래스에서 구현한 compareTo의 내용이다.

 

Integer의 compareTo는 숫자의 크기에 따라 오름차순 정렬된다.

 

그런데 만약 필요에 따라 숫자의 크기에 따라 내림차순 정렬하거나 알파벳의 길이에 따라 정렬해야한다면 어떻게 해야할까? 이미 만들어진 클래스를 뜯어 고칠수는 없는 일이다. 더군다나 String, Integer 등은 final 클래스이기 때문에 메서드를 재정의할 수도 없다.

 

4. 매번 새로운 정렬 기준을 적용하려면 Comparator<T>

Comparable은 각 클래스에 고정된 정렬 기준을 재공한다. 정렬할 때마다 새로운 정렬 기준을 이용하려면 Comparator<T>를 사용할 수 있다.

Comparator에는 compare 메서드가 선언되어있고 이번에는 비교하려는 두 객체 o1과 o2가 파라미터로 들어온다.

@FunctionalInterface
public interface Comparator<T> {
	int compare(T o1, T o2);
}

이제 새로운 정렬 기준으로 정렬하는 방식에 대해 알아보자. 매번 새로운 정렬 기준을 적용하기 위해서는 Arrays.sort(T[] a, Comparator<T> c) 형태의 메서드를 사용한다.

 

다음은 숫자에 대한 내림차순 정렬을 구현한 예이다.

Integer[] arr = { 5, 7, 3, 8, 2, 4, 9, 0, 1, 6 };
Arrays.sort(arr, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		if (o1 > o2) {
			return -1;// 자리 바뀜: 뒤로 이동
		} else if (o1 < o2) {
			return 1;// 자리 바뀜: 앞으로 이동
		} else {
			return 0;// 자리 이동 없음
		}
	}	
});
System.out.println(Arrays.toString(arr));

앞선 예와 달라진 점은 크기가 다를때 반환되는 수가 양수 <-->음수로 서로 변경되었다.

 

그런데 이미 Integer는 정렬 방식이 정해저서 Comparable을 구현하고 있기 때문에 위 코드는 다음과 같이 작성할 수 있다.

Integer[] arr = { 5, 7, 3, 8, 2, 4, 9, 0, 1, 6 };
Arrays.sort(arr, new Comparator<Integer>() {
	@Override
	public int compare(Integer o1, Integer o2) {
		//return o1.compareTo(o2)*-1;	// -1을 곱해서 부호를 변경하거나
		return o2.compareTo(o1);	// 비교 대상의 순서를 변경할 수도 있다.
	}		
});

System.out.println(Arrays.toString(arr));

기본적으로 객체들의 정렬 방식이 오름차순이므로 내림차순으로 바꿀 때에는 -1을 곱해서 부호를 바꾸거나 비교 대상의 순서를 변경해주면 된다.

 

다음으로 문자열을 비교할 때 알파벳 내림차순으로 정렬하도록 처리해보자.

String[] strs = { "Hulk", "IronMan", "C.A", "S.M" };
Arrays.sort(strs, new Comparator<String>() {
	@Override
	public int compare(String o1, String o2) {
		return o2.compareTo(o1);
	}
});

System.out.println(Arrays.toString(strs));

 

물론 Comparator는 @FunctionalInterface이기 때문에 lambda를 적용하면 아래와 같이 간략히 사용할 수 있다.

String[] strs = { "Hulk", "IronMan", "C.A", "S.M" };
Arrays.sort(strs, (s1, s2)-> s2.compareTo(s1));

System.out.println(Arrays.toString(strs));

 

Comparator를 이용해서 정렬할 때 사용되는 알고리즘은 MergeSort를 사용하지 않는다. 메서드 구현을 살펴보자.

public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

Comparator가 전달되지 않으면 기본 sort를 사용하기 때문에 MergeSort를 사용하지만 Comparator가 전달되는 경우는 사용자가 지정한 경우 LegacyMergeSort, 그렇지 않은 경우는 TimSort라는 것을 사용한다. 더 타고 들어가보면 사실 LegacyMergeSort가 사용되는 경우는 거의 없다고 보면 되고 실제적인 알고리즘은 TimSort를 사용한다.

 

TimSort는 상황에 따라서 binary search를 이용한 삽입 정렬과 병합정렬을 적절히 섞어서 사용한다.

TimSort가 궁금한 경우는 https://www.geeksforgeeks.org/timsort/를 참조하기 바란다.

 

5. 다양한 정렬 형태

마지막으로 Comparable, Comparator를 이용해서 여러 방식으로 Hero를 정렬하는 예를 살펴보자.

public void heroSort() {
	Hero[] heroes = { new Hero("Hulk", 100),
			new Hero("C.A", 80),
			new Hero("IronMan", 90),
			new Hero("S.M", 85) };
	
	// 기본 정렬: Hero는 이미 Comparable 하다.
	Arrays.sort(heroes);
	System.out.println(Arrays.toString(heroes));
	
	// 알파벳 순으로 오름차순 정렬
	Arrays.sort(heroes, (h1, h2) -> h1.name.compareTo(h2.name));
	System.out.println(Arrays.toString(heroes));
	
	// 이름의 길이에 따른 오름차순 정렬
	Arrays.sort(heroes, (h1, h2) -> {
		Integer h1Len = h1.name.length();
		Integer h2Len = h2.name.length();
		return h1Len.compareTo(h2Len);
	});
	System.out.println(Arrays.toString(heroes));
	
	// 이름의 길이에 따라 오름차순하고 길이가 같을 경우는 power의 내림차순
	Arrays.sort(heroes, (h1, h2) -> {
		if (h1.name.length()== h2.name.length()) {
			return Integer.compare(h2.power, h1.power);
		} else {
			return Integer.compare(h1.name.length(), h2.name.length());
		}
	});
	System.out.println(Arrays.toString(heroes));
}