Arrays.sort()란?
우리는 보통 자바에서 배열 정렬을 할때 java.util.Arrays 클래스의 sort()메소드를 이용하여 정렬을 한다.
이러한 Arrays.sort를 이용하여 우리는 아래와 같이 쉽게 오름차순으로 정렬할 수 있다.
// Array
int[] intArr = new int[] {1,3,5,2,4};
double[] doubletArr = new double[] {1.1, 3.3, 5.5, 2.2, 4.4};
String[] stringArr = new String[] {"A","C","F","E","D"};
// 전체 정렬
Arrays.sort(intArr);
Arrays.sort(doubletArr);
Arrays.sort(stringArr);
// 부분 정렬
Arrays.sort(intArr, 1, 4);⬇️Answer⬇️
// 전체 정렬
intArr : 1 2 3 4 5
doubletArr : 1.1 2.2 3.3 4.4 5.5
stringArr : A B C D E
// 부분 정렬
intArr : 1 2 3 5 4
이런식의 코드는 우리가 종종 코딩테스트에서 사용을 해왔고, 짧은 라인수로 정렬을 쉽게 해주는 아주 오아시스 같은 메소드이다.
시간복잡도는?
여기서 드는 고민이 있다.
Arrays.sort()의 내부는 어떻게 동작할까?
정렬할때 무지성으로 써도 될까? 실행시간에 괜한 영향을 끼치는 것은 아닐까?
다행히 자바11 레퍼런스에 간략하게나마 어떤 알고리즘으로 구현이 되어있는지 설명이 나와있다.
"Java11 reference에서 발췌"
살펴보니 내부적으로 DualPivotQuickSort을 사용한다.
(단, object타입의 sort를 보면 TimSort도 사용하는것 같다.)
본문에도 나와있듯이 기존 1 pivot의 퀵소트보다 일반적으로 더 개선된 성능을 보여준다 한다. (1 pivot 퀵소트보다 Average Case가 더 많이 hit된다고 한다.)
DualPivotQuickSort의 성능을 정리해보면 아래와 같다.
Best Cases : O(nlog(n))
Average Cases : O(nlog(n))
Worst Cases :O(n^2)
얼핏 보면 기존 1 pivot 퀵소트와 차이가 없는 것 같지만, 레퍼런스 기준으로 퀵소트 보다 일반저으로 더 개선된 성능을 보여준다고 하니..
일반적으로 정렬 세계관 중 최강자는 퀵소트라고 알고 있었는데 이것보다 더 빠르고 개선되었다고 하니 큰 고민 없이 사용해도 될 것 같다.
내 입맛대로 정렬하기
자 그러면 내 입맛대로 정렬을 해볼려면 어떻게 할까??
다시 친절한 java11 레퍼런스로 돌아가보자
친절하게 '지정된 비교기'에 의해 정렬이 가능하다라고 써있다.
여기서 '지정된 비교기'란 'Comparator'를 의미한다. 즉, sort의 인자로 배열과 Comparator 객체를 전달하면 우리의 입맛대로 정렬이 가능할 것이다.
그렇다면 Comparator란 무엇인가? 어떻게 Comparator객체를 선언하지?
레퍼런스를 읽어보니 Comparator는 interface이고, 이것은 java.util.Comparator를 import하여 사용이 가능하다.
또한, Comparator 내부의 compare 메소드가 존재하고 이것은 비교조건을 명시한다. 따라서 우리는 이 compare 메소드를 override 받아 재정의 해주면 될 것이다.
아래와 같이 정리할 수 있다.
java.util.Comparator를 구현한 Class내 compare() 메서드를 원하는 정렬조건으로 오버라이드하여 sort 메서드 호출시 구현한 Comparator 클래스를 명시해 주면 된다.
다만, 주의할 점은 주의할 점은 byte, char, double, short, long, int, float같은 PrimitiveType의 배열에는 적용이 불가능하니 Integer같은 Wrapper "Class"를 이용해야 한다는 점이다.
또한, Comparator의 compare를 따로 재정의 해주지 않는다면, 기본적으로 오름차순 정렬을 하게 된다.
이제 실습을 해볼까??
import java.util.Arrays;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
// Integer 배열 선언
Integer[] int_arr = {100, 99, 80, 60 ,50, 101};
Arrays.sort(int_arr, new iComparator());
for (int i = 0; i < int_arr.length; i++)
System.out.print(int_arr[i]+ " ");
System.out.println();
// String 배열 선언
String[] s_arr = {"z", "a", "v", "s", "b", "m"};
Arrays.sort(s_arr, new sComparator());
for (int i = 0; i < s_arr.length; i++)
System.out.print(s_arr[i]+ " ");
System.out.println();
}
public static class iComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
public static class sComparator implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
}
}내림차순으로 정렬하는 Comparator 인터페이스를 직접 구현해 보았다.
@Override 어노테이션을 붙인 후, 각각의 배열에 해당하는 compare 함수를 재정의 하여 구현을 해보았다.
...
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
...
@Override
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
...알아두어야 할 것은 Comparator를 사용하는 정렬 메서드는 Comparator가 음수를 반환하면 비교된 두 수를 바꾸지 않는다.
따라서, 위와 같이 위치상으로 두번째 수와 첫 번째 수를 비교하여, 만약 음수또는 0인 경우에는 첫번째 수가 더 큰 것이므로, 자리를 바꾸지 않고 그대로 둔다. 즉, 내림차순 정렬인 것이다.
출력결과는 아래와 같다.
50 60 80 99 100 101
z v s m b a 결론
오늘은 간단하게 Arrays.sort에 대해서 알아보았다.
사실 코딩테스트를 준비하면서 여러 메소드들을 단지 외우고 이것을 복사 붙여넣기 하는 것 같아 회의감이 들어 원리를 파악하고자 하여 이 글을 준비하게 되었다.
"사실 코딩테스트에서 털리고 글을 작성하는 건 안 비밀"
해당 개념을 활용하여 해결할 수 있는 코딩테스트 문제를 하나 준비해보았다.
이 문제를 풀어보면서 Arrays.sort의 개념을 되새겨보자
REFERENCES
https://docs.oracle.com/en/java/javase/11/docs/api/index.html
https://ifuwanna.tistory.com/232
https://st-lab.tistory.com/243
https://hipopatamus.tistory.com/111
https://mine-it-record.tistory.com/133
https://velog.io/@injoon2019/%EC%9E%90%EB%B0%94-Comparator%EC%99%80-Comparable
