정렬은 매우 중요하다. 알고리즘을 풀 때에도 정렬이 되어 있다는 가정 하에 정렬이 되는 경우가 많고, 실제 개발 로직을 작성할 때도 정렬을 해야할 때가 있다.
그래서 JAVA에서 primitive type을 정렬하는 법과 reference를 정렬하는 법 두 가지를 정리하려고 한다! 포스팅에서 람다식 사용할 거라서 JAVA 8버전 이상이 필수이다!
1. Arrays.sort, Collections.sort
두 가지를 나누는 게 무의미하기도 한 게, 사실 Collections.sort 또한 컬렉션 자료구조를 정렬하는 것 뿐이지 메소드 내부를 확인해보면 컬렉션를 toArray로 변경한 후, Arrays.sort 메서드로 정렬하는 걸 확인할 수 있다.
@SuppressWarnings({"unchecked", "rawtypes"})
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}그래서 다시 정리하자면! 배열을 정렬할 땐, Arrays.sort를 사용하고
컬렉션을 정렬할 땐, Collections.sort를 사용한다.
Arrays.sort(arr);Collections.sort(list);하지만 컬렉션 또한 내부적으로 배열로 다시 바꿔서 배열의 정렬 메소드를 사용한다!
2. Primitive Type vs Reference Type
두 가지 타입의 차이점은 다 알 것이라고 생각하지만! 다시 한 번 정리해보면
Primitive type은 원시 타입으로 기본적인 자료형을 뜻한다.
Reference type은 객체 타입으로 기본적인 자료형이 아닌 객체형을 말하며 커스텀하게 만든 객체도 포함되지만 primitive type의 wrapper 클래스인 Integer, Character 등과 같은 Wrapper 클래스도 포함된다!
근데 이걸 왜 설명하지?
정렬 메소드를 사용하고는 있지만, 파라미터에 따라 사용하는 정렬 알고리즘이 다르다.
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, 0, a.length);
}
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);
}
}결론적으로!
원시 타입을 정렬할 때는 DualPivotQuicksort를 사용하고,
reference 타입을 정렬할 때는 TimSort를 사용한다.
3. DualPivotQuickSort, TimSort
DualPivotQuickSort는 기존 퀵소트와는 다르게 피벗을 2개 두는 정렬이다. 만일 리스트에 피벗이 두개라면, 리스트는 3개로 분할될 것이다. 위와 같이 기존에 피벗을 하나로 둘 때보다 하나 더 분할되기 때문에 logN 계수가 낮아진다. (시간복잡도는 동일하지만, 상수 계수가 줄어들 확률이 높다.)
또한 내부에 다양한 최적화를 해서 매우 빠르다.
TimSort는 삽입정렬과 병합정렬을 합친 정렬 알고리즘이다.
퀵 정렬을 사용하지 않는 이유는?
추측해보자면, 병합 정렬이 최악의 경우에도 동일한 시간복잡도를 가지고 있고 안정적이며 현대에는 공간 복잡도가 큰 고려 요소가 아니기 때문이다.
병합 정렬을 이용하며, 매우 작은 리스트로 분할된다면, 이때 삽입 정렬을 사용하는 정렬 알고리즘이다.
TimSort는 참조 지역성 등의 이유로 reference type에 특화된 정렬 알고리즘이다.
(사실 내용이 너무 복잡해서 추후에 다시 공부해야될 것 같다!)
4. Comparable, Comparator
객체를 정렬하기 위해서는 특별한 기준이 있어야 한다! 기준 없이 정렬할 수 없다.
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}객체를 정렬하기 위해서는 Collections 클래스에서 위 두 가지 메소드를 이용할 수 있다.
여기서 말하고 싶은 건!
1. 객체 자체가 Comparable interface를 상속한 객체이든지
2. Comparator를 생성해서 sort 메소드에 인자로 넣어줘야 한다
이 두 가지를 지켜야만 정렬을 수행할 수 있다.
만일 Comparable interface를 상속하지 않고 그냥 extends 한다면, 인자값이 다르기 때문에 저 메소드로 판단되지 않는다.
Comparator에 null을 넣어 정렬하면,
Exception in thread "main" java.lang.ClassCastException: class Node cannot be cast to class java.lang.Comparable (Node is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap')
at java.base/java.util.ComparableTimSort.countRunAndMakeAscending(ComparableTimSort.java:320)
at java.base/java.util.ComparableTimSort.sort(ComparableTimSort.java:188)
at java.base/java.util.Arrays.sort(Arrays.java:1107)
at java.base/java.util.Arrays.sort(Arrays.java:1301)
at java.base/java.util.ArrayList.sort(ArrayList.java:1721)
at java.base/java.util.Collections.sort(Collections.java:179)위와 같은 출력 값을 얻는다. (어디서 막히는지 몰라 직접 수행하고 출력해서 확인해봄. 내부에서 엄청 호출한다.) 객체를 Comparable로 타입 형변환 하는데 거기서 형변환이 안 되는 에러가 출력된다.
Comparable
그래서 Comparable 상속하는 법은,
정렬할 객체에 Comparable 인터페이스만 상속하고 compareTo 메소드를 구현하면 된다.
class Node implements Comparable<Node>{
int idx;
public Node(int idx) {
this.idx = idx;
}
public int compareTo(Node n) {
return Integer.compare(this.idx, n.idx);
}
}위와 같이 하면 된다.
compare
여기서 compareTo나 Comparator의 compare 정의 시에, 어떤 값을 return 하는지가 중요하다.
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}나는 주로 Integer wrapper 클래스의 compare를 이용하는 편인데,
x<y인 경우 -1
x==y인 경우 0
x>y인 경우 1을 출력한다.
그럼 return 값이 무슨 의미를 내포하고 있는지가 궁금할 것이다.
-1: 첫번째 객체가 두번째 객체보다 작다
0: 첫번째 객체와 두번째 객체가 동일하다
1: 첫번째 객체가 두번째 객체보다 크다
만일 오름차순을 원한다면 compare 값 그대로를 반환하면 되고,
내림차순을 원한다면 compare에 -1을 곱해서 반환하면 된다.
만일 [2, 3] 이렇게 들어왔을 때 내림차순은 [3, 2] 형식으로 표현되어야 한다.
compare(2, 3) = -1이기 때문에 첫번째 객체가 두번째 객체보다 작다.
하지만 [3,2]로 표현해야한다.
즉, 3이 2보다 앞에 와야 한다.
-1이 나오면 x, y 순서 변경하지 않음
0 동일하니 그대로
1이 나오면 x, y 순서를 변경함
위와 같이 간단하게 정리할 수 있다.
Comparator
Comparator는 1. 객체에 Comparable 인터페이스를 상속하지 않을 때 또는 2. Comparable 인터페이스를 상속했지만 다른 기준으로 정렬하고 싶을 때 정의할 수 있다.
(내부 코드를 확인하면 Comparable 보다 Comparator가 더 우선시 적용된다.)
Comparator는 인터페이스라 클래스로 만들어서 사용해야 한다.
class NodeComparator implements Comparator<Node>{
@Override
public int compare(Node o1, Node o2) {
return Integer.compare(o1.idx, o2.idx);
}
}이렇게 생성된 커스텀 Comparator의 인스턴스를 만들어서 정렬하면 된다.
public static void main(String[] args) {
List<Node> nodes = new ArrayList<>();
nodes.add(new Node(10));
nodes.add(new Node(4));
Collections.sort(nodes, new NodeComparator());
for(Node node:nodes){
System.out.println(node.idx);
}
}[4, 10]의 결과가 나온다.
인터페이스지만 바로 객체로 만들 수도 있다!
익명 클래스를 사용하면 된다.
익명 클래스는 클래스를 만들지 않고 객체를 생성하는 방법으로, 인터페이스 또한 바로 객체로 만들 수 있다.
만일 comparator를 위 코드처럼 클래스로 만들지 않고 바로 객체를 생성한다고 하면,
Collections.sort(nodes, new Comparator<Node>() {
public int compare(Node o1, Node o2) {
return Integer.compare(o1.idx, o2.idx);
}
});이렇게 나타낼 수 있다.
람다식으로 간단하게 변경도 가능하다.
이것은 다 Comparator가 함수형 인터페이스이기 때문이다.
Collections.sort(nodes, (Node o1, Node o2) -> {
return Integer.compare(o1.idx, o2.idx);
});
더 축약하면
Collections.sort(nodes, (Node o1, Node o2) -> Integer.compare(o1.idx, o2.idx));이렇게까지 축약할 수 있다.
5. 참고 자료
https://d2.naver.com/helloworld/0315536
TimSort와 같은 경우에는 더 공부를 해야할 것 같다. 내용이 많고 생각보다 어려워서 아직 확실하게 이해하지 못한 것 같다!
단순히 자바 내에서의 정렬에 대해 알아보려고 했는데, 생각보다 많은 부분을 공부하게 되었다. 다 나중에 도움이 되기를...
