Introsort

Introsort

Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku	O( n log n )
Średnia wydajność	O( n log n )

Introsort lub sortowanie introspektywne to hybrydowy algorytm sortowania , który zapewnia zarówno szybką średnią wydajność, jak i (asymptotycznie) optymalną wydajność w najgorszym przypadku. Zaczyna się od sortowania szybkiego , przełącza się na sortowanie na stosie , gdy głębokość rekurencji przekroczy poziom oparty na ( logarytmie ) liczby sortowanych elementów i przełącza się na sortowanie przez wstawianie gdy liczba elementów jest poniżej pewnego progu. Łączy to dobre części trzech algorytmów, z praktyczną wydajnością porównywalną z szybkim sortowaniem na typowych zestawach danych i najgorszym przypadkiem O ( n log n ) ze względu na sortowanie sterty. Ponieważ trzy algorytmy, których używa, to sortowanie porównawcze , jest to również sortowanie porównawcze.

Introsort został wynaleziony przez Davida Mussera w Musser (1997) , w którym wprowadził również introselect , hybrydowy algorytm selekcji oparty na quickselect (wariant szybkiego sortowania), który powraca do mediany median , a tym samym zapewnia złożoność liniową najgorszego przypadku, która jest optymalny. Oba algorytmy zostały wprowadzone w celu zapewnienia ogólnych algorytmów dla standardowej biblioteki C++ który charakteryzował się zarówno wysoką średnią wydajnością, jak i optymalną wydajnością w najgorszym przypadku, umożliwiając w ten sposób zaostrzenie wymagań dotyczących wydajności. Introsort jest na swoim miejscu i nie jest stabilny .

Pseudo kod

Jeśli dostępna jest implementacja sortowania sterty i funkcje partycjonowania typu omówionego w artykule o szybkim sortowaniu , introsort można zwięźle opisać jako

 procedura  sort(A : tablica): maxgłębokość ← ⌊log  2  (długość(A))⌋ × 2 introsort(A, maxgłębokość)  procedura  introsort(A, maxgłębokość): n ← długość(A)  jeśli  n < 16: wstawianiesort(A )  else if  maxdepth = 0: heapsort(A)  else  : p ← partition(A)  // zakładamy, że ta funkcja dokonuje wyboru przestawnego, p jest końcową pozycją przestawnego introsort  (A[1:p-1], maxgłębokość - 1 ) introsort(A[p+1:n], maxgłębokość - 1) 

Współczynnik 2 w maksymalnej głębokości jest dowolny; można go dostroić pod kątem praktycznej wydajności. A [ i : j ] oznacza wycinek tablicy elementów od i do j , w tym zarówno A [ i ] , jak i A [ j ] . Zakłada się, że indeksy zaczynają się od 1 (pierwszy element tablicy A to A[1] ).

Analiza

W sortowaniu szybkim jedną z krytycznych operacji jest wybranie osi obrotu: elementu, wokół którego podzielona jest lista. Najprostszym algorytmem wyboru przestawnego jest wzięcie pierwszego lub ostatniego elementu listy jako przestawnego, co powoduje złe zachowanie w przypadku posortowanych lub prawie posortowanych danych wejściowych. Niklausa Wirtha wykorzystuje środkowy element, aby zapobiec tym zdarzeniom, degenerując się do O ( n ² ) dla wymyślonych sekwencji. Algorytm wyboru przestawnego mediana z 3 bierze medianę pierwszego, środkowego i ostatniego elementu listy; jednakże, mimo że działa to dobrze na wielu rzeczywistych danych wejściowych, nadal możliwe jest wymyślenie zabójców z medianą 3 , która spowoduje dramatyczne spowolnienie szybkiego sortowania w oparciu o tę technikę wyboru przestawnego.

Musser poinformował, że w sekwencji 100 000 elementów z medianą 3 zabójców czas działania introsortu wynosił 1/200 czasu szybkiego sortowania z medianą 3. Musser rozważał również wpływ na pamięci podręczne opóźnionego sortowania małych Sedgewicka , w którym małe zakresy są sortowane na końcu w jednym przebiegu sortowania przez wstawianie . Poinformował, że może podwoić liczbę chybień w pamięci podręcznej, ale jego wydajność w przypadku kolejek dwustronnych była znacznie lepsza i powinna zostać zachowana dla bibliotek szablonów, po części dlatego, że w innych przypadkach zysk z natychmiastowego sortowania nie był duży.

Implementacje

Introsort lub inny wariant jest używany w wielu standardowych funkcjach sortowania w bibliotece, w tym w niektórych implementacjach sortowania w C++ .

Implementacja standardowej biblioteki szablonów SGI C++ z czerwca 2000 r . Stl_algo.h sortowania niestabilnego wykorzystuje podejście Musser introsort z głębokością rekurencji do przełączenia na sortowanie sterty przekazaną jako parametr, wybór przestawny mediany z 3 i przepustka sortowania końcowego wstawiania Knutha dla mniejszych partycji niż 16.

Biblioteka GNU Standard C++ jest podobna: używa introsortu o maksymalnej głębokości 2×log ₂ n , po którym następuje sortowanie przez wstawianie na partycjach mniejszych niż 16.

LLVM libc++ wykorzystuje również introsort z maksymalną głębokością 2×log ₂ n , jednak limit rozmiaru dla sortowania przez wstawianie jest różny dla różnych typów danych (30, jeśli zamiany są trywialne, 6 w przeciwnym razie). Ponadto tablice o rozmiarach do 5 są obsługiwane oddzielnie. Kutenin (2022) zawiera przegląd niektórych zmian wprowadzonych przez LLVM, z naciskiem na poprawkę 2022 dotyczącą kwadratowości.

Biblioteka klas Microsoft .NET Framework , począwszy od wersji 4.5 (2012), używa introsort zamiast prostego sortowania szybkiego.

Go używa introsort z niewielkimi modyfikacjami: w przypadku wycinków zawierających 12 lub mniej elementów używa sortowania Shellsort zamiast sortowania przez wstawianie i bardziej zaawansowanej mediany trzech median z trzech selekcji przestawnej do szybkiego sortowania.

Java , począwszy od wersji 14 (2020), używa hybrydowego algorytmu sortowania, który wykorzystuje sortowanie przez scalanie dla tablic o wysokiej strukturze (tablice składające się z niewielkiej liczby posortowanych podtablic) i introsort w inny sposób do sortowania tablic int, longs, float i doubles .

Warianty

sortowanie pdq

Quicksort pokonujący wzorce (pdqsort) to odmiana introsortu zawierająca następujące ulepszenia:

• Mediana z trzech obrotowych,
• Technika partycjonowania „BlockQuicksort” w celu złagodzenia kar za błędne prognozy gałęzi,
• Liniowa wydajność czasowa dla określonych wzorców wejściowych ( sortowanie adaptacyjne ),
• Użyj tasowania elementów w złych przypadkach, zanim spróbujesz wolniejszego sortowania.

pdqsort jest używany przez Rust , GAP i bibliotekę C++ Boost .

Ogólny

• Musser, David R. (1997). „Introspektywne algorytmy sortowania i selekcji” . Oprogramowanie: praktyka i doświadczenie . 27 (8): 983–993. doi : 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# .
•   Niklausa Wirtha. Algorytmy i struktury danych . Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1 .