자바에서 배열이나 리스트를 정렬할 때, sort() 메서드를 사용하여 간편하게 정렬할 수 있다.
Arrays.sort()
자바의 데이터 타입은 Primitive Type(원시 타입)과 Reference Type(참조 타입)으로 구분할 수 있다.
Primitive Type(원시 타입)
기본형(byte, char, short, int, long, float, dulble, boolean) 타입을 제공한다.
- default 값이 있으므로 Null이 존재하지 않는다.
- Stack(스택) 메모리에 실제 값을 저장한다.
Reference Type(참조 타입)
원시 타입을 제외한 모든 타입을 말한다. 배열, 열거, 클래스, 인터페이스 타입이 참조 타입에 해당된다.
- Null이 존재한다.(빈 객체)
- Heap(힙) 메모리에 실제 값이 아닌 실제 값이 저장된 주소 값을 저장한다.
배열의 정렬 방법은 원시 타입과 참조 타입 각각 다르다. 참조 타입의 경우, Comparable 인터페이스를 구현해서 사용해야 한다.
- 배열 정렬
- 객체 정렬
원시 타입 배열 정렬
배열은 기본적으로 오름차순으로 정렬된다.
int[] arr = {3, 6, 10, 1, 4, 2};
Arrays.sort(arr);
// Output: [1, 2, 3, 4, 6, 10]내림차순으로 정렬한다면, Collections 클래스의 reverseOrder()를 사용한다.
+) Collections는 collection에 사용할 정적 유틸리티 메서드 모음이 있는 java.util.Collections 클래스를 말한다.
int[] arr = {3, 6, 10, 1, 4, 2};
Arrays.sort(arr, Collections.reverseOrder());
// Output: [10, 6, 4, 3, 2, 1]객체(Object) 배열 정렬
객체로 이루어진 배열은 Comparable 인터페이스 구현이 필요하다.
class People implements Comparable {
private String name;
private int age;
public People(String name, int age){
this.name = name;
this.age = age;
}
@Override
public int compareTo(People people){
if(this.age < people.age) {
return -1;
} else if(this.age == people.age) {
return 0;
} else {
return 1;
}
}
}Comparable과 Comparator에 대해 알아보자.
자바에서는 Primitive Type의 변수는 부등호를 가지고 비교할 수 있다.
public class Test {
public static void main(String[] args) {
int a = 1;
int b = 2;
if(a > b) {
System.out.println("a > b");
}
else if(a == b) {
System.out.println("a == b");
}
else {
System.out.println("b > a");
}
}
} 그럼 나이와 이름을 갖고 있는 Member라는 클래스 객체가 생성된다면 이것은 어떻게 비교할까? 기준이 무엇일지 판단할 수 없다. 이를 해결하려면 정렬 기준을 정해줘야하고 Comparable 인터페이스를 구현했다. 그런데 찾아보면 Comparator라는 것도 확인할 수 있을 것이다.
Comparable VS Comparator
Comparable인터페이스의 compareTo(T o)와 Comparator의 compare(T o1, T o2) 차이는 무엇일까?
- Comparable: 자기 자신과 파라미터로 들어오는 객체를 비교한다.
- Comparator: 자기 자신의 상태와 상관없이 파라미터로 들어오는 두 객체를 비교한다.
+) comparable은 lang 패키지에 있지만, Comparator는 util 패키지에 있다.
즉, 두 인터페이스 모두 비교하는 것은 같지만 비교 대상이 다르다.
Comparable
Comparable 인터페이스를 확인해보면 다음과 같다.
public interface Comparable<T> {
public int compareTo(T o);
}<T>는 객체 타입이 지정될 자리를 말한다.
예를들어, Member 클래스를 비교한다면 T 자리에 Member가 들어가고 Comparable을 implements한다.
class Member implements Comparable<Member> {
int age;
String name;
Student(int age, String name){
this.age = age;
this.name = name;
}
@Override
public int compareTo(Member o) {
// 비교 구현
if(this.age > o.age) {
return 1; // 자기자신 age > o의 age -> 양수
}
else if(this.age == o.age) {
return 0; // 자기자신 age == o의 age -> 같다
}
else {
return -1; // 자기자신 age < o의 age -> 음수
}
}
} compareTo는 '값'을 비교해서 정수를 반환하는 방식이다. 1,0,-1은 각각 자기자신과 o의 값의 차를 의미한다. 즉 자기자신을 기준으로 비교하여 반환한 것이다.
+) 만약 비교 과정에서 범위를 넘어가게 된다면, underflow 또는 overflow가 발생할 수 있다.⭐️
Comparator
파라미터(매개 변수)로 들어오는 두 객체를 비교한다.
public interface Comparator<T> {
int compare(T o1, T o2);
...
} 확인해보면 Comparable과 인터페이스 형식이 유사하다.
이것을 가지고 클래스를 비교하는 코드를 작성한다면 다음과 같다.
import java.util.Comparator;
public class Member implements Comparator<Member> {
int age;
String name;
Student(int age, String name){
this.age = age;
this.name = name;
}
@Override
public int compare(Member o1, Member o2) {
/* 비교 구현 */
if(o1.age > o2.age) {
return 1;
}
else if(o1.age == o2.age) {
return 0;
}
else {
return -1;
}
/* 간단하게 작성한다면 다음과 같다.
return o1.Member - o2.Member;
*/
}
} Comparable의 경우, 자기자신과 비교하는 파라미터를 비교하지만 Comparator는 새로 들어오는 두 인자를 비교한다.
정렬
정렬하기 위해서는 비교하는 작업이 필요하다. 일단 대부분의 언어는 옵션을 지정하지 않는 이상 '오름차순'을 기준으로 정렬한다.
방금 알아본 Comparator와 Comparable의 작동방식을 정렬에 적용하면 다음과 같다.
- 결과가 음수인 경우: 두 원소의 위치를 교환 X
- 결과가 양수인 경우: 두 원소의 위치를 교환 O
대부분의 정렬 알고리즘은 '두 데이터를 비교'하여 교환할지 말지 결정한다.(counting sort 제외)
Comparable - compareTo(T o)
public class Test {
public static void main(String[] args) {
Member[] arr = new Member[10];
// 랜덤으로 배열 초기화
for(int i = 0; i < 10; i++) {
arr[i] = new Member((int) (Math.random() * 100));
}
// 정렬 이전
System.out.println("정렬 전 : ");
for(int i = 0; i < 10; i++) {
System.out.print(arr[i].age + " ");
}
System.out.println();
Arrays.sort(arr);
// 정렬 이후
System.out.println("정렬 후 : ");
for(int i = 0; i < 10; i++) {
System.out.print(arr[i].age + " ");
}
System.out.println();
}
}
class Member implements Comparable<Member> {
int age;
public Member(int age) {
this.age = age;
}
// 비교 기준을 생성한다.
@Override
public int compareTo(@NotNull Member o) {
return this.age - o.age;
}
}만약 Comparable을 구현하지 않았다면?
ClassCastException 예외가 나온다. 클래스를 비교할 수 있는 기준이 정의되지 않았기 때문이다.
Comparator - compare(T o1, T o2)
import java.util.Arrays;
import java.util.Comparator;
public class Test {
public static void main(String[] args) {
Member[] arr = new Member[10];
// 랜덤으로 배열 초기화
for (int i = 0; i < 10; i++) {
arr[i] = new Member((int) (Math.random() * 100));
}
// 정렬 이전
System.out.println("정렬 전 : ");
for (int i = 0; i < 10; i++) {
System.out.print(arr[i].age + " ");
}
System.out.println();
Arrays.sort(arr, comp);
// 정렬 이후
System.out.println("정렬 후 : ");
for (int i = 0; i < 10; i++) {
System.out.print(arr[i].age + " ");
}
System.out.println();
}
static Comparator<Member> comp = new Comparator<Member>() {
@Override
public int compare(Member o1, Member o2) {
return o1.age - o2.age;
}
};
}
class Member {
int age;
public Member(int age) {
this.age = age;
}
}Q. Arrays.sort(Object[] a)와 Arrays.sort(T[] a, Comparator<? super T>c) 차이는 무엇인가?🔎
Arrays.java를 살펴보자.
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);
}
}c가 null이면 sort(a)를 호출한다.
이것은 다음 메서드를 호출한다.
public static void sort(Object[] a) {
if (LegacyMergeSort.userRequested)
legacyMergeSort(a);
else
ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}즉, Comparator로 넘겨받은 인자가 null이면 Arrays.sort(Object[] a)를 호출하고, 정렬에 Comparable을 구현한 compareTo()를 사용한다.
만약 c가 null이 아니라면 Comparator을 구현한 객체의 compare() 메서드를 사용한다.
Q. 내림차순으로 정렬하고 싶다면? 🔎
compareTo를 구현할 때, 부호를 바꿔주면 된다.
내림차순은 작은 원소가 큰 원소보다 앞에 있는 것이니, 선행 원소 < 후행 원소일 때 선행 원소 - 후행 원소 < 0 이면 위치를 바꾸려면 음수 결과를 양수로 바꾸어야 한다.
ArrayList 정렬
Java에서 List 인터페이스는 다음과 같다.
public interface List<E> extends Collection<E> {
...
} 여기서 <E>는 Generic을 나타내는데 타입 파라미터로 명시할 수 있는 것은 참조 타입(Reference) 뿐이다. 또한 사용자 정의 클래스도 가능하다.
그럼 List는 어떻게 정렬할까?
Collections.sort()
Collections.sort() 코드를 살펴보면 list 인터페이스의 sort() 메서드를 실행한다.
public static <T extends Comparable<? super T>> void sort(List<T> list) {
list.sort(null);
}list.sort()를 확인해보면 1) List를 Array로 변경하고, 2) Arrays.sort() 가 실행된다. 이 안에서 sort 알고리즘을 확인해보면 Timsort()를 사용하고 있다.
@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);
}
}Collections.sort()를 사용하면 다음처럼 정렬할 수 있다.
Collections.sort(arraylist);Java8부터는 list.sort()를 제공한다. Comparator 인터페이스에서 구현된 메서드를 사용하여 정렬하면 된다.
arraylist.sort(Comparator.naturalOrder()); // 오름차순
arraylist.sort(Comparator.reverseOrder()); // 내림차순
arraylist.sort(String.CASE_INSENSITIVE_ORDER); // 대소문자 구분없이 오름차순 정렬
arraylist.sort(Collection.reverseOrder(String.CASE_INSENSITIVE_ORDER)); // 대소문자 구분없이 내림차순 정렬즉, 결국 정렬을 수행하기 위해서 사용되는 메서드는 Arrays.sort()이다.
어떤 정렬 알고리즘을 사용할까?
정렬 알고리즘은 primitive type과 reference type에 따라 구분된다.
- 기본형은 DualPivotQuickSort를 사용한다. DualPivotQuickSort는 Insertion Sort와 QuickSort를 섞은 것으로, 기존 QuickSort의 Pivot이 한개지만 Dual Pivot Quick Sort는 Pivot을 2개 사용한다.
- 참조형은 TimSort를 사용한다. TimSort는 Insertion Sort와 Merge Sort를 섞은 것을 말한다.
자세한 알고리즘은 추후에 알아보도록 하겠다.
Summary
- Java의 정렬은 결국 Arrays.sort()로 정렬한다.
- 원시 타입은 부등호를 가지고 크기를 비교할 수 있지만, 참조 타입은 비교 기준이 정해져 있지 않으므로 Comparable 또는 Comparator를 구현한다.
Comparable - compareTo(T o): 자기 자신과 파라미터로 들어오는 객체를 비교한다.Comparator - compare(T o1, T o2): 자기 자신의 상태와 상관없이 파라미터로 들어오는 두 객체를 비교한다.- 선택한 정렬 알고리즘은 primitive type과 reference type에 따라 다르다.
- primitive type(기본형): DualPivotQuickSort
- reference type(참조형): TimSort
Reference
- https://codechacha.com/ko/java-sorting-array/
- https://defacto-standard.tistory.com/38
- https://st-lab.tistory.com/243
- https://hianna.tistory.com/569
- https://codingdog.tistory.com/entry/java%EC%9D%98-arrayssort-%EB%A9%94%EC%84%9C%EB%93%9C%EB%8A%94-%EC%96%B4%EB%96%A4-%EC%A0%95%EB%A0%AC%EC%9D%84-%EC%82%AC%EC%9A%A9%ED%95%A0%EA%B9%8C%EC%9A%94
- https://codingnojam.tistory.com/38
