안녕하세요 coding-knowjam입니다.
오늘은 정렬할 때 사용하는 대표적인 메서드 Arrays.sort()와 Collections.sort()에 대해 알아보겠습니다.
1. Arrays.sort()
1.1 API 문서 (Java 8)
문서 URL : https://docs.oracle.com/javase/8/docs/api/
API문서를 살펴보면 여러 가지 타입에 따라 사용할 수 있도록 overloading 된 sort() 메서드를 볼 수 있습니다.
그로 인해 우리는 Arrays.sort()에 char, int, boolean 등 과 같은 primitve(기본형) 타입과 reference(참조) 타입의 배열을 인자로 전달해서 사용할 수 있습니다. (배열만 사용 가능)
메서드에 매개변수로 Comparator를 받는 경우는 Comparable인터페이스에서 구현한 정렬 기준 외에 개발자가 정의한 다른 기준을 적용하고 싶을 때 사용합니다. (리터럴 타입의 배열은 사용할 수 없습니다.)
Comparator과 Comparable 관련해서는 따로 포스팅을 했으니 궁금하시면 아래 글을 검색해서 보시길 바랍니다.
[Java] Comparable / Comparator에 대해서 알아보자! (feat. 백준 알고리즘-1181)
또한 Arrays.sort()는 static메서드이므로 인스턴스를 생성하지 않고 바로 사용할 수 있습니다.
1.2 사용 방법
사용 방법에 대해서 간단하게 알아보겠습니다.
import java.util.Arrays;
import java.util.Collections;
public class Tistory_example {
public static void main(String[] args) {
System.out.println("--------int(기본형 타입) -----------");
// Integer
int[] intArr = {1,5,9,11,2,3,6,2,3,4,2};
// 오름차순 정렬 전
System.out.println("오름차순 정렬 전");
for(int i: intArr) {
System.out.print(i + " ");
}
System.out.println();
Arrays.sort(intArr);
// 오름차순 정렬 후
System.out.println("오름차순 정렬 후");
for (int i : intArr) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("-------- String(참조 타입) -----------");
// String
String[] strArr = {"한글", "코딩", "노잼", "자바", "배열", "정렬"};
// 가나다순 정렬 전
System.out.println("가다나순 정렬 전");
for(String i: strArr) {
System.out.print(i + " ");
}
System.out.println();
Arrays.sort(strArr);
// 가나다순 정렬 후
System.out.println("가다나순 정렬 후");
for (String i : strArr) {
System.out.print(i + " ");
}
System.out.println();
Arrays.sort(strArr, Collections.reverseOrder());
// 가나다 역순 정렬 후
System.out.println("가다나 역순 정렬 후");
for (String i : strArr) {
System.out.print(i + " ");
}
}
}
코드는 기본형 타입과 참조 타입으로 나눠서 작성해보았습니다.
10라인에서 int배열(기본형 타입)을 생성해주고, 19라인에 Arrays, sort() 메서드를 사용해서 정렬하였습니다.
참조 타입은 30라인에 String배열을 생성해주고, 39라인에 Arrayss.sort() 메서드를 사용해서 정렬하였습니다.
기본적으로 String이나 Integer클래스에서는 Comparable인터페이스를 구현하고 있기 때문에 배열 생성 후 정렬 메서드에 바로 사용할 수 있습니다.
만약에 개발자가 추가로 작성한 클래스라면 Comparable인터페이스를 구현해야만 Arrays.sort() 메서드를 사용할 수 있습니다.
기본적으로 숫자는 오름차순으로 정렬되며, 한글은 가나다순으로 정렬됩니다.
그러면 내림차순(역순)으로 정렬하고 싶을 때는 어떻게 해야 할까요??
Arrays.sort()에 Comparator인터페이스를 전달해서 기존의 Comparable에서 구현한 정렬 기준 말고 다른 기준으로 정렬할 수 있습니다. (참조 타입의 배열인 경우에만 사용 가능합니다)
이때, 개발자가 직접 Comparator인터페이스를 구현해서 매개변수로 사용해도 됩니다.
그러나 더 간단한 방식은 Collections.reverseOrder()를 사용하면 Comparable에서 구현된 정렬 기준의 역순으로 정렬할 수 있습니다.
Collections.reversOrder()에 대한 API문서도 한번 참고해보시면 좋습니다.
위의 코드를 실행하면 다음과 같습니다.
1.3 내부에서 어떤 정렬을 사용할까?
Arrays.sort()를 사용해서 배열을 정렬한다는 것은 알겠는데 내부적으로 어떤 정렬을 사용할까요??
우리가 정렬 알고리즘을 공부할 때 대표적으로 삽입, 선택, 버블, 힙, 퀵, 계수 정렬 등을 배우게 됩니다.
이 중에서 어떤 알고리즘을 사용할까요??
2가지의 경우로 나누어서 살펴보겠습니다.
1.3.1 primitive(기본형) 타입의 배열인 경우
기본형 타입의 배열인 경우는 DualPivotQuicksort를 사용합니다.
정말 그런지 확인을 하기 위해서는 실제 Arrays.class의 내부 소스를 보시면 됩니다.
앞서 작성했던 int배열을 파라미터로 받는 sotr함수의 내부 소스는 다음과 같습니다. (Java 8 기준)
/*
* Sorting methods. Note that all public "sort" methods take the
* same form: Performing argument checks if necessary, and then
* expanding arguments into those required for the internal
* implementation methods residing in other package-private
* classes (except for legacyMergeSort, included in this class).
*/
/**
* Sorts the specified array into ascending numerical order.
*
* <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
* by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
* offers O(n log(n)) performance on many data sets that cause other
* quicksorts to degrade to quadratic performance, and is typically
* faster than traditional (one-pivot) Quicksort implementations.
*
* @param a the array to be sorted
*/
public static void sort(int[] a) {
DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
}
일반적인 Quicksort의 경우 1개의 Pivot으로 정렬을 수행하지만 DualPivotQuicksort는 피벗을 2개 사용해서 정렬을 수행합니다.
Quicksort는 최악의 경우 O(N²), 평균적으로 O(NlogN)의 시간 복잡도를 가집니다.
DualPivotQuicksort은 랜덤 데이터에 대해 일반적인 Quicksort보다 나은 시간 복잡도를 보장하지만, 여전히 최악의 경우 시간 복잡도 O(NlogN)를 가집니다.
그러므로 만약에 정렬 알고리즘 문제 등등과 같이 시간 복잡도 O(NlogN)을 보장하는 정렬 코드를 작성해야 한다면 기본형 타입의 배열을 Arrays.sort()로 정렬하는 것은 다시 한번 생각해보셔야 할 것입니다.
사실 내부 로직을 깊게 파고들면 배열의 크기에 따라서 적용되는 정렬이 달라지지만 Arrays.sort()를 단순하게 사용하는 경우라면 나중에 필요에 의해서 소스코드를 분석해보는 것을 추천드립니다.
1.3.2 reference(참조) 타입의 배열인 경우
참조 타입의 배열인 경우는 TimSort를 사용합니다.
실제 내부 소스를 보면 다음과 같습니다. (Java 8 기준)
/** ~~~~~~~~
* ascending and descending order in different parts of the same
* input array. It is well-suited to merging two or more sorted arrays:
* simply concatenate the arrays and sort the resulting array.
*
* <p>The implementation was adapted from Tim Peters's list sort for Python
* (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
* TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic
* Sorting and Information Theoretic Complexity", in Proceedings of the
* Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
* January 1993.
*
* @param a the array to be sorted
* @throws ClassCastException if the array contains elements that are not
* <i>mutually comparable</i> (for example, strings and integers)
* @throws IllegalArgumentException (optional) if the natural
* ordering of the array elements is found to violate the
* {@link Comparable} contract
*/
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}
/** To be removed in a future release. */
private static void legacyMergeSort(Object[] a) {
Object[] aux = a.clone();
mergeSort(aux, a, 0, a.length, 0);
}24라인을 보면 ComparableTimSort클래스의 sort() 메서드를 사용하는 것을 알 수 있습니다.
22라인의 legacyMergeSort는 27라인의 주석을 보면 향후 릴리스 될 버전에서는 제거될 예정이므로 ComparableTimSort클래스의 sort() 메서드를 사용한다고 생각하시면 됩니다.
TimSort는 다른 프로그래밍 언어에서도 사용하고 있는 정렬방법으로 삽입 정렬(Insertion)과 병합 정렬(Merge)을 섞어서 정렬을 수행합니다.
TimSort의 시간 복잡도는 삽입 정렬과 병합 정렬의 장점을 가지고 있습니다.
위의 표를 보시면 TimSort는 최선의 상태에서는 삽입 정렬의 시간 복잡도 O(N)를 최악의 경우에는 병합 정렬의 시간 복잡도 O(N*logN)을 가집니다.
최악의 경우에도 O(N*logN) 시간 복잡도를 가지는 정렬 알고리즘이 필요하다면 Arrays.sort()가 TimSort를 수행할 수 있도록 primitive타입의 배열보단 reference타입의 배열을 사용해야 합니다.
내부에서 어떻게 정렬을 수행하는지에 대해서는 나중에 필요할 때 살펴보시는 걸 추천드립니다. (가성비 있게!)
2. Collections.sort()
2.1 API 문서 (Java 8)
API 공식문서에서 Collections.sort()를 찾아보시면 위와 같이 2개의 overloading 메서드가 있습니다.
List객체를 파라미터로 받는 경우는 제네릭 타입인 클래스가 Comparable를 구현하고 있어야 사용 가능합니다.
Comaparator를 파라미터로 받는 경우에는 제네릭 타입 클래스가 Comparable을 구현하고 있지 않아도 사용할 수 있습니다.
이러한 경우에는 Comparator 인터페이스에 구현된 정렬 기준으로 정렬이 수행됩니다.
2.2 사용방법
Collections.sort()의 사용방법은 아래와 같습니다.
package com.nojam.coding.algorithm;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class ArraysTest {
public static void main(String[] args) {
Integer[] intArr = {3,4,5,2,111,55,4326,22,42,11,156,784,433,9};
// Integer배열을 List로 변환
List<Integer> intList = Arrays.asList(intArr);
System.out.println("---------------- 숫자 오름차순 정렬 전 ------------------");
for(int i : intList) {
System.out.print(i + " ");
}
System.out.println();
Collections.sort(intList);
System.out.println("---------------- 숫자 오름차순 정렬 후 ------------------");
for(int i : intList) {
System.out.print(i + " ");
}
System.out.println();
System.out.println();
String[] strArr = {"한글", "영어","갤럭시", "경제", "유튜브", "삼성", "코딩노잼", "배열"};
// String배열을 List로 변환
List<String> strList = Arrays.asList(strArr);
System.out.println("---------------- 문자 가나다 역순 정렬 전 ------------------");
for(String s : strList) {
System.out.print(s + " ");
}
System.out.println();
// 가나다의 역순으로 정렬
Collections.sort(strList, Collections.reverseOrder());
System.out.println("---------------- 문자 가나다 역순 정렬 후 ------------------");
for(String s : strList) {
System.out.print(s + " ");
}
}
}
코드 자체가 간단해서 따로 설명드릴 부분이 있을까 싶지만 짧게 설명을 드리겠습니다.
11라인 : Integer배열 생성
13라인 : 11라인에서 생성한 배열을 List로 전환 (ArrayList 같은 구현 클래스로 객체 생성해도 됩니다)
20라인 : Integer클래스에서 구현한 Comparable인터페이스의 정렬 기준이 기본적으로 오름차순이므로 정렬도 오름차순으로 됩니다.
30라인 : String배열 생성
32라인 : 30라인에서 생성한 String배열을 List로 전환 (ArrayList 같은 구현 클래스로 객체 생성해도 됩니다)
40라인 : 기본적으로 String클래스도 Comparable인터페이스를 구현할 때 가나다순으로 정렬이 되도록 구현되어있습니다. 여기에 Arrays.sort()에서도 등장했던 Collections.reverseOrder()를 사용하면 가나다의 역순으로 정렬을 할 수 있습니다. Collections.reverseOrder() 메서드의 retrun타입이 Comparator인터페이스이라서 파라미터로 전달 가능하며, return 된 인터페이스는 Comparable에 정의된 정렬 기준의 역순으로 정렬을 수행합니다.
코드를 실행하면 아래와 같이 정렬이 정상적으로 수행된 걸 볼 수 있습니다.
2.3 내부에서는 어떤 정렬을 사용할까?
실제 내부 소스를 한번 살펴보겠습니다.
Collections.sort() 내부 소스를 보면 List인터페이스의 sort() 메서드를 실행합니다.
Collections.sort() 메서드에 Comparator인터페이스를 파라미터로 전달하면 list.sort(null)이 아니라 list.sort(Comparator)가 실행됩니다.
list.sort()를 타고 들어가면 아래와 같이 Arrays.sort()가 실행되는 걸 볼 수 있습니다.
즉, Collections.sort()에서는 List객체를 Object배열로 변환해서 Arrays.sort()를 실행해서 정렬을 수행합니다.
Arrays.sort() 내부를 살펴보면 다음과 같이 TimSort.sort()를 실행하는 걸 볼 수 있습니다.
legacyMergeSort() 메서드는 추후 릴리즈 될 버전에서는 사라질 것이므로 실제로 내부 소스는 파라미터로 받은 Comparator가 null이면 sort()를 null이 아니면 TimSort.sort()를 실행합니다.
sort() 메서드를 찾아가 보면 위에 Arrays.sort()에서 설명했던 ComparableTimSort.sort()를 실행합니다.
ComparableTimSort.sort()와 TimSort.sort()는 동일한 TimSort알고리즘을 수행하며 Comparator와 Comparable 둘 중 정렬 기준이 되는 객체에 따라서 수행하는 클래스명이 달라질 뿐입니다.
정말 그런지 궁금하시면 직접 소스를 확인하시면 됩니다만 제가 미리 해봤으므로 안 하셔도 무방합니다.
3. 정리
결국 정렬을 수행하기 위해서 사용되는 메서드는 Arrays.sort()입니다.
그러나 어떤 타입의 배열을 받느냐에 따라서 실행되는 정렬 알고리즘이 달라지는 것입니다.
표로 정리하면 다음과 같습니다.
'Java' 카테고리의 다른 글
| [Java] Map Interface의 유용한 메서드를 알아보자! (Java 8 기준) (0) | 2021.04.07 |
|---|---|
| [Java] Comparable / Comparator에 대해서 알아보자! (feat. 백준알고리즘-1181) (0) | 2021.01.14 |
댓글