Sortuj Shell - Shellsort

Powłoka

Shellsort z przerwami 23, 10, 4, 1 w akcji
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku	O( n 2 ) (najgorszy znany najgorszy ciąg przerw) O( n log 2 n ) (najlepiej znany najgorszy ciąg przerw)
Wydajność w najlepszym przypadku	O( n log n ) (większość ciągów przerw) O( n log 2 n ) (najlepiej znany ciąg przerw w najgorszym przypadku)
Średnia wydajność	zależy od sekwencji przerw
Najgorsza złożoność przestrzeni	О( n ) ogółem, O(1) pomocniczy

Zamiana par elementów w kolejnych krokach Shellsort z przerwami 5, 3, 1

Shellsort , znany również jako Shell sort lub Shell's method , jest sortowaniem porównującym w miejscu . Może to być postrzegane jako albo uogólnienia sortując wymiany ( pęcherzyka rodzaju ) lub sortowanie według wkładania ( wkładania rodzaju ). Metoda zaczyna się od sortowania par elementów daleko od siebie, a następnie stopniowego zmniejszania odstępu między porównywanymi elementami. Rozpoczynając od oddalonych od siebie elementów, może przesunąć na miejsce niektóre nierówne elementy szybciej niż zwykła wymiana najbliższego sąsiada. Donald Shell opublikował pierwszą wersję tego rodzaju w 1959. Czas działania Shellsort jest silnie zależny od używanej sekwencji przerw. Dla wielu praktycznych wariantów ustalenie ich złożoności czasowej pozostaje otwartym problemem .

Opis

Shellsort to optymalizacja sortowania przez wstawianie, która umożliwia wymianę elementów, które są daleko od siebie. Pomysł polega na ułożeniu listy elementów w taki sposób, aby począwszy od dowolnego miejsca, pobranie każdego h elementu dawało posortowaną listę. Mówi się, że taka lista jest posortowana h . Może być również traktowane jako h przeplatane listami, indywidualnie sortowane. Rozpoczęcie od dużych wartości h umożliwia elementom przemieszczanie się na duże odległości w oryginalnej liście, szybko redukując duże ilości nieporządku i pozostawiając mniej pracy na wykonanie mniejszych kroków sortowania h . Jeśli lista jest następnie posortowana według k dla jakiejś mniejszej liczby całkowitej k , to lista pozostaje posortowana według h . Podążając za tym pomysłem dla malejącej sekwencji wartości h kończących się na 1, gwarantujemy pozostawienie na końcu posortowanej listy.

W uproszczeniu oznacza to, że jeśli mamy tablicę 1024 liczb, nasza pierwsza przerwa ( h ) może wynosić 512. Następnie przeglądamy listę porównując każdy element z pierwszej połowy z elementem w drugiej połowie. Nasza druga przerwa ( k ) wynosi 256, co powoduje rozbicie tablicy na cztery sekcje (zaczynając od 0,256,512,768) i upewniamy się, że pierwsze elementy w każdej sekcji są posortowane względem siebie, a następnie drugi element w każdej sekcji i tak dalej . W praktyce sekwencja przerw może być dowolna, ale ostatnią przerwą jest zawsze 1, aby zakończyć sortowanie (efektywnie kończąc zwykłym sortowaniem przez wstawianie).

Przykładowy przebieg Shellsort z przerwami 5, 3 i 1 pokazano poniżej.

Pierwszy przebieg, 5-sorting, wykonuje sortowanie przez wstawianie na pięciu oddzielnych podtablicach ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( ₅ , ₁₀ ). Na przykład zmienia podtablicę ( a ₁ , a ₆ , a ₁₁ ) z (62, 17, 25) na (17, 25, 62). Kolejny przebieg, 3-sorting, wykonuje sortowanie przez wstawianie na trzech podtablicach ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , ₉ , ₁₂ ). Ostatni przebieg, 1-sortowanie, jest zwykłym sortowaniem całej tablicy przez wstawianie ( a ₁ ,..., a ₁₂ ).

Jak ilustruje przykład, podtablice, na których operuje Shellsort, są początkowo krótkie; później są dłuższe, ale prawie uporządkowane. W obu przypadkach sortowanie przez wstawianie działa sprawnie.

Shellsort nie jest stabilny : może zmienić względną kolejność elementów o równych wartościach. Jest to adaptacyjny algorytm sortowania, który działa szybciej, gdy dane wejściowe są częściowo posortowane.

Pseudo kod

Używając sekwencji luk Marcina Ciury, z wewnętrznym sortowaniem przez wstawianie.

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]  // Ciura gap sequence

# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

Sekwencje przerw

Trudne jest podjęcie decyzji, której sekwencji odstępów użyć. Każda sekwencja przerw zawierająca 1 daje poprawne sortowanie (ponieważ ostatnie przejście jest zwykłym sortowaniem przez wstawianie); jednak właściwości tak otrzymanych wersji Shellsort mogą być bardzo różne. Zbyt mało odstępów spowalnia przejazdy, a zbyt wiele odstępów powoduje wzrost.

Poniższa tabela porównuje większość proponowanych sekwencji przerw opublikowanych do tej pory. Niektóre z nich mają malejące elementy, które zależą od rozmiaru posortowanej tablicy ( N ). Inni są rosnącymi ciągami nieskończonymi, których elementy mniejsze niż N powinny być używane w odwrotnej kolejności.

OEIS	Termin ogólny ( k ≥ 1)	Szczeliny betonowe	Złożoność czasowa w najgorszym przypadku	Autor i rok publikacji
	${\ Displaystyle \ lewo \ l podłoga {\ Frac {N} {2 ^ {k}}} \ prawo \ r podłoga}$	${\displaystyle \lewo\lpodłoga {\frac {N}{2}}\prawo\rpodłoga,\lewo\lpodłoga {\frac {N}{4}}\prawo\rpodłoga,\ldots,1}$	${\ Displaystyle \ Theta \ lewo (N ^ {2} \ prawo)}$[np. gdy N = 2 p ]	Powłoka , 1959
	${\ Displaystyle 2 \ lewo \ l piętro {\ Frac {N} {2 ^ {k + 1}}} \ prawo \ r piętro + 1}$	${\displaystyle 2\lewo\lpodłoga {\frac {N}{4}}\prawo\rpiętro +1,\ldots,3,1}$	${\ Displaystyle \ Theta \ lewo (N ^ {\ Frac {3} {2}} \ po prawej)}$	Frank i Łazarz, 1960
A000225	${\ Displaystyle 2 ^ {k} -1}$	${\displaystyle 1,3,7,15,31,63,\ldots}$	${\ Displaystyle \ Theta \ lewo (N ^ {\ Frac {3} {2}} \ po prawej)}$	Hibbard , 1963
A083318	${\ Displaystyle 2 ^ {k} + 1}$, poprzedzony 1	${\ Displaystyle 1,3,5,9,17,33,65,\ldots}$	${\ Displaystyle \ Theta \ lewo (N ^ {\ Frac {3} {2}} \ po prawej)}$	Papernov i Stasevich, 1965
A003586	Kolejne liczby postaci ( liczby 3-gładkie ) ${\ Displaystyle 2 ^ {p} 3 ^ {q}}$	${\ Displaystyle 1,2,3,4,6,8,9,12,\ldots}$	${\ Displaystyle \ Theta \ lewo (N \ log ^ {2} N \ po prawej)}$	Pratt , 1971
A003462	${\ Displaystyle {\ Frac {3 ^ {k}-1} {2}}}$, nie większy niż ${\displaystyle \lewo\lceil {\frac {N}{3}}\prawo\rceil}$	${\ Displaystyle 1,4,13,40,121,\ldots}$	${\ Displaystyle \ Theta \ lewo (N ^ {\ Frac {3} {2}} \ po prawej)}$	Knuth , 1973, na podstawie Pratta , 1971
A036569	${\ Displaystyle {\ zacząć {wyrównany} i \ prod \ limity _ {ja} a_ {q} {\ hbox {gdzie}} \ \ a_ {0} = {} i 3 \ \ a_ {q} = {} i \min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq q<r\mid q\neq {\frac {1}{ 2}}\left(r^{2}+r\right)-k\right\}\\r={}&\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\ rfloor \end{aligned}}}$	${\displaystyle 1,3,7,21,48,112,\ldots}$	${\ Displaystyle O \ lewo (N ^ {1 + {\ sqrt {\ Frac {8 \ ln \ lewo (5/2 \ po prawej))} {\ ln (N)}}}} \ po prawej)}$	Incerpi i Sedgewick , 1985, Knuth
A036562	${\ Displaystyle 4 ^ {k} + 3 \ cdot 2 ^ {k-1} + 1}$, poprzedzony 1	${\ Displaystyle 1,8,23,77,281,\ldots}$	${\ Displaystyle O \ lewo (N ^ {\ Frac {4} {3}} \ po prawej)}$	Sedgewick, 1982
A033622	${\ Displaystyle {\ zacząć {przypadki} 9 \ lewo (2 ^ {k} -2 ^ {\ Frac {k} {2}} \ prawej) + 1 i k {\ tekst {nawet}} \ \ 8 \ cdot 2 ^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ nieparzysty}}\end{przypadki}}}$	${\ Displaystyle 1,5,19,41,109 \ldots}$	${\ Displaystyle O \ lewo (N ^ {\ Frac {4} {3}} \ po prawej)}$	Sedgewick, 1986
	${\ Displaystyle h_ {k} = \ max \ lewo \ {\ lewo \ l piętro {\ Frac {5h_ {k-1}-1} {11}} \ prawo \ r piętro, 1 \ prawo \}, h_ {0} =N}$	${\displaystyle \lewo\lpodłoga {\frac {5N-1}{11}}\prawa\rpodłoga,\lewo\lpodłoga {\frac {5}{11}}\lewo\lpodłoga {\frac {5N-1} {11}}\right\rfloor -1\right\rfloor ,\ldots ,1}$	Nieznany	Gonnet i Baeza-Yates , 1991
A108870	${\ Displaystyle \ lewo \ lceil {\ Frac {1} {5}} \ lewo (9 \ cdot \ lewo ({\ Frac {9} {4}} \ po prawej) ^ {K-1} -4 \ po prawej) \prawo\rceil }$	${\ Displaystyle 1,4,9,20,46,103,\ldots}$	Nieznany	Tokuda, 1992
A102549	Nieznane (pochodzące eksperymentalnie)	${\ Displaystyle 1,4,10,23,57,132,301,701}$	Nieznany	Ciura, 2001

Gdy binarna reprezentacja N zawiera wiele kolejnych zer, sortowanie Shell przy użyciu oryginalnej sekwencji odstępów powłoki wykonuje porównania Θ ( N ² ) w najgorszym przypadku. Na przykład ten przypadek występuje dla N równego potędze dwójki, gdy elementy większe i mniejsze od mediany zajmują odpowiednio pozycje parzyste i nieparzyste, ponieważ są porównywane tylko w ostatnim przebiegu.

Chociaż ma wyższą złożoność niż O ( N  log  N ), która jest optymalna dla sortowania porównawczego, wersja Pratta nadaje się do sieci sortujących i ma taką samą asymptotyczną złożoność bramki jak sorter bitonic Batchera .

Gonnet i Baeza-Yates zaobserwowali, że Shellsort dokonuje średnio najmniej porównań, gdy stosunki kolejnych przerw są w przybliżeniu równe 2,2. Dlatego ich ciąg o przeliczeniu 2,2 i ciąg Tokudy o przeliczeniu 2,25 okazują się skuteczne. Nie wiadomo jednak, dlaczego tak się dzieje. Sedgewick zaleca stosowanie przerw, które mają niskie największe wspólne dzielniki lub są parami względnie pierwsze .

Jeśli chodzi o średnią liczbę porównań, sekwencja Ciury ma najbardziej znaną wydajność; odstępy od 701 nie zostały określone, ale sekwencja może być dalej rozszerzana zgodnie z formułą rekurencyjną . ${\ Displaystyle h_ {k} = \ l piętro 2,25 h_ {k-1} \ r piętro}$

Do praktycznych zastosowań można polecić ciąg Tokudy, określony prostym wzorem , gdzie , . ${\ Displaystyle h_ {k} = \ lceil h '_ {k} \ rceil}$${\ Displaystyle h'_ {k} = 2,25h'_ {k-1} + 1}$${\displaystyle h'_{1}=1}$

Jeśli maksymalny rozmiar danych wejściowych jest mały, co może się zdarzyć, gdy Shellsort jest używany na małych podtablicach przez inny rekurencyjny algorytm sortowania, taki jak quicksort lub merge sort , wówczas możliwe jest zestawienie optymalnej sekwencji dla każdego rozmiaru wejściowego.

Złożoność obliczeniowa

Posiada następującą właściwość: po h ₂ -sorting dowolnego H ₁ -sorted tablicy, Tablica pozostaje h ₁ -sorted. Każda tablica h ₁ -sortowana i h ₂ -sortowana jest również sortowana ( a ₁ h ₁ + a ₂ h ₂ ) dla dowolnych nieujemnych liczb całkowitych a ₁ i a ₂ . Najgorszy przypadek złożoności Shellsort jest zatem związany z problemem Frobeniusa : dla danych liczb całkowitych h ₁ ,..., h _n przy gcd = 1, liczba Frobeniusa g ( h ₁ ,..., h _n ) jest największa całkowita, która nie może być reprezentowane na ₁ godzinę ₁ + ... + _n h, _n z nieujemną liczbę całkowitą o ₁ , ..., a _n . Używając znanych wzorów na liczby Frobeniusa, możemy określić najgorszy przypadek złożoności Shellsort dla kilku klas sekwencji przerw. Sprawdzone wyniki przedstawiono w powyższej tabeli.

W odniesieniu do średniej liczby operacji żaden ze sprawdzonych wyników nie dotyczy praktycznej sekwencji przerw. Dla przerw, które są potęgami dwójki, Espelid obliczył tę średnią jako . Knuth określił średnią złożoność sortowania N- elementowej tablicy z dwiema przerwami ( h , 1) jako . Wynika z tego, że dwuprzebiegowe sortowanie Shell z h = Θ( N ^1/3 ) dokonuje średnio O ( N ^5/3 ) porównań/inwersji/czasu działania. Yao znalazł średnią złożoność sortowania Shellsort z trzema przebiegami. Jego wynik został doprecyzowany przez Jansona i Knutha: średnia liczba porównań/inwersji/czasu działania dokonanych podczas sortowania Shell z trzema przerwami ( ch , cg , 1), gdzie h i g są względnie pierwsze, jest w pierwszym przebiegu, w drugim i w trzecim przejściu. ψ ( h , g ) w ostatnim wzorze jest skomplikowaną funkcją asymptotycznie równą . W szczególności, gdy h = ( N ^7/15 ) i g = Θ( N ^1/5 ), średni czas sortowania wynosi O ( N ^23/15 ). ${\ Displaystyle 0,5349N {\ sqrt {N}} -0,4387N-0,097 {\ sqrt {N}} + O (1)}$${\ Displaystyle {\ Frac {2N ^ {2}} {h}} + {\ sqrt {\ pi N ^ {3} h}}}$${\ Displaystyle {\ Frac {N ^ {2}} {4ch}} + O (N)}$${\ Displaystyle {\ Frac {1} {8g}} {\ sqrt {\ Frac {\ pi} {ch}}} (h-1) N ^ {3/2} + O (hN)}$${\ Displaystyle \ psi (h, g) N + {\ Frac {1} {8}} {\ sqrt {\ Frac {\ pi} {c}}} (c-1) N ^ {3/2} + O \left((c-1)gh^{1/2}N\right)+O\left(c^{2}g^{3}h^{2}\right)}$${\ Displaystyle {\ sqrt {\ Frac {\ pi h}{128}}} g + O \ lewo (g ^ {-1/2} h ^ {1/2} \ prawej) + O \ lewo (gh ^ {-1/2}\prawo)}$

Na podstawie eksperymentów przypuszcza się, że sortowanie Shellsort z sekwencją przerw Hibbarda przebiega w średnim czasie O ( N ^5/4 ) i że sekwencja Gonneta i Baeza-Yatesa wymaga średnio 0,41 N  ln  N  (ln ln  N  + 1/6 ) element się porusza. Przybliżenia średniej liczby operacji, które poprzednio były wykonywane dla innych sekwencji, kończą się niepowodzeniem, gdy posortowane tablice zawierają miliony elementów.

Poniższy wykres przedstawia średnią liczbę porównań pierwiastków w różnych wariantach Shellsort podzieloną przez teoretyczną dolną granicę tj. log ₂ N !, gdzie sekwencja 1, 4, 10, 23, 57, 132, 301, 701 została rozszerzona według wzoru . ${\ Displaystyle h_ {k} = \ l piętro 2,25 h_ {k-1} \ r piętro}$

Stosując teorię złożoności Kołmogorowa , Jiang, Li i Vitányi wykazali następujące dolne ograniczenie dla rzędu średniej liczby operacji/czasu działania w p-przebiegowym sortowaniu powłokowym: Ω( pN ^{1+1/ p} ) gdy p  ≤ log ₂ N i Ω( pN ) gdy p  > log ₂ N . Dlatego Shellsort ma szanse na działanie w średnim czasie, który asymptotycznie rośnie jak N log N tylko wtedy, gdy używa się sekwencji przerw, których liczba przerw rośnie proporcjonalnie do logarytmu rozmiaru tablicy. Nie wiadomo jednak, czy sortowanie Shell może osiągnąć ten asymptotyczny porządek złożoności średniej wielkości, który jest optymalny dla sortowań porównawczych. Dolna granica została poprawiona przez Vitányi dla każdej liczby podań na którym . Wynik ten implikuje na przykład dolną granicę Jiang-Li- Vitányi dla wszystkich sekwencji inkrementacji -pass i poprawia tę dolną granicę dla poszczególnych sekwencji inkrementacji. W rzeczywistości wszystkie granice (dolne i górne) obecnie znane dla przeciętnego przypadku są dokładnie dopasowane przez tę dolną granicę. Na przykład daje to nowy wynik, że górna granica Jansona-Knutha jest dopasowywana przez wynikową dolną granicę dla używanej sekwencji inkrementacji, pokazując, że trzyprzebiegowe Shellsort dla tej sekwencji inkrementacji używa porównań/inwersji/czasu działania. Formuła pozwala nam szukać sekwencji przyrostowych, które dają dolne granice, które są nieznane; na przykład sekwencja inkrementacji dla czterech przejść, która ma dolne ograniczenie większe niż dla sekwencji inkrementacji . Dolna granica staje się ${\displaystyle p}$${\ Displaystyle \ Omega (N \ suma _ {k = 1} ^ {p} h_ {k-1} / h_ {k})}$${\displaystyle h_{0}=N}$${\displaystyle p}$${\ Displaystyle \ Theta (N ^ {23/15})}$${\ Displaystyle \ Omega (pn ^ {1 + 1 / p}) = \ Omega (n ^ {5/4})}$${\ Displaystyle h_ {1} = n ^ {11/16},}$ ${\ Displaystyle h_ {2} = n ^ {7/16},}$ ${\ Displaystyle h_ {3}= n ^ {3/16},}$ ${\ Displaystyle h_{4}=1}$${\ Displaystyle T = \ Omega (n \ cdot (n ^ {1-11/16} + n ^ {11/16-7/16} + n ^ {7/16-3/16} + n ^ {3 /16})=\Omega (n^{1+5/16})=\Omega (n^{21/16}).}$

Najgorsza złożoność jakiejkolwiek wersji Shellsort jest wyższego rzędu: Plaxton, Poonen i Suel pokazali, że rośnie co najmniej tak szybko, jak . ${\ Displaystyle \ Omega \ lewo (N \ lewo ({\ log N \ nad \ log \ log N} \ prawej) ^ {2} \ prawej)}$

Aplikacje

Shellsort wykonuje więcej operacji i ma wyższy współczynnik braku pamięci podręcznej niż quicksort . Jednakże, ponieważ może być zaimplementowana przy użyciu niewielkiej ilości kodu i nie używa stosu wywołań , niektóre implementacje funkcji qsort w standardowej bibliotece C przeznaczonej dla systemów wbudowanych używają jej zamiast quicksort. Shellsort jest używany na przykład w bibliotece uClibc . Z podobnych powodów w przeszłości Shellsort był używany w jądrze Linuksa .

Shellsort może również służyć jako podalgorytm sortowania introspektywnego , do sortowania krótkich podtablic i zapobiegania spowolnieniu, gdy głębokość rekurencji przekracza określony limit. Ta zasada jest stosowana na przykład w kompresorze bzip2 .

Zobacz też

• Sortowanie grzebieniowe

Bibliografia

Bibliografia

• Knut, Donald E. (1997). „Metoda Shella”. Sztuka programowania komputerowego. Tom 3: Sortowanie i wyszukiwanie (wyd. 2). Czytanie, Massachusetts: Addison-Wesley. s. 83-95. Numer ISBN 978-0-201-89685-5.
• Analysis of Shellsort and Related Algorithms , Robert Sedgewick, Fourth European Symposium on Algorithms, Barcelona, ​​wrzesień 1996.

Zewnętrzne linki

• Animowane algorytmy sortowania: Shell Sort at the Wayback Machine (archiwum 10 marca 2015) – demonstracja graficzna
• Shellsort z lukami 5, 3, 1 jako węgierski taniec ludowy