Timsort

Timsort는 병합 정렬과 삽입 정렬을 결합한 정렬 알고리즘으로, 실제로 효율성이 좋습니다. Tim Peters가 2002년에 이 알고리즘을 설계했으며 Python에서 사용됩니다 (TimSort는 Python에서 list.sort의 기본 구현입니다). 이 알고리즘은 정렬된 블록 (데이터의 파티션)을 찾으며, 각 파티션을 런이라고 하며, 특정 규칙에 따라 이러한 런을 병합합니다. Python은 버전 2.3부터 정렬을 위해 Timsort 알고리즘을 사용하고 있습니다. 현재 Java SE7 및 Android도 배열을 정렬하기 위해 Timsort 알고리즘을 사용합니다.

1. Operations

실제로 대부분의 데이터는 이미 정렬된 일부 부분을 가지고 있으며 Timsort는 이 기능을 활용합니다. Timsort의 입력 단위는 개별 숫자가 아니라 파티션입니다. 각 파티션을 "런"이라고 합니다 (그림 1). 이러한 런 시퀀스의 경우 매번 하나의 런을 꺼내어 병합합니다. 각 병합은 두 개의 런을 하나의 런으로 결합합니다. 각 런은 최소 2개의 요소를 가져야 합니다. Timsort는 각 런을 오름차순 및 내림차순으로 나눕니다. 런이 오름차순인 경우 런의 다음 요소는 이전 요소보다 크거나 같아야 합니다 (a[lo] <= a[lo + 1] <= a[lo + 2] <=...); 런이 엄격한 내림차순인 경우, 즉 런의 이전 요소가 다음 요소보다 큰 경우 (a[lo] > a[lo + 1] > a[lo + 2] >...), 런의 요소를 뒤집어야 합니다 (내림차순 부분은 뒤집히려면 "엄격하게" 내림차순이어야 합니다. TimSort의 중요한 목표는 안정성을 유지하는 것이기 때문입니다. >=의 경우에 반전이 수행되면 알고리즘은 더 이상 안정적이지 않습니다).

1.1 Minimum Length of Run

런은 정렬된 파티션입니다. 런은 길이가 다를 수 있으며 Timsort는 런 길이에 따라 정렬 전략을 선택합니다. 예를 들어 런 길이가 특정 값보다 작으면 삽입 정렬 알고리즘이 정렬에 선택됩니다. 런의 최소 길이 (minrun)는 배열 크기에 따라 달라집니다. 배열 요소 수가 64보다 작으면 런의 최소 길이는 배열 길이이고 Timsort는 정렬에 삽입 정렬 알고리즘을 사용합니다. 배열 요소 수가 63보다 크거나 같으면 배열의 크기를 최소 런 크기로 나눈 값이 2의 거듭제곱과 같거나 약간 작은 32에서 65 범위의 minrun이라는 숫자가 큰 배열에 대해 선택됩니다. 이를 위한 최종 알고리즘은 단순히 배열 크기의 가장 중요한 6비트를 가져와 나머지 비트가 설정된 경우 1을 더하고 해당 결과를 minrun으로 사용합니다. 이 알고리즘은 배열 크기가 64보다 작은 경우를 포함하여 모든 경우에 작동합니다.

1.2 Optimizing Run Length

런 길이 최적화는 런 길이가 minrun보다 작을 때 이러한 런 길이가 minrun 길이에 도달하도록 배열에서 적절한 요소를 선택하여 런에 삽입됨을 의미합니다. 이렇게 하면 대부분의 런 길이가 균형을 이루게 되어 후속 런 병합에 도움이 됩니다.

1.3 Merging Runs

런을 분할하고 런 길이를 최적화한 후 다음 단계는 런을 병합하는 것입니다. 런 병합 원칙은 병합 기술에서 가장 높은 효율성을 보장하는 것입니다. Timsort 알고리즘이 런을 찾으면 배열에서 런의 시작 위치와 런 길이를 스택에 넣은 다음 스택에 이전에 푸시된 런에 따라 런을 병합할지 여부를 결정합니다. Timsort는 스택에서 연속되지 않은 런을 병합하지 않습니다 (Timsort는 연속되지 않은 런을 병합하면 세 런 모두에 공통적인 요소가 중간 런에 대해 순서가 어긋날 수 있기 때문에 병합하지 않습니다).

Timsort는 스택에서 연속된 두 런을 병합합니다. X, Y 및 Z를 스택 맨 위에 있는 세 런의 길이를 나타냅니다 (그림 2). 다음 두 조건이 동시에 충족되지 않으면 다음 두 조건이 동시에 충족될 때까지 두 런 X와 Y가 병합된 다음 병합이 종료됩니다.

1. X>Y+Z
2. Y>Z

예를 들어 X<Y + Z이면 X + Y가 병합되어 새 런이 된 다음 스택에 푸시됩니다. 위의 단계를 두 조건이 동시에 충족될 때까지 반복합니다. 병합이 종료된 후 Timsort는 다음 런을 계속 찾은 다음 찾은 후 스택에 푸시합니다. 위의 단계를 반복합니다. 즉, 런이 스택에 푸시될 때마다 두 런을 병합해야 하는지 확인합니다.

1.4 Steps of Merging Runs

인접한 두 런을 병합하려면 임시 저장 공간이 필요하며 임시 저장 공간의 크기는 두 런 중 작은 런의 크기입니다. Timsort 알고리즘은 먼저 더 작은 런을 이 임시 저장 공간에 복사한 다음 원래 두 런을 저장하는 공간을 사용하여 병합된 런을 저장합니다.

간단한 병합 알고리즘은 간단한 삽입 알고리즘을 사용하여 요소를 왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽으로 차례로 비교한 다음 두 런을 병합합니다. 효율성을 높이기 위해 Timsort는 이진 병합 정렬을 사용합니다. 먼저 이진 검색 알고리즘을 사용하여 삽입 위치를 찾은 다음 삽입합니다.

예를 들어 두 런 A와 B를 병합하고 A가 더 작은 런이라고 가정합니다. A와 B는 각각 이미 정렬되었으므로 이진 검색은 B의 첫 번째 요소를 A에 삽입해야 하는 위치를 찾습니다 (그림 4). 마찬가지로 A의 마지막 요소가 B에 삽입해야 하는 위치를 찾습니다. 찾은 후 이 요소 뒤에 있는 B의 요소는 비교할 필요가 없습니다 (그림 5). 이러한 종류의 검색은 난수에서는 매우 효율적이지 않을 수 있지만 다른 경우에는 효율성이 높습니다.

1.5 Galloping Model

위의 런과 유사한 병합 프로세스를 설명합니다. 자세한 내용은 Wikipedia Galloping Model을 참조하십시오.

2. Performance

2.1 Core Process of Timsort

오름차순 부분의 역추적과 내림차순 부분의 성능 저하를 줄이기 위해 TimSort 알고리즘은 오름차순 및 내림차순 특성에 따라 입력을 분할합니다. 정렬의 입력 단위는 개별 숫자가 아니라 블록 (파티션)입니다. 각 파티션을 런이라고 합니다. 이러한 런 시퀀스의 경우 매번 하나의 런을 꺼내어 규칙에 따라 병합합니다. 각 병합은 두 개의 런을 하나의 런으로 결합합니다. 병합 결과는 스택에 저장됩니다. 모든 런이 소모될 때까지 병합이 계속된 다음 스택에 남아 있는 런은 런이 하나만 남을 때까지 병합됩니다. 이때 이 남아 있는 런이 정렬된 결과입니다.

요약하면 Timsort 알고리즘의 프로세스는 다음과 같습니다.

1. 배열 길이가 특정 값보다 작으면 이진 삽입 정렬 알고리즘을 직접 사용합니다.
2. 각 런을 찾아 스택에 푸시합니다.
3. 규칙에 따라 런을 병합합니다.

2.2 Performance Analysis

정보학 이론에 따르면 평균적인 경우 비교 기반 정렬은 O(n log n)보다 빠를 수 없습니다. Timsort 알고리즘은 실제로 대부분의 데이터에 정렬된 영역이 있다는 사실을 활용하기 때문에 Timsort는 O(n log n)보다 빠릅니다. 난수의 경우 활용할 수 있는 정렬된 영역이 없으며 Timsort의 시간 복잡도는 log(n!)이 됩니다.

Timsort의 시간 복잡도와 다른 비교 기반 정렬 알고리즘을 비교합니다.

공간 복잡도 비교.

설명: JSE 7은 퀵 정렬이 불안정하기 때문에 객체 정렬에 퀵 정렬을 사용하지 않는 반면 Timsort는 안정적입니다.

다음은 JSE7의 Timsort 구현 코드에서 발췌한 것으로 Timsort의 장점을 잘 보여줍니다.

A stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when running on partially sorted arrays, while offering performance comparable to a traditional mergesort when run on random arrays. Like all proper mergesorts, this sort is stable and runs O(n log n) time (worst case). In the worst case, this sort requires temporary storage space for n/2 object references; in the best case, it requires only a small constant amount of space.

일반적으로 Timsort는 안정적인 알고리즘입니다. 정렬할 배열에 이미 정렬된 숫자가 있는 경우 시간 복잡도는 n logn보다 작습니다. 다른 병합 정렬과 마찬가지로 Timesrot는 안정적인 정렬 알고리즘이며 최악의 경우 시간 복잡도는 O(n log n)입니다. 최악의 경우 Timsort 알고리즘은 n/2의 임시 공간이 필요하고 최상의 경우 매우 적은 양의 임시 저장 공간만 필요합니다.

Leapcell: Golang 웹 호스팅을 위한 최고의 서버리스 플랫폼

마지막으로 Golang 프로젝트를 배포하기 위한 최고의 플랫폼인 Leapcell을 추천합니다.

1. 다중 언어 지원

• JavaScript, Python, Go 또는 Rust로 개발합니다.

2. 무제한 프로젝트를 무료로 배포

• 사용량에 대해서만 지불합니다. 요청도, 요금도 없습니다.

3. 최고의 비용 효율성

• 유휴 요금 없이 사용한 만큼 지불합니다.
• 예: $25는 평균 응답 시간 60ms로 694만 건의 요청을 지원합니다.

4. 간소화된 개발자 경험

• 간편한 설정을 위한 직관적인 UI.
• 완전 자동화된 CI/CD 파이프라인 및 GitOps 통합.
• 실행 가능한 통찰력을 위한 실시간 메트릭 및 로깅.

5. 간편한 확장성 및 고성능

• 쉬운 동시성 처리를 위한 자동 확장.
• 운영 오버헤드가 없어 구축에만 집중할 수 있습니다.

문서에서 자세히 알아보세요!

Leapcell Twitter: https://x.com/LeapcellHQ