무엇을 배웠나

• 코딩테스트 연습

확장학습

Arrays.sort()의 정렬 알고리즘

'Arrays.sort()' 메서드는 배열을 오름차순으로 정렬하는 데에 사용된다. 이 메소드를 사용하면 배열의 모든 요소를 오름차순으로 정렬할 수 있다. 내부적으로는 Dual-Pivot Quicksort 알고리즘을 사용하며, 평균적으로 O(n log n)의 시간 복잡도를 가진다.

Dual-Pivot Quicksort는 기존의 Quicksort와 비슷하지만, pivot을 두 개 사용하여 성능을 향상시킨 알고리즘이다. 퀵소트(Quicksort)와 Dual-Pivot Quicksort의 가장 큰 차이점은 피봇을 사용하는 방식이다.

퀵소트(Quicksort) 알고리즘은 하나의 피봇을 사용하여 배열을 두 개의 부분 배열로 분할한다. 피봇을 선택하고, 피봇보다 작은 요소들은 피봇의 왼쪽에 배치되고, 피봇보다 큰 요소들은 피봇의 오른쪽에 배치된다. 이렇게 분할된 두 부분 배열에 대해 같은 과정을 재귀적으로 수행하면 최종적으로 정렬된 배열을 얻을 수 있다.

Dual-Pivot Quicksort 알고리즘은 퀵소트의 변형 버전으로, 두 개의 피봇을 사용하여 배열을 세 개의 부분 배열로 분할한다. 보통 첫 번째 요소와 마지막 요소를 두 피봇으로 선택하며, 첫 번째 피봇보다 작은 요소들은 왼쪽에, 두 번째 피봇보다 큰 요소들은 오른쪽에, 그 사이의 요소들은 중간에 배치된다. 이렇게 분할된 세 부분 배열에 대해 같은 과정을 재귀적으로 수행하면 최종적으로 정렬된 배열을 얻을 수 있다.

원시 타입 배열 (예: int[], double[] 등)에는 Dual-Pivot Quicksort 알고리즘이 사용되지만, 사용자 정의 객체 배열 (예: Object[] 등)에 대해서는 TimSort 알고리즘이 사용된다. TimSort는 안정적인 정렬 알고리즘으로, 객체의 순서가 중요한 경우에 적합하다. 사용자 정의 객체는 종종 특정 필드 또는 메소드를 기반으로 비교되며, 이러한 비교를 수행하는 데에는 TimSort가 더 적합하다.

TimSort는 Insertion Sort와 Merge Sort의 원칙을 결합한 효율적인 정렬 알고리즘이다. TimSort가 다른 정렬 알고리즘들에 비해 우수한 성능을 보이는 이유는, 데이터의 특성에 따라 최적의 정렬 전략을 선택하고, 이미 정렬된 시퀀스를 활용할 수 있다는 점이다. TimSort의 동작 방식은 다음과 같다.

1) 원본 데이터를 작은 '런'들로 나눈다. 런은 연속적인 데이터 항목 그룹으로, 오름차순 또는 내림차순으로 데이터가 정렬된 상태를 나타내는 말이다.

2) 각 런을 Insertion Sort를 사용하여 정렬한다. 이 단계에서는 데이터의 일부분만을 대상으로 하므로 Insertion Sort의 느린 속도가 문제가 되지 않는다.

3) 이후에, Merge Sort를 이용하여 두 개의 런을 병합한다. 이 단계에서는 두 개의 정렬된 런을 효율적으로 병합하여 더 큰 정렬된 런을 만든다.

4) 이 과정은 모든 런이 하나의 정렬된 런이 될 때까지 반복된다.

Insertion Sort는 간단하고 비교적 느린 정렬 알고리즘이다. 이 방법은 각 항목을 이미 정렬된 부분에 적절한 위치로 삽입함으로써 작동한다. 알고리즘은 각 단계에서 하나의 데이터 항목을 선택하고, 이 항목을 이미 정렬된 항목 목록에 적절한 위치에 삽입한다. 이 과정은 모든 데이터가 정렬된 목록에 포함될 때까지 반복된다.

여기서 의문이 생긴다. 정렬하지도 않았는데, 어떻게 이미 정렬된 부분이 존재하고, 그 지점이 작동지점이 될 수 있을까. 이에 대한 답은 상태가 어떻든 정렬된 부분이 반드시 존재하기 때문에, Insertion Sort의 작동은 필연적으로 가능하다는 것이다. 처음에는 첫 번째 요소만을 '정렬된 부분'으로 보고, 이후에는 하나씩 추가하면서 '정렬된 부분'을 확장해나간다. 이렇게 하면서 추가하는 각 요소를 '정렬된 부분' 내에서 알맞은 위치에 삽입해 나가는 것이다. Insertion Sort는 요소의 일부가 이미 정렬된 상태라면 효율적으로 작동하는 알고리즘이지만, 전체가 무작위로 섞여있는 상태라도 잘 동작한다. 이 알고리즘의 핵심 아이디어는, 각 반복마다 배열(혹은 리스트)의 '정렬된 부분'을 확장하는 것이다.

예를 들어, 리스트 [4, 3, 2, 1]이 있다고 해 보자. Insertion Sort는 먼저 4만을 정렬된 부분으로 보고 시작한다. 그 다음에는 3을 정렬된 부분인 [4]에 적절한 위치에 삽입하려 시도하게 되는데, 이 경우 4 앞에 3을 삽입하므로 [3, 4]가 된다. 이런 식으로 계속 진행하면 전체 리스트가 정렬된 상태가 된다.

이처럼 Insertion Sort는 정렬되지 않은 입력에 대해서도 잘 동작하지만, 이미 어느 정도 정렬된 상태의 입력에 대해서는 훨씬 빠르게 동작한다. 이 때문에 TimeSort에서는 입력 리스트를 일정 크기의 런으로 나누고, 각 런을 Insertion Sort로 먼저 정렬한 후에 Merge Sort 단계를 거치는 방식을 사용하는 것이다.

Merge Sort는 분할 정복 전략을 따르는 효율적인 정렬 알고리즘이다. 이 알고리즘은 원래의 데이터를 절반으로 분할하고, 각 부분을 재귀적으로 정렬한 다음, 두 개의 정렬된 부분을 병합함으로써 작동한다. 이 방법은 데이터를 두 부분으로 분할하고, 각각을 정렬한 다음 다시 병합하여 전체를 정렬하는 방식이다.

종합해보면, TimSort는 Merge Sort와 Insertion Sort의 원리를 결합하여 사용하는 효율적인 정렬 알고리즘이다. 이 알고리즘은 주어진 데이터를 작은 런(run)이라고 불리는 연속된 요소 그룹으로 분할한다. 각 런은 이미 정렬된 상태이며, 오름차순 또는 내림차순으로 정렬되어 있다.

TimSort의 첫 번째 단계는 주어진 데이터를 작은 런으로 분할하는 것이다. 이때, 이미 정렬된 부분 런을 최대한 활용하여 성능을 개선한다. 그 후, 분할된 각 런에 대해 Insertion Sort를 수행하여 빠르게 정렬한다. Insertion Sort는 작은 데이터 집합에 대해서 빠르게 작동하는 알고리즘이기 때문에, 런의 크기가 작은 경우에 이를 활용하여 최적의 성능을 달성한다.

두 번째 단계는 정렬된 런들을 병합하는 것이다. Merge Sort의 원리를 사용하여 두 개의 정렬된 런을 효율적으로 병합하고, 더 큰 정렬된 런을 생성한다. 이 과정을 반복하여 모든 런이 하나의 정렬된 런이 될 때까지 진행한다.

TimSort의 주요 장점은 데이터의 특성을 고려하여 최적의 정렬 전략을 선택할 수 있다는 것이다. 이미 정렬된 부분이나 작은 크기의 런은 추가 정렬 작업 없이 그대로 활용할 수 있으므로 성능을 향상시킬 수 있다. 또한, 안정적인 정렬 알고리즘으로서 데이터의 순서가 중요한 경우에 적합하다.

이렇게 TimSort는 Insertion Sort와 Merge Sort의 원리를 결합하여 성능과 안정성을 모두 갖춘 정렬 알고리즘이다. 사용자 정의 객체의 정렬에도 적용 가능하며, 데이터의 특성과 상황에 따라 최적의 정렬 전략을 선택하여 효율적인 정렬을 수행할 수 있다.