Arrays.sort로 퀵,병합 정렬하기

java.util.Arrays클래스는 배열에 관련된 다양한 메서드를 제공한다.

public class Arrays {
    // 생략..
    
    private Arrays() {}
 	
    // 생략..
}

또한 Arrays의 생성자의 접근지정자는 private이며 이는 곧 모든 메서드가 static으로 이루어져 있고 인스턴스 생성이 불가능한 class라고 보면된다.

Arrays.sort 메서드↓

위 표의 주황색 부분은 안정적인 정렬 알고리즘을 사용하는 sort메서드들이다.

위 표에 정리한 메서드는 모두 배열 a의 요소들을 기본적으로 오름차순으로 정렬한다.

fromIndex, toIndex를 매개변수로 받는 메서드들은 a[fromIndex]~a[toIndex] 까지만 정렬한다.
※ fromIndex > toIndex → IllegalArgumentException
※ fromIndex < 0 or toIndex > a.length → ArrayIndexOutOfBoundsException

기본 자료형 배열의 정렬(퀵 정렬)

위 표에서 주황색 부분을 제외한 나머지 부분은 기본 자료형 배열을 정렬하기 위한 메서드들이다. 이 sort 메서드의 내부에서 사용하는 알고리즘은 DualPivotQuicksort이다. 이는 퀵 정렬의 개선한 버전으로 퀵 정렬의 단점인 안정적이지 않은 정렬이라는 부분은 해결하지 못한다.

---

참조형(클래스 객체 배열)배열의 정렬(병합 정렬)

위 표에서 주황색 부분의 sort 메서드는 클래스 객체 배열을 정렬할 때 사용한다. 크게 두 종류로 나눈다.

여기서의 sort 메서드 내부에서 사용하는 알고리즘은 Timsort로 이는 병합 정렬과 삽입 정렬을 합친 하이브리드 개선 알고리즘이다.

※ jdk1.7 이전에서는 Timsort가 아닌 LegacyMergeSort(그냥 병합 정렬)로 정렬 했었는데 지금은 사용할 일이 없고, 심지어 useLegacyMergeSort라는 필드도 찾아볼 수 없다.

TMI로 굳이굳이 LegacyMergeSort를 사용하는 방법이 있다.
'java -Djava.util.Arrays.useLegacyMergeSort=true ...'
로 시스템 속성을 바꾸면 되긴 하는데..
자바7이전 컴파일 ->자바7이후 실행 할 때 사용할 수 있을듯하다만 정말 사용할 일이 없을것 같다.

A. 자연스러운 순서를 갖고 있는 배열을 정렬
자연스로운 순서로 요소의 대소 관계를 비교 판단한다. Inter형 배열, String형 배열에 알맞다.

여기서 자연스러운 순서란 자바에서 객체마다 특정한 기준으로 비교할 수 있는 값을 가지는 경우 인터페이스'Comparable'을 구현 해 놓는다. 대표적인 예시로 String클래스가 있다. Comparable의 구현 메서드인 compareTo()를 사용해 문자열 두개를 비교하고, 어느쪽이 사전순서 기준으로 앞에있는지 판단할 수 있다.

String a = "apple";
String b = "banana";
String c = "car";
System.out.println(a.compareTo(b)); // 결과 -1 1과2를 비교한 것과 같다.
System.out.println(a.compareTo(c)); // 결과 -2 1과3을 비교한 것과 같다.

위의 결과처럼 해당 문자열이 비교하는 문자열에 비해 사전순서로 어느정도 앞에 위치해야 하는지 알려준다. 이를 이용해 정렬 알고리즘으로 문자열 오름차순 정렬 할 수있는 것이다.

※ 더욱 자세한 Comparable & Comparator에 대한 내용은 이미 업로드한 포스트를 참조하자.

B. 자연스러운 순서를 갖고 있지 않은 배열을 정렬
위의 String처럼 a,b,c,d.. 순서를 가지는 객체가 있고, 그렇지 않는 객체를 정렬해야 할 때가 있다.

자동차라는 객체가 있다고 하자.

	public class Car {
    	private String 이름;
        private int 마력;
        private int 전장;
        private int 무게;
		private int 배기량;        
    }

위 Car클래스를 바탕으로

	Car k9 = ("K9", ...);
    Car mustang = ("Mustang", ...);
    Car huracan = ("Huracan", ...);
    Car[] carArr = {k5, mustang, huracan};

carArr를 정렬하고 싶다. 어떤 방식으로 정렬해야 할까?

carArr를 정렬하고 싶지만 Car클래스에 Comparable을 구현하기엔 뭔가 통상적으로 자동차를 정렬할 때 쓰는 기준이 없다.(내가 아는 바로는 일단 없다)

이럴때 상황에 맞게 구현해서 사용하는 것이 Comparator 인터페이스이다.
Comparable의 compareTo()처럼 Comparator의 compare()를 필요한대로 구현하면 된다.

이렇게 Compartor를 사용하는 sort메서드 2개가 존재한다.

※ 이에 관한 자세한 설명은 포스트의 흐름에 맞지 않으니 이미 포스팅된 내용을 참고하자.

이렇게 A, B모두 jdk7이상 버전에서 Timsort를 사용하여 안정적인 정렬을 구현해 준다.