Timsort
Főnév
Timsort (tsz. Timsorts)
Timsort
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.
Fő ötlet
- Run-ok keresése:
- Az algoritmus az adathalmazban lévő már rendezett részhalmazokat (ún. run-okat) azonosítja.
- A run lehet növekvő vagy csökkenő sorrendű. Ha csökkenő, akkor először megfordítja.
- Run-ok rendezése:
- A beillesztéses rendezést alkalmazza kis méretű run-okra, mivel az gyors és hatékony kis halmazoknál.
- Run-ok egyesítése:
- Az összefésülő rendezés segítségével egyesíti a run-okat, figyelve az optimális memóriakezelésre és stabilitásra.
Algoritmus működése
1. Run-ok azonosítása
- A bemeneti adathalmazt kisebb, már rendezett részhalmazokra (run-okra) bontja.
- Egy run hossza legalább (min_run), amelyet az adathalmaz méretétől függően határoz meg: [ min_run = 32. ]
2. Beillesztéses rendezés
- A kisebb run-okat rendezetté teszi beillesztéses rendezéssel, amely kis méretű halmazok esetén gyors.
3. Run-ok egyesítése
- A már rendezett run-okat az összefésülő rendezés segítségével egyesíti, miközben figyeli az optimális összeolvasztási stratégiát.
Optimalizációk
- Run-ok kihasználása:
- Az algoritmus kihasználja, hogy sok adathalmazban már eleve vannak részben rendezett részhalmazok (run-ok).
- Adaptivitás:
- A Timsort adaptív, ami azt jelenti, hogy részben rendezett adatok esetén jelentősen gyorsabb, mint más általános rendezési algoritmusok.
- Stabilitás:
- Az algoritmus stabil, azaz nem változtatja meg az egyenlő elemek sorrendjét.
Pszeudokód
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.
Python implementáció
MIN_RUN = 32
def insertion_sort(array, left, right):
for i in range(left + 1, right + 1):
key = array[i]
j = i - 1
while j >= left and array[j] > key:
array[j + 1] = array[j]
j -= 1
array[j + 1] = key
def merge(array, left, mid, right):
left_part = array[left:mid + 1]
right_part = array[mid + 1:right + 1]
i = j = 0
k = left
while i < len(left_part) and j < len(right_part):
if left_part[i] <= right_part[j]:
array[k] = left_part[i]
i += 1
else:
array[k] = right_part[j]
j += 1
k += 1
while i < len(left_part):
array[k] = left_part[i]
i += 1
k += 1
while j < len(right_part):
array[k] = right_part[j]
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 = [5, 2, 9, 1, 5, 6, 7, 3, 4, 8]
timsort(array)
print("Rendezett tömb:", array)
Kimenet:
Rendezett tömb: [1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
C++ implementáció
#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[i];
int j = i - 1;
while (j >= left && array[j] > key) {
array[j + 1] = array[j];
--j;
}
array[j + 1] = 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[i] <= right_part[j]) {
array[k++] = left_part[i++];
} else {
array[k++] = right_part[j++];
}
}
while (i < left_part.size()) {
array[k++] = left_part[i++];
}
while (j < right_part.size()) {
array[k++] = right_part[j++];
}
}
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
Előnyök
- Adaptivitás:
- Rendkívül hatékony részben rendezett adatokon.
- Stabilitás:
- Az algoritmus megőrzi az egyenlő elemek sorrendjét.
- Hatékony memóriahasználat:
- Az összefésülő rendezés optimalizációkat alkalmaz a memóriahasználat minimalizálására.
Hátrányok
- Bonyolultság:
- Az algoritmus implementációja összetettebb, mint az egyszerűbb rendezési algoritmusoké.
- Kis halmazok esetén:
- Nem mindig gyorsabb, mint más egyszerűbb algoritmusok, ha az adathalmaz kicsi.
Alkalmazások
- Python beépített rendező algoritmusa.
- Java Arrays.sort() és Collections.sort().
- Nagy adathalmazok rendezése, ahol a rendezési stabilitás fontos.
Összegzés
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.