숫자라면 값을 크기에 따라 대소 비교, 문자열이라면 길이나 사전순서를 이용하여 비교하는 등 데이터의 종류에 따라 다양한 기준으로 정렬할 수 있습니다.
정렬 방법에 따른 시간 복잡도
- 버블 정렬: O(N^2)
- 선택 정렬: O(N^2)
- 삽입 정렬: O(N^2)
- 퀵 정렬: O(N^2)
- 합병 정렬: O(NlogN)
- 힙 정렬: O(NlogN)
이외에도 많은 종류의 정렬 알고리즘이 있습니다. 각 알고리즘은 원본 리스트의 상태에 따른 시간 복잡도와 사용하는 메모리 등 각각 장단점이 있습니다.
코딩 테스트에서는 최악의 경우 시간복잡도만 따지면 됩니다. 자바는 내장 정렬 메서드를 제공하므로 위의 정렬 방법들을 직접 구현할 필요는 없습니다. 위의 정렬 방법들을 개량한 정렬 알고리즘을 사용하기 때문에 O(NlogN) 시간 복잡도를 기대할 수 있습니다.
기본 정렬 기준
자바 내장 정렬 메서드는 기본 정렬 기준으로 정렬합니다.
| 대상 | 정렬 메서드 | 내용 |
|---|---|---|
| 배열 | Arrays.sort(배열) | 전달받은 배열을 정렬 |
| List, Vector, ... | Collections.sort(리스트) | 전달받은 Collection 정렬 |
| Stream | stream.sorted() | 정렬된 Stream을 반환 |
기저 자료형(primitive data type)
- 숫자형인 int, long, char, double, float
- 문자열인 String
기본 정렬 기준은 숫자형은 오름차순 문자열은 사전 순입니다.
자바는 이런 기저 자료형만 해당 기준이 정의되어있습니다.
int[] primitiveArray = {6,4,1,3,5,2};
Arrays.sort(primitiveArray); // [1,2,3,4,5,6]
그렇다면 primitive 자료형이 아닌 Object 자료형 또는 클래스를 정렬하거나 기저 자료형을 내림차순 등으로 내가 원하는 기준을 만들어 정렬하는 방법은 어떻게 할까요?
직접 기준 정하기
Comparator< T > 사용
자바의 정렬 메서드들은 하나의 추가 매개변수를 받을 수 있습니다.
| 대상 | 정렬 메서드 | 내용 |
|---|---|---|
| 배열 | Arrays.sort(Comparator< t > c) | 전달받은 배열을 정렬 |
| List, Vector, ... | Collections.sort(Comparator< t > c) | 전달받은 Collection 정렬 |
| Stream | stream.sorted(Comparator< t > c) | 정렬된 Stream을 반환 |
Comparator은 함수형 인터페이스이므로 메서드를 구현해줘야합니다.
Integer[] objectArray = {6,4,1,3,5,2};
Arrays.sort(objectArray, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o1 - o2; // 오름차순
//return o2 - o1; // 내림차순
}
})파라미터로 받는 두 원소(o1, o2)를 비교했을 때 reutn 되는 값의 부호가 두 객체의 비교 결과를 나타냅니다.
| 부호 | 비교 결과 |
|---|---|
| 0 | 두 객체가 같다. |
| 음수 | 왼쪽 객체가 더 크다. |
| 양수 | 오른쪽 객체가 더 크다. |
오름차순은 o1 - o2 값을 반환하는 것이고, 내림차순은 o2 - o1 값을 반환합니다.
제네릭 타입 사용
compare() 메서드의 매개변수가 int형이 아닌 Integer형인 것은,
제네릭 인터페이스인 Comparator< T >의 제네렉 메서드이기 때문입니다.
따라서 매개변수로 제네릭 타입인 T를 받는데, int형은 자바의 기저 자료형이므로 제네릭 타입으로 쓸 수 없습니다. 그 대신 int형의 wrapper class인 Integer를 사용하여 구현할 수 있습니다.
람다 사용
자바에서는 Comparator< T >처럼 하나의 메스드만 구현하면 되는 인터페이스를 람다로 쉽게 작성할 수 있습니다.
위의 코드처럼 Comparator< T > 객체를 만들어 compare() 메서드를 구현한 뒤 정렬 메서드인 sort()의 매게변수로 전달하는 코드를 람다를 사용하여 간단히 표현해봅니다.
Integer[] objectArray = {6,4,1,3,5,2};
Arrays.sort(objectArray, (o1, o2) -> o1 - o2)int[] primitiveArray = {6,4,1,3,5,2};
// stream을 이용한 내림차순
int[] reversed = Arrays.stream(primitiveArray) // int[]형 배열을 stream으로 변환
.boxed() // Stream<Integer>로 변환
.sorted((o1, o2)-> o2 - o1) // 내림차순 정렬
.mapToInt(Integer::intValue)
.toArray();
클래스 정렬
클래스를 직접 기준으로 정렬하는 방법은 두가지가 있습니다.
- Comparable Interface 구현하여 compareTo 메서드 오버라이딩 하기
static public class Member implements Comparable<Member>{
String name;
int age;
int joinNum;
public Member(String name, int age, int joinNum) {
this.name = name;
this.age = age;
this.joinNum = joinNum;
}
@Override
public int compareTo(Member o) {
if(age == o.age){
return joinNum - o.joinNum;
}
return age - o.age;
}
}- Comparator 사용하기
Member[] members = { ... };
Arrays.sort(members, (o1, o2)-> {
if(o1.age == o2.age){
return o1.joinNum - o2.joinNum;
}
return o1.age - o2.age;
});