자바의 여러가지 정렬 방법

🤔 자바의 정렬

• 자바에서는 데이터를 정렬하는 여러가지 방법을 제공한다.
• 이러한 정렬 기능들은 코딩 테스트를 풀 때 유용하게 사용된다.
• 기본적으로 오름차순, 내림차순을 넘어 정렬 기준을 입맛대로 정의하여 코딩테스트에서 유용하게 사용해보자

😤 Arrays.sort()

int[] numbers = {5, 3, 9, 1, 6};
Arrays.sort(numbers); // 오름차순 정렬

• 배열을 정렬할 수 있는 기본적인 정렬 기능이다.
• int, long, short, double 등 기본 타입에 대한 정렬을 지원한다.

[내림차순]

• 오름차순만 지원하기 때문에 내림차순을 구현하기 위해선 정렬 기준을 Comparator 로 설정해줘야 한다.

int[] numbers = {5, 3, 9, 1, 6};
Arrays.sort(numbers, Collections.reverseOrder());

• 미리 정의되어있는 Comparator Collections.reverseOrder() 를 사용하여 내림차순 정렬을 할 수 있다.

Comparator 는 뒤에서 자세하게 다룬다.

[구현방식]

• 이 메서드는 내부적으로 Quick Sort 를 개선한 DualPivotQuickSort를 사용한다.
• 예외로 Integer[] 와 같은 객체 배열에는 삽입정렬과 합병정렬을 결합한 정렬인 TimSort 를 사용한다.

😮 Collections.sort()

List<Integer> numbers = Arrays.asList(5, 3, 9, 1, 6);
Collections.sort(numbers); // 오름차순 정렬

• List 와 같은 컬렉션에 대해서는 Collections.sort() 를 사용해야 한다.
• 마찬가지로 기본적으로 오름차순으로 정렬되며 다른 정렬 기준을 사용하려면 직접 정의해야 한다.
• 내부적으로 TimSort 알고리즘을 사용한다.

[DualPivotQuickSort vs TimSort]

	정렬 방식	시간 복잡도(평균)	시간 복잡도(최악)
Arrays.sort()	DualPivotQuickSort	O(nlog(n))	O(n^2)
Collections.sort()	TimSort	O(nlog(n))	O(nlog(n))

• 위와 같은 성능차이 때문에 코딩 테스트에서 간혹 Arrays.sort() 를 사용했을 때 시간초과가 발생하는 경우가 있다.
• 때문에 만약 시간초과가 난다면 이를 의심해보고 배열을 List<Integer> 등으로 바꿔서 Collections.sort() 를 써보자.

🤯 Comparator와 Comparable로 정렬 기준 정의

• 자바에서는 객체의 정렬 기준을 직접 정의하고 싶을 때 Comparable 인터페이스 또는 Comparator 인터페이스를 구현하여 정의한다.

[Comparable]

• compareTo 메서드를 오버라이드하여 클래스 안에 정렬 기준을 명시한다.
• 메서드의 반환 타입은 항상 int 이다.

class Person implements Comparable<Person> {
    private String name;
    private int age;

    @Override
    public int compareTo(Person other) {
        return this.age - other.age;  // 나이 기준 오름차순 정렬
    }
}

List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));
Collections.sort(people);  // 나이를 기준으로 오름차순 정렬
// {Bob : 25}, {Alice : 30}

• compareTo 반환 규칙
  • 음수 : 호출하는 객체가 매개 변수로 전달된 객체보다 작을 때(this가 other보다 작을 때)
  • 0 반환 : 두 객체가 같을 때
  • 양수 반환 : 호출하는 객체가 매개 변수로 전달된 객체보다 클 때
• 누가 더 큰지를 알 수 있는 compareTo 메서드를 통해서 정렬을 수행한다.

[Comparator]

• 외부에서 새로운 정렬 기준을 정의하여 Collections.sort()의 인자로 넣을 수 있다.

List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));

// 나이 내림차순 정렬
Comparator<Person> byAgeDescending = new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        return p2.getAge() - p1.getAge();  // 내림차순 정렬
    }
};

Collections.sort(people, byAgeDescending);
System.out.println(people); // {Alice : 30}, {Bob : 25}

😎 람다 표현식을 사용한 정렬

• 자바 8부터는 람다 표현식을 사용하여 더 간결하게 정렬 기준을 명시할 수 있다.

List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 25));

// 나이로 오름차순 정렬
people.sort((p1, p2) -> p1.getAge() - p2.getAge());

// 이름으로 알파벳 순 정렬
people.sort((p1, p2) -> p1.getName().compareTo(p2.getName()));

누군가가 물어본다면

자바가 제공하는 Arrays.sort(), Collections.sort() 로 쉽게 정렬 기능을 사용할 수 있고, Comparator 와 Comparable로 원하는 정렬 기준을 만들 수 있습니다.

자바 8부터는 람다 표현식을 사용하여 보다 깔끔하게 정렬 기준을 정의할 수 있습니다.