sortowanie błyskawiczne

Flashsort to algorytm sortowania rozkładu wykazujący liniową złożoność obliczeniową $O (n)$ dla równomiernie rozłożonych zbiorów danych i stosunkowo niewielkie zapotrzebowanie na dodatkową pamięć. Oryginalna praca została opublikowana w 1998 roku przez Karla-Dietricha Neuberta.

Pojęcie

Flashsort to wydajna implementacja sortowania histogramowego w miejscu , która sama w sobie jest rodzajem sortowania kubełkowego . Przypisuje każdy z $n$ elementów wejściowych do jednego z $m$ zasobników , wydajnie przestawia dane wejściowe, aby umieścić zasobniki we właściwej kolejności, a następnie sortuje każdy zasobnik. Oryginalny algorytm sortuje tablicę wejściową $A$ w następujący sposób:

Korzystając z pierwszego przejścia przez dane wejściowe lub wiedzę a priori , znajdź minimalne i maksymalne klucze sortowania.
Podziel liniowo zakres $[A min, A max]$ na $m$ przedziałów.
Wykonaj jedno przejście przez wejście, licząc liczbę elementów $A i$ , które wpadają do każdego kubełka. (Neubert nazywa zasobniki „klasami”, a przypisanie elementów do ich zasobników „klasyfikacją”).
Przekształć liczbę elementów w każdym zasobniku na przedrostek sum , gdzie $L b$ to liczba elementów $A i$ w zasobniku $b$ lub mniejsza. ( $0 L = 0$ i $L m = n$ .)
Zmień kolejność danych wejściowych, aby wszystkie elementy każdego segmentu $b$ były przechowywane w pozycjach $A i$ gdzie $L b -1 < i \leq L b$ .
Posortuj każdy segment za pomocą sortowania przez wstawianie .

Kroki 1–3 i 6 są wspólne dla każdego sortowania kubełkowego i można je ulepszyć za pomocą technik typowych dla sortowania kubełkowego. W szczególności celem jest, aby przedziały były w przybliżeniu równej wielkości ( $n / m$ elementów każdy), przy czym ideałem jest podział na $m$ kwantyli . Podczas gdy podstawowym algorytmem jest sortowanie z interpolacją liniową , jeśli wiadomo, że rozkład danych wejściowych jest niejednorodny, podział nieliniowy będzie bardziej zbliżony do tego ideału. Podobnie, ostateczne sortowanie może wykorzystywać dowolną z wielu technik, w tym rekurencyjne sortowanie flash.

Tym, co wyróżnia sortowanie flash, jest krok 5: wydajny algorytm $O (n)$ w miejscu do zbierania razem elementów każdego segmentu we właściwej kolejności względnej przy użyciu tylko $m$ słów dodatkowej pamięci.

Implementacja wydajna pod względem pamięci

Faza przegrupowania Flashsort przebiega cyklicznie . Elementy zaczynają się jako „niesklasyfikowane”, a następnie są przenoszone do odpowiedniego zasobnika i uznawane za „sklasyfikowane”. Podstawowa procedura polega na wybraniu niesklasyfikowanego elementu, znalezieniu jego właściwego kubełka, zamianie go tam na element niesklasyfikowany (który musi istnieć, ponieważ wcześniej policzyliśmy wielkość każdego kubełka), oznaczeniu go jako sklasyfikowanego, a następnie powtórzeniu z właśnie wymieniony niesklasyfikowany element. W końcu element jest wymieniany ze sobą i cykl się kończy.

Szczegóły są łatwe do zrozumienia dzięki dwóm zmiennym (wielkości słowa) na zasobnik. Sprytna część polega na wyeliminowaniu jednej z tych zmiennych, co pozwala na użycie dwukrotnie większej liczby wiader, a tym samym o połowę mniej czasu spędzonego na końcowym sortowaniu $O (n 2) .$

Aby zrozumieć to z dwoma zmiennymi na zasobnik, załóżmy, że istnieją dwie tablice $m$ dodatkowych słów: $K b$ jest (stałą) górną granicą zasobnika $b$ (i $0 K = 0$ ), podczas gdy $L b$ jest (ruchomym) indeksem do zasobnika $b$ , więc $K b -1 \leq L b \leq K b$ .

Utrzymujemy niezmiennik pętli , że każdy segment jest podzielony przez $L b$ na niesklasyfikowany przedrostek ( $A i$ dla $K b -1 < i \leq L b$ jeszcze nie został przeniesiony do ich docelowych pojemników) i sklasyfikowany sufiks ( $A i$ dla $L b < i \leq K b$ znajdują się we właściwym pojemniku i nie zostaną ponownie przeniesione). Początkowo $L b = K b$ i wszystkie elementy są niesklasyfikowane. W miarę postępu sortowania $Lb są klasyfikowane$ są zmniejszane, aż $i Lb = Kb -1 dla do wszystkich b$ wszystkie $elementy$ właściwego segmentu.

Każda runda rozpoczyna się od znalezienia pierwszego niekompletnie sklasyfikowanego przedziału $c$ (który ma $K c -1 < L c$ ) i pobrania pierwszego niesklasyfikowanego elementu z tego przedziału $A i$ , gdzie $i = K c -1 + 1$ . (Neubert nazywa to „liderem cyklu”.) Skopiuj $A i$ do tymczasowej zmiennej $t$ i powtórz:

Oblicz wiadro $b$ , do którego należy $t$ .
Niech $j = L b$ będzie lokalizacją, w której $t$ będzie przechowywane.
Zamień $t$ na $Aj,$ $Aj,$ tj. przechowuj $t$ w $Aj przesuniętą$ pobierając poprzednią wartość w ten sposób.
Zmniejsz $Lb,$ aby odzwierciedlić fakt, że $Aj jest$ teraz poprawnie sklasyfikowany.
Jeśli $j \neq i$ , uruchom ponownie tę pętlę z nowym $t$ .
Jeśli $j = i$ , ta runda jest zakończona i znajdź nowy pierwszy niesklasyfikowany element $A i$ .
Kiedy nie ma już elementów niesklasyfikowanych, podział na segmenty jest zakończony.

W przypadku implementacji w ten sposób z dwiema zmiennymi na koszyk, wybór punktu początkowego każdej rundy $i$ jest w rzeczywistości arbitralny; każdy niesklasyfikowany element może być użyty jako lider cyklu. Jedynym wymogiem jest sprawne znalezienie liderów cyklu.

Chociaż poprzedni opis wykorzystuje $K$ do znalezienia liderów cyklu, w rzeczywistości można się bez niego obejść, co pozwala na wyeliminowanie całej tablicy $m -słów.$ (Po zakończeniu dystrybucji granice segmentów można znaleźć w $L$ .)

Załóżmy, że sklasyfikowaliśmy wszystkie pierwiastki do $i -1$ i rozważamy $A i$ jako potencjalnego nowego lidera cyklu. Łatwo jest obliczyć jego docelowe wiadro $b$ . Przez niezmiennik pętli jest klasyfikowany, jeśli $L b < i \leq K b$ , i nieklasyfikowany, jeśli $i$ jest poza tym zakresem. Pierwsza nierówność jest łatwa do przetestowania, ale wydaje się, że druga wymaga wartości $K b$ .

Okazuje się, że z hipotezy indukcyjnej , że wszystkie elementy do $i -1$ są sklasyfikowane, wynika, że $i \leq K b$ , więc nie jest konieczne testowanie drugiej nierówności.

Rozważmy wiadro $c , w$ którym znajduje się pozycja $i$ . To znaczy $K.c - 1 < ja \leq K.c._$ Zgodnie z hipotezą indukcyjną wszystkie elementy poniżej $i$ , które obejmują wszystkie przedziały do $K c -1 < i$ , są całkowicie sklasyfikowane. Oznacza to, że żadne elementy należące do tych zasobników nie pozostają w pozostałej części tablicy. Dlatego nie jest możliwe, aby $b < c$ .

Jedynym pozostałym przypadkiem jest $b \geq c$ , co implikuje $K b \geq K c \geq i$ , QED

Uwzględniając to, algorytm dystrybucji flashsort zaczyna się od $L$ , jak opisano powyżej, i $i = 1$ . Następnie wykonaj:

Jeśli $i > n$ , dystrybucja jest zakończona.
Biorąc pod uwagę $A i$ , oblicz wiadro $b$ , do którego należy.
Jeśli i ≤ L _b , to A _i jest niesklasyfikowane. Skopiuj zmienną tymczasową t i:
- Niech $j = L b$ będzie lokalizacją, w której $t$ będzie przechowywane.
- Zamień $t$ na $Aj,$ $Aj,$ tj. przechowuj $t$ w $Aj przesuniętą$ pobierając poprzednią wartość w ten sposób.
- Zmniejsz $Lb,$ aby odzwierciedlić fakt, że $Aj jest$ teraz poprawnie sklasyfikowany.
- Jeśli $j \neq i$ , oblicz wiadro $b$ , do którego należy $t$ i uruchom ponownie tę (wewnętrzną) pętlę z nowym $t$ .
$A i$ jest teraz poprawnie sklasyfikowane. Zwiększ $i$ i zrestartuj (zewnętrzną) pętlę.

Oszczędzając pamięć, Flashsort ma tę wadę, że przelicza wiadro dla wielu już sklasyfikowanych elementów. Jest to już wykonywane dwa razy na element (raz podczas fazy liczenia kubełków i drugi raz podczas przenoszenia każdego elementu), ale poszukiwanie pierwszego niesklasyfikowanego elementu wymaga trzeciego obliczenia dla większości elementów. Może to być kosztowne, jeśli przedziały są przypisywane przy użyciu bardziej złożonego wzoru niż prosta interpolacja liniowa. Wariant zmniejsza liczbę obliczeń z prawie $3 n$ do co najwyżej $2 n + m - 1$ , biorąc ostatni niesklasyfikowany element w niedokończonym wiadrze jako lidera cyklu:

Zachowaj zmienną $c$ identyfikującą pierwszy niekompletnie sklasyfikowany segment. Niech $c = 1$ na początek, a kiedy $c > m$ , rozkład jest kompletny.
Niech $ja = L c$ . Jeśli $i = L c -1$ , zwiększ $c$ i zrestartuj tę pętlę. ( $0 L = 0$ .)
Oblicz wiadro $b$ , do którego należy $A i$ .
Jeśli $b < c$ , to $L c = K c -1$ i skończymy z wiadrem $c$ . Zwiększ $c$ i zrestartuj tę pętlę.
Jeśli $b = c$ , klasyfikacja jest trywialna. Zmniejsz $L c$ i zrestartuj tę pętlę.
Jeśli $b > c$ , to $A i$ jest niesklasyfikowane. Wykonaj tę samą pętlę klasyfikacji, co w poprzednim przypadku, a następnie zrestartuj tę pętlę.

W przypadku większości elementów zasobniki są obliczane tylko dwa razy, z wyjątkiem ostatniego elementu w każdym zasobniku, który jest używany do wykrywania zakończenia kolejnego zasobnika. Niewielką dalszą redukcję można osiągnąć, utrzymując liczbę niesklasyfikowanych elementów i zatrzymując się, gdy osiągnie zero.

Wydajność

Jedynymi dodatkowymi wymaganiami dotyczącymi pamięci są wektor pomocniczy $L$ do przechowywania granic przedziałów i stała liczba innych używanych zmiennych. Ponadto każdy element jest przenoszony (poprzez tymczasowy bufor, czyli dwie operacje przenoszenia) tylko raz. Jednak ta wydajność pamięci ma tę wadę, że dostęp do tablicy jest losowy, więc nie można skorzystać z pamięci podręcznej danych mniejszej niż cała macierz.

Podobnie jak w przypadku wszystkich rodzajów łyżek, wydajność zależy w decydującym stopniu od wyważenia łyżek. W idealnym przypadku zrównoważonego zestawu danych każdy segment będzie mniej więcej tej samej wielkości. Jeśli liczba $m$ przedziałów jest liniowa w rozmiarze wejściowym $n$ , każdy przedział ma stały rozmiar, więc sortowanie pojedynczego przedziału za pomocą algorytmu $O (n 2) , takiego jak sortowanie przez wstawianie, ma złożoność$ $O (1 2) = O (1)$ . Czas działania końcowego sortowania przez wstawianie wynosi zatem $m \cdot O(1) = O (m) = O (n)$ .

Wybór wartości dla $m$ , liczby segmentów, zamienia czas poświęcony na klasyfikację elementów (wysokie $m$ ) i czas spędzony na ostatnim etapie sortowania przez wstawianie (niskie $m$ ). Na przykład, jeśli $m$ jest wybrane proporcjonalnie do $\sqrt n$ , to czas wykonywania końcowego sortowania przez wstawianie wynosi zatem $m \cdot O(\sqrt n 2) = O (n 3/2)$ .

W najgorszych scenariuszach, w których prawie wszystkie elementy znajdują się w kilku segmentach, złożoność algorytmu jest ograniczona wydajnością końcowej metody sortowania segmentów, więc spada do $O (n 2)$ . Odmiany algorytmu poprawiają wydajność w najgorszym przypadku, stosując sortowanie o lepszej wydajności, takie jak sortowanie szybkie lub rekurencyjne sortowanie flash w zasobnikach, które przekraczają określony limit rozmiaru.

Dla $m = 0,1 n$ z równomiernie rozłożonymi losowymi danymi sortowanie błyskawiczne jest szybsze niż sortowanie na stosie dla wszystkich $n$ i szybsze niż sortowanie szybkie dla $n > 80$ . Staje się około dwa razy szybsze niż sortowanie szybkie przy $n = 10000$ . Należy zauważyć, że pomiary te zostały wykonane pod koniec lat 90., kiedy hierarchie pamięci były znacznie mniej zależne od buforowania.

Ze względu na permutację in situ , którą flashsort wykonuje w swoim procesie klasyfikacji, flashsort nie jest stabilny . Jeśli wymagana jest stabilność, możliwe jest użycie drugiej tablicy, aby elementy mogły być klasyfikowane sekwencyjnie. Jednak w tym przypadku algorytm będzie wymagał $O (n)$ dodatkowej pamięci.

Zobacz też

Wyszukiwanie interpolacyjne , wykorzystujące rozkład elementów do wyszukiwania zamiast sortowania

Linki zewnętrzne

Algorytmy sortowania
Teoria	Teoria złożoności obliczeniowej Notacja dużego O Całkowite zamówienie Listy Zastąpienie Stabilność Sortowanie porównawcze Sortowanie adaptacyjne Sieć sortująca Sortowanie liczb całkowitych Sortowanie X + Y Model transdychotomiczny Sortowanie kwantowe
Rodzaje wymiany	Sortowanie bąbelkowe Rodzaj shakera do koktajli Sortowanie nieparzyste-parzyste Sortowanie grzebieniowe Gatunek gnoma Sortowanie proporcjonalne Szybkie sortowanie Powolne sortowanie Stooge sort Bogosort
Sortowanie przez wybór	Sortowanie przez wybór sortowanie Sortowanie gładkie Sortowanie drzewa kartezjańskiego Sortowanie turniejowe Sortowanie cykliczne Sortowanie według słabej sterty
Sortowanie przez wstawianie	Sortowanie przez wstawianie sortowanie skorup sortowanie Sortowanie drzew Sortowanie w bibliotece Sortowanie cierpliwości
Scal sortowania	Sortuj przez scalanie Kaskadowe sortowanie przez scalanie Oscylacyjne sortowanie przez scalanie Sortowanie przez scalanie polifazowe
Sortowanie dystrybucji	Rodzaj amerykańskiej flagi Sortowanie koralików Sortowanie kubełkowe sortowanie seryjne Sortowanie liczące Sortowanie interpolacyjne Rodzaj przegródek Sortowanie mapy zbliżeniowej Sortowanie według radixa sortowanie błyskawiczne
Sortowania równoległe	Sortownik bitoniczny Batcher nieparzyste-parzyste scalanie Sieć sortowania parami sortowanie próbek
Rodzaje hybrydowe	Sortowanie przez scalanie bloków Sortowanie według Kirkpatricka-Reischa Timsort Introsort sortowanie Sortowanie przez wstawianie
Inny	Sortowanie topologiczne Porządek przedtopologiczny Sortowanie naleśników Rodzaj spaghetti