Timsort (tsz. Timsorts)
A Timsort egy hibrid rendezési algoritmus, amelyet Tim Peters fejlesztett ki 2002-ben a Python programozási nyelv számára. Az algoritmus a beillesztéses rendezés (Insertion Sort) és az összefésülő rendezés (Merge Sort) kombinációján alapul. Úgy tervezték, hogy hatékonyan kezelje a való életben előforduló adatokat, különösen azokat, amelyek részben rendezettek.
Timsort(array):
1. Ossza fel az array-t run-okra:
- Keresd meg a meglévő rendezett részhalmazokat.
- Ha egy részhalmaz rövidebb, mint min_run, töltsd ki beillesztéses rendezéssel.
2. Rendezd a run-okat:
- A kis run-okat beillesztéses rendezéssel rendezd.
3. Egyesítsd a run-okat:
- Használj összeolvasztási szabályokat, hogy a run-okat összefésüld.
- Figyelj a stabilitásra és a memóriahasználatra.
MIN_RUN = 32
def insertion_sort(array, left, right):
for i in range(left + 1, right + 1):
key = array
j = i - 1
while j >= left and array > key:
array = array
j -= 1
array = key
def merge(array, left, mid, right):
left_part = array
right_part = array
i = j = 0
k = left
while i < len(left_part) and j < len(right_part):
if left_part <= right_part:
array = left_part
i += 1
else:
array = right_part
j += 1
k += 1
while i < len(left_part):
array = left_part
i += 1
k += 1
while j < len(right_part):
array = right_part
j += 1
k += 1
def timsort(array):
n = len(array)
for start in range(0, n, MIN_RUN):
end = min(start + MIN_RUN - 1, n - 1)
insertion_sort(array, start, end)
size = MIN_RUN
while size < n:
for left in range(0, n, 2 * size):
mid = min(left + size - 1, n - 1)
right = min(left + 2 * size - 1, n - 1)
if mid < right:
merge(array, left, mid, right)
size *= 2
# Példa használat
array =
timsort(array)
print("Rendezett tömb:", array)
Kimenet:
Rendezett tömb:
#include <iostream>
#include <vector>
#include <algorithm>
const int MIN_RUN = 32;
void insertion_sort(std::vector<int>& array, int left, int right) {
for (int i = left + 1; i <= right; ++i) {
int key = array;
int j = i - 1;
while (j >= left && array > key) {
array = array;
--j;
}
array = key;
}
}
void merge(std::vector<int>& array, int left, int mid, int right) {
std::vector<int> left_part(array.begin() + left, array.begin() + mid + 1);
std::vector<int> right_part(array.begin() + mid + 1, array.begin() + right + 1);
int i = 0, j = 0, k = left;
while (i < left_part.size() && j < right_part.size()) {
if (left_part <= right_part) {
array = left_part;
} else {
array = right_part;
}
}
while (i < left_part.size()) {
array = left_part;
}
while (j < right_part.size()) {
array = right_part;
}
}
void timsort(std::vector<int>& array) {
int n = array.size();
for (int start = 0; start < n; start += MIN_RUN) {
int end = std::min(start + MIN_RUN - 1, n - 1);
insertion_sort(array, start, end);
}
for (int size = MIN_RUN; size < n; size *= 2) {
for (int left = 0; left < n; left += 2 * size) {
int mid = std::min(left + size - 1, n - 1);
int right = std::min(left + 2 * size - 1, n - 1);
if (mid < right) {
merge(array, left, mid, right);
}
}
}
}
int main() {
std::vector<int> array = {5, 2, 9, 1, 5, 6, 7, 3, 4, 8};
timsort(array);
std::cout << "Rendezett tömb: ";
for (int num : array) {
std::cout << num << " ";
}
std::cout << std::endl;
return 0;
}
Kimenet:
Rendezett tömb: 1 2 3 4 5 5 6 7 8 9
A Timsort egy hatékony, adaptív rendezési algoritmus, amely különösen jól működik részben rendezett adatokkal. A stabilitása és adaptív természete miatt az egyik leggyakrabban használt rendezési algoritmus a modern programozási nyelvekben.