Tim 정렬
Tim 정렬은 안정적인 하이브리드 정렬 알고리즘입니다. 삽입 정렬 및 병합 정렬에서 파생 된 하이브리드 알고리즘입니다. 먼저 삽입 정렬을 사용하여 하위 배열합니다. 이러한 작은 정렬 하위 배열을 자연 실행이라고합니다. 그런 다음 이러한 실행은 병합 정렬을 사용하여 병합 된 하위 배열로 최종 정렬 된 배열을 생성합니다. 실제 데이터에서 알고리즘의 최적 성능을 염두에두고 설계되었습니다. 삽입 정렬이 작은 하위 배열에서 정말 잘 수행된다는 사실을 사용합니다. Java의Array.sort()와 Python의sorted()및sort()에서 사용하는 표준 정렬 알고리즘입니다.
Tim 정렬 알고리즘
n 요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정 해 보겠습니다. 런의 크기는 32로 간주합니다. 숫자가 2의 거듭 제곱 일 때 병합이 더 효과적이기 때문에 2의 모든 거듭 제곱이 될 수 있습니다.
TimSort()
-
배열을
n / 32실행으로 나눕니다. -
삽입 정렬을 사용하여 개별 실행을 정렬합니다.
-
병합 정렬의
merge기능을 사용하여 정렬 된 런을 하나씩 병합합니다.
Merge()
-
정렬 된 출력을 저장하기 위해 보조 배열
output을 초기화합니다. -
3 개의 포인터
i,j&k를 초기화합니다.i는 첫 번째 하위 배열beg의 시작을 가리 킵니다.
j는 두 번째 하위 배열mid + 1의 시작을 가리 킵니다.
beg로 초기화 된k는 정렬 된 배열output의 현재 인덱스를 유지합니다. -
arr[beg, ...., mid]또는arr[mid + 1, ...., end]하위 배열의 끝에 도달 할 때까지 요소 중에서 더 작은 값을 선택합니다. 인덱스i&j에서output에 삽입합니다. -
나머지 요소를 선택하고 배열 중 하나가 소진되면
출력에 삽입합니다. -
output을arr[beg, ..., end]에 복사합니다.
Tim 정렬 예
배열이(3, 5, 2, 8, 1, 7, 6, 4)라고 가정합니다. Tim 정렬 알고리즘을 사용하여 정렬합니다. 그림을 간단하게 유지하기 위해 런의 크기를 4로 간주하겠습니다.
배열을 (3, 5, 2, 8)및 (1, 7, 6, 4)의 두 하위 배열로 나눕니다.
첫 번째 하위 배열 :(3, 5, 2, 8)
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (삼) | (5, 2, 8) | (3,5,2,8) |
- 첫 번째 반복
키 :A[1]= 5
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (3, 5) | (2, 8) | (3, 5, 2, 8) |
- 두 번째 반복
키 :A[2]= 4
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (2, 3, 5) | (8) | (2, 3, 5, 8) |
- 세 번째 반복
키 :A[3]= 2
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (2, 3, 5, 8) | () | (2, 3, 5, 8) |
두 번째 부분 배열 :(1,7,6,4)
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (1) | (7, 6, 4) | (1, 7, 6, 4) |
- 첫 번째 반복
키 :A[1]= 7
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (1, 7) | (6, 4) | (1, 7, 6, 4) |
- 두 번째 반복
키 :A[2]= 6
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (1, 6, 7) | (4) | (1, 6, 7, 4) |
- 세 번째 반복
키 :A[3]= 4
| 정렬 된 하위 배열 | 정렬되지 않은 하위 배열 | 정렬 |
|---|---|---|
| (1, 4, 6, 7) | () | (1, 4, 6, 7) |
두 개의 정렬 된 부분 배열을 병합하여 최종 부분 배열을(1, 2, 3, 4, 5, 6, 7, 8)로 얻습니다.
Tim 정렬 알고리즘 구현
#include <bits/stdc++.h>
using namespace std;
const int RUN = 32;
void insertionSort(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
void merge(int arr[], int beg, int mid, int end) {
int output[end - beg + 1];
int i = beg, j = mid + 1, k = 0;
// add smaller of both elements to the output
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
output[k] = arr[i];
k += 1;
i += 1;
} else {
output[k] = arr[j];
k += 1;
j += 1;
}
}
// remaining elements from first array
while (i <= mid) {
output[k] = arr[i];
k += 1;
i += 1;
}
// remaining elements from the second array
while (j <= end) {
output[k] = arr[j];
k += 1;
j += 1;
}
// copy output to the original array
for (i = beg; i <= end; i += 1) {
arr[i] = output[i - beg];
}
}
void timSort(int arr[], int n) {
for (int i = 0; i < n; i += RUN)
insertionSort(arr, i, min((i + 31), (n - 1)));
for (int size = RUN; size < n; size = 2 * size) {
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size - 1;
int right = min((left + 2 * size - 1), (n - 1));
merge(arr, left, mid, right);
}
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
timSort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Tim 정렬 알고리즘 복잡성
시간 복잡성
- 평균 사례
알고리즘은n 요소의 배열을 정렬하기 위해O(nlogn)비교를 필요로합니다. 따라서 시간 복잡도는 [Big Theta] :O(nlogn)의 순서입니다.
- 최악의 경우
최악의 경우nlogn 비교가 필요합니다. 최악의 시간 복잡성은 [Big O] : O(nlogn)입니다. 평균 케이스 시간 복잡성과 동일합니다.
- 베스트 케이스
최상의 경우는 어레이가 이미 정렬되어 있고 교체가 필요하지 않은 경우에 발생합니다. 최적의 시간 복잡도는 [Big Omega] :O(n)입니다.
공간 복잡성
이 알고리즘의 공간 복잡도는 O(n)입니다. 병합 정렬 알고리즘에 O(n)의 추가 보조 공간이 필요하기 때문입니다.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn