Lambda의 정렬 알고리즘 (List Sort)

글 내용과 관련된 프로그래머스 문제 풀이

List.sort((o1, o2) -> 비교식(비교 결과 값) )

위의 코드는 Comparator 인터페이스의 compare 메서드를 구현한 람다 표현식입니다.
이 람다 표현식은 o1과 o2 두 객체를 비교하여 정렬하게됩니다.

내부 메서드 동작 과정

1. list.sort((o1, o2) -> 비교식(비교 결과 값) ) 호출

2. List.sort() 메서드가 호출되어 Comparator 를 인수로 받음

3. List.Sort() 는 내부적으로 Collections.sort() 를 호출

4. Collections.sort() 는 TimSort 알고리즘을 사용하여 리스트 정렬

   • TimSort 알고리즘은 병합 정렬과 삽입 정렬을 결합하여 만든 정렬로, 시간복잡도는 O(nlogn)

5. TimSort 알고리즘은 정렬 과정에서 Comparator 의 compare 메서드를
   반복적으로 호출하여 두 객체를 비교

여기서 비교식(비교 결과 값) 이 부분은 결과 값에 따라 정렬이 이루어지게 되는데,
값이 양수, 0, 음수 임에 따라 정렬 알고리즘이 객체의 순서를 결정하게 됩니다.

• 양수: 첫 번째 객체가 두 번째 객체보다 큼 (순서 변경)
• 0: 두 객체가 같음 (순서 변경X)
• 음수: 첫 번째 객체가 두 번째 객체보다 작음 (순서 변경X)

결과 값이 양수일 때만 객체 간 순서 변경이 일어나게 됩니다.

비교식은 아래와 같이 o1 - o2 이렇게 간단하게 작성할 수 있습니다.

list.sort((o1, o2) -> {
	o1 - o2
});

하지만 이 방식을 사용하면 다음과 같은 문제가 발생할 수 있습니다
(1) 오버플로우 및 언더플로우 발생
(2) 부동소수점(double, float) 연산에서는 결과 값이 정확하지 않을 수 있음

여기서 (1) 문제의 예시로는 o1 = Integer.MAXVALUE, o2 = -1 일 때, o1 - o2 를 했을 시
오버플로우가 발생하게 됩니다.

이 문제를 해결하기 위해 Comparable 인터페이스의 compareTo() 메서드를 사용할 수 있습니다.
해당 메서드는 두 객체를 비교하여 순서를 결정하므로, 비교 과정에서 발생할 수 있는 오버플로우, 언더플로우 등의 문제를 방지합니다.

(2) 문제의 예시로는 (int) (o1 - o2) 처럼 결과를 int로 변환하는 경우, 소수점 이하의 값이
손실되므로 결과가 달라질 수 있습니다. 만약 o1 = 0.2, o2 = 0.1인 경우, 결과는 0.1 이지만,
이를 int로 타입 캐스팅 하는 경우 0 이 됩니다.

compareTo() 메서드는 (2) 문제인 부동소수점 연산 문제도 나타나지는 않지만, 부동 소수점 연산의 경우에는
Double 클래스의 compare() 메서드를 사용하는 것이 더 적절하며 이유는 다음과 같습니다.

compareTo() 메서드의 사용 목적은 객체 간의 비교를 위한 것이지만, Double.compare() 메서드는
부동소수점의 값의 비교를 위해 사용되는 것이므로 더 목적에 부합합니다.

Double 클래스가 제공하는 메서드인 Double.compare()

public static int compare(double d1, double d2)

Double.compare() 를 사용하여 다음 과 같이 작성할 수 있습니다.

list.sort((o1, o2) -> {
	Double.compare(o1, o2)
});

추가) Integer 클래스가 제공하는 메서드인 Integer.compare()

public static int compare(int x, int y)

이를 사용하면 정수 비교도 안전하게 수행할 수 있습니다.