[Java] 오름차순 정렬, 내림차순 정렬 Arrays.sort(), Collections.sort(), Collections.reverse()

* JDK 1.8부터 배열 <-> 컬렉션을 컨버팅하는 방법이 바뀌었다. 아래 글 참조바란다.

https://defacto-standard.tistory.com/20

Arrays.sort()는 Primitive Type이나 Object Type의 Array를 정렬할 때 쓰고

Collections.sort()는 Collection의 List를 정렬할 때 쓴다.

기본적으로 둘 다 오름차순 정렬이고, 인자로서 Array 또는 List를 넣어주면 인자로 넘겨진 객체의 내용 자체가 바뀐다.

둘 다 static method이므로 Arrays나 Collections객체를 생성하는 것이 아니라 바로 호출한다.

Arrays.sort(), Collections.sort() 모두 Comparator를 통한 커스터마이즈 정렬을 지원한다.

Collections.reverse()는 내림차순 정렬이 아닌, 리스트의 구성을 반대로 뒤집는 것이다.

- 오름차순

< Arrays.sort(int[] a) 사용 >

int[] arr = {2, 4, 9, 7, 5, 2};

for(int element : arr) {
    System.out.print(element);
}

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

for(int element : arr) {
    System.out.print(element);
}

< Collections.sort(List<T> list) 사용 >

int[] arr = {2, 4, 9, 7, 5, 2};

for (int element : arr) {
    System.out.print(element);
}

System.out.println();

// convert Primitive Array to List
List<Integer> list = Arrays.stream(arr).boxed().collect(Collectors.toList());

// arr 배열은 그대로이며, list는 arr배열의 오름차순으로 저장된다.
Collections.sort(list);

for (int element : list) {
    System.out.print(element);
}

- 내림차순

< Arrays.sort(T[] a, Comparator<? super T> c) 사용 >

int [] arr = {2, 4, 9, 7, 5, 2};

for(int element : arr) {
    System.out.print(element);
}

System.out.println();

// to boxed Array
Integer[] integerArr = Arrays.stream( arr ).boxed().toArray( Integer[]::new );
Arrays.sort(integerArr, Comparator.reverseOrder());

for(int element : integerArr) {
    System.out.print(element);
}

< Collections.sort(List<T> list, Comparator<? super T> c) >

int[] arr1 = {2, 4, 9, 7, 5, 2};
int[] arr2 = {2, 4, 9, 7, 5, 2};

for(int element : arr1) {
    System.out.print(element);
}

System.out.println();

for(int element : arr2) {
    System.out.print(element);
}

System.out.println();

// 방법1
List<Integer> integerArr1 = Arrays.stream(arr1).boxed().sorted(Comparator.reverseOrder()).collect(Collectors.toList());

for(int element : integerArr1) {
    System.out.print(element);
}

System.out.println();

// 방법2
List<Integer> integerArr2 = Arrays.stream( arr2 ).boxed().collect(Collectors.toList());
Collections.sort(integerArr2, Comparator.reverseOrder());

for(int element : integerArr2) {
    System.out.print(element);
}

* 참고

Arrays는 하나의 알고리즘만을 쓰는 것이 아니다.

기본적으로 Insertion Sort, Merge Sort, Quick Sort 3가지를 쓴다.

예전에는 이 3개가지 Sorting이 구분되어서 사용되었지만

현재는 이를 변형한 Tim Sort, Dual-Pivot Quick Sort 를 쓴다고한다.

<예전 기준>

1. 배열의 크기가 아주 작을 때(7개 미만) -> Insertion Sort

왜 7개 미만일 때는 Insertion Sort를 쓰는지에 대해선 수학적으로, 그리고 빅오 표기법의 맹점에 대해 접근할 수 있다.

Insertion Sort는 2개의 대상일 땐 1번 비교, 3개의 대상일 땐 2번 비교, 4개의 대상일 땐 3번 비교를 한다.

즉, n개일 때 n-1번 비교한다. 이는 1 + 2 + ... + n-1 + n 이고 이는 n(n-1)/2 라는 공식이 나온다.n^2이 영향이 가장 크므로 빅오 표기법으로는 O(n^2)가 되지만 정확히는 n(n-1)/2이다.

n=6일 때는 6*5/2 = 15 라는 값이 나오며 n=7일때는 7*6/2 = 21이라는 값이 나온다.

Merge Sort는 이다.

n=6일 때는 = 15.509라는 값이 나오며 n=7일 때는 19.651 이라는 값이 나온다.

따라서 n=6일 때는 일반적으로 Insertion Sort가 유리하며 n=7일 때는 Merge Sort가 유리하므로

n=6 이하일 때는 Insertion Sort를 쓰는 것이 빠른 경우이며 n=7이상 일 때는 Merge Sort를 쓰는 것이 빠른 경우이다,

게다가, Insertion의 Worst Case는 정렬할 데이터가 완전히 역순일 때 해당되는 것이고 이러한 경우는 아주 특별한 케이스이기 때문에

그냥 무시하고 평균적으로 n=6일 때 Insertion Sort가 더 빠르므로 이를 사용하는 것이다.

빅오 표기법으로는 Merge Sort가 훨씬 빠르지만 n=6일 때는 말이 다르다는 것이다. 이것이 빅오 표기법의 맹점이다.

2. Merge Sort와 Quick Sort를 사용하는 여부는 Sorting 알고리즘의 Stable과 관계가 있다.

Stable이란 안정성을 의미하는데, 정렬에서의 Stable은 같은 값을 비교했을 때 그 순서가 바뀌는지 안바뀌는지를 의미한다.

잘 생각을 해보면 Primitive Type Array를 정렬한다는 것은 말 그대로 어떠한 값이 더 크고 작은지를 따지며, 같은 값을 가지는 2개의 숫자를 구분(크기 비교가 아니라 이 숫자 자체를 구분)할 방법이 없다.

예를 들어 2 1 2 3 이라는 배열을 오름차순 정렬하면 1 2 2 3이 된다. 이때 2와 2는 서로 같은 값을 가지지만 정렬하는 과정에서 그 상대적인 위치가 바뀔 수 있다. 하지만 애초에 Primitive Type끼리는 구분할 수도 없고, 별다른 영향이 없기에 구분할 필요도 없다.

이러한 것을 Not Stable하다고 한다. Merge Sort를 써도 상관 없으나, 일반적으로 Quick Sort가 더 빠르므로 Primitive Type은 Quick Sort를 사용하여 정렬한다.

Quick Sort가 Merge Sort보다 값에 대한 비교를 더 많이 한다고 할지라도 Array에 대한 Access 횟수가 적기 때문에 크게 봤을 때 더 빠르다. Quick, Merge Sort가 둘다 분할 정복법에 기반하여서 서브 리스트를 나누어 작은 배열을 정렬하는 방식을 사용한다.

일반적으로 Quick Sort가 Merge Sort가 빠른 이유는

Quick Sort는 어느 정도 정렬을 하면서 서브리스트로 분할하고 마지막에도 정렬을 하지만

Merge Sort는 쪼개질 수 없을 때까지 나눈 후 이를 합칠 때 부터서야 조금씩 정렬하기 때문이다.

반대로 Object Array는 말이 달라진다. 객체는 주소를 가지고 있고 엄연히 구분될 수 있는 것이기 때문에 구분을 할 필요가 있다.

따라서 이러한 Object Sorting은 Stable한 정렬 방법을 써야한다. 특정 어플리케이션에서, 값은 같은데 객체 자체가 다른 경우, 개발자가 생각한 것과 다른 결과물을 낼 수 있기 때문이다. 그리고 Stable한 정렬 방법 중 빠른 편에 속하는 것이 Merge Sort이다.

정리를 하자면,

Primitive Type Array는 Quick Sort

Object Type Array는 Merge Sort를 쓴다.

Quick Sort는 Not Stable 하고, Merge Sort는 Stable하다.

<현재 기준>

예전에는 3개의 알고리즘이 완전히 나뉘어 졌지만, 지금은 Insertion Sort와 Merge Sort를 합친 TimSort라는 것을 사용하고

Quick Sort역시 그냥 쓰는게 아니라 Dual-pivot Quick Sort라는 것을 사용한다.

3개의 알고리즘을 쓰는 것은 같지만 알고리즘의 변형이 생긴 것이다.

TimSort는 역시 Stable하므로 Object에, Dual-pivot Quick Sort는 Not Stable하므로 Primitive Type에 쓰인다.

또한 Quick Sort는 nlog2n의 퍼포먼스를 보장하지 않지만 Merge Sort는 Worst Case라도 반드시 nlog2n을 보장한다.