Sortowanie Shella

algorytm sortowania

Sortowanie Shella (ang. Shellsort) – jeden z algorytmów sortowania działających w miejscu i korzystających z porównań elementów. Można go traktować jako uogólnienie sortowania przez wstawianie lub sortowania bąbelkowego, dopuszczające porównania i zamiany elementów położonych daleko od siebie. Na początku sortuje on elementy tablicy położone daleko od siebie, a następnie stopniowo zmniejsza odstępy między sortowanymi elementami. Dzięki temu może je przenieść w docelowe położenie szybciej niż zwykłe sortowanie przez wstawianie.

Sortowanie Shella
Ilustracja
Przykład działania sortowania Shella z odstępami 23, 10, 4, 1
Rodzaj

sortowanie

Struktura danych

tablica

Złożoność
Czasowa

zależy od ciągu odstępów

Pamięciowa

Pierwszą wersję tego algorytmu, której zawdzięcza on swoją nazwę, opublikował w 1959 roku Donald Shell[1]. Złożoność czasowa sortowania Shella w dużej mierze zależy od użytego w nim ciągu odstępów. Wyznaczenie jej dla wielu stosowanych w praktyce wariantów tego algorytmu pozostaje problemem otwartym.

Opis algorytmuEdytuj

Sortowanie Shella to algorytm wieloprzebiegowy. Kolejne przebiegi polegają na sortowaniu przez proste wstawianie elementów oddalonych o ustaloną liczbę miejsc   czyli tak zwanym  -sortowaniu.

Poniżej zilustrowano sortowanie przykładowej tablicy metodą Shella z odstępami 5, 3, 1.

 

Pierwszy przebieg, czyli 5-sortowanie, sortuje osobno przez wstawianie zawartość każdego z fragmentów         Na przykład fragment   zmienia z (62, 17, 25) na (17, 25, 62).

Następny przebieg, czyli 3-sortowanie, sortuje przez wstawianie zawartość fragmentów    

Ostatni przebieg, czyli 1-sortowanie, to zwykłe sortowanie przez wstawianie całej tablicy  

Jak widać, fragmenty tablicy, na których operuje algorytm Shella, są z początku krótkie, a pod koniec dłuższe, ale prawie uporządkowane. W obu tych przypadkach sortowanie przez proste wstawianie działa wydajnie.

Sortowanie Shella nie jest stabilne, czyli może nie zachowywać wejściowej kolejności elementów o równych kluczach. Wykazuje ono zachowanie naturalne, czyli krótszy czas sortowania dla częściowo uporządkowanych danych wejściowych.

Ciągi odstępówEdytuj

Każdy ciąg odstępów zakończony jedynką prowadzi do poprawnie sortującego algorytmu. Własności tak otrzymanych wersji algorytmu mogą być jednak bardzo różne.

W poniższej tabeli zestawiono większość dotychczas opublikowanych propozycji ciągów odstępów. Niektóre z tych ciągów mają malejące wyrazy zależne od   czyli rozmiaru sortowanej tablicy. Inne to rosnące ciągi nieskończone, z których należy użyć w odwrotnej kolejności wyrazów mniejszych od  

Wyraz ogólny ciągu   Konkretne odstępy Rząd złożoności
pesymistycznej
Autor i rok publikacji
      [gdy  ] Shell, 1959[1]
      Frank, Lazarus, 1960[2]
      Hibbard, 1963[3]
  na początku 1     Papiernow, Stasiewicz, 1965[4]
kolejne liczby postaci       Pratt, 1971[5]
  nie większe niż       Knuth, 1973[6]
 
 
 
 
    Incerpi, Sedgewick, 1985[7]
  na początku 1     Sedgewick, 1986[8]
      Sedgewick, 1986[8]
    ? Gonnet, Baeza-Yates, 1991[9]
    ? Tokuda, 1992[10]
nieznany   ? Ciura, 2001[11]

Jeśli   jest potęgą dwójki, to sortowanie z oryginalnym ciągiem odstępów zaproponowanym przez Shella wykonuje w najgorszym przypadku   porównań. Przypadek ten zachodzi na przykład wtedy, gdy elementy większe i mniejsze od mediany zajmują odpowiednio parzyste i nieparzyste pozycje tablicy, ponieważ są one porównywane dopiero w ostatnim przebiegu.

Wersja zaproponowana przez Pratta ma wprawdzie wyższą złożoność niż optymalne dla algorytmów sortowania opartych na porównaniach   ale za to prowadzi do sieci sortującej o liczbie komparatorów tego samego rzędu, co sieć Batchera.

Zauważono, że średnio najmniej porównań elementów potrzeba, gdy ilorazy kolejnych odstępów leżą mniej więcej pomiędzy 2,2 a 2,3. Dlatego ciągi Gonneta i Baezy-Yatesa o ilorazie 2,2 i Tokudy o ilorazie 2,25 sprawdzają się w praktyce. Nie wiadomo jednak, dlaczego minimum przypada właśnie w tym miejscu. Zalecane jest też stosowanie odstępów o niskich największych wspólnych dzielnikach lub zgoła parami względnie pierwszych.

Pod względem średniej liczby porównań elementów najlepsze znane ciągi odstępów to ciąg 1, 4, 10, 23, 57, 132, 301, 701 i podobne, o wyrazach znalezionych doświadczalnie. Dalsze wyrazy optymalnych ciągów pozostają nieznane. Do dobrych wyników prowadzi przedłużenie ich zgodnie ze wzorem rekurencyjnym  

Do zastosowań praktycznych można też polecić ciąg Tokudy, określony prostymi wzorami   gdzie    

Złożoność obliczeniowaEdytuj

Zachodzi intrygująca własność: po  -sortowaniu dowolnej  -posortowanej tablicy pozostaje ona nadal  -posortowana[12]. Każda  -posortowana i  -posortowana tablica jest też  -posortowana dla wszystkich całkowitych nieujemnych   i   Zatem złożoność pesymistyczna sortowania Shella wiąże się z problemem Frobeniusa: dla danych całkowitych   o   liczba Frobeniusa   to największa liczba całkowita, której nie da się przedstawić w postaci   przy   całkowitych nieujemnych. Korzystając ze wzorów na liczby Frobeniusa, potrafimy wyznaczać złożoność pesymistyczną dla kilku klas ciągów odstępów. Dowiedzione przypadki zamieszczono w powyższej tabeli.

Żaden dowiedziony wynik na temat średniej liczby operacji nie dotyczy praktycznego ciągu odstępów. Espelid wyliczył ją dla odstępów będących potęgami dwójki jako  [13]. Knuth wyznaczył średnią złożoność sortowania  -elementowej tablicy z dwoma przebiegami   jako  [6]. Wynika stąd, że dwuprzebiegowe sortowanie Shella z   wykonuje średnio   porównań. Yao znalazł średnią złożoność sortowania z trzema przebiegami[14]. Jego wynik uściślili potem Janson i Knuth[15]. Średnia liczba porównań wykonywanych podczas sortowania z trzema przebiegami   gdzie   i   są względnie pierwsze wynosi   w pierwszym przebiegu,   w drugim przebiegu i   w trzecim przebiegu. Skomplikowana funkcja   z ostatniego wzoru jest asymptotycznie równa   W szczególności, gdy   a   średni czas sortowania jest rzędu  

Na podstawie doświadczeń odgadnięto, że z ciągami Hibbarda i Knutha algorytm działa w średnim czasie rzędu  [6], a z ciągiem Gonneta i Baezy-Yatesa wykonuje średnio   przesunięć elementów[9]. Aproksymacje średniej liczby operacji czynione kiedyś dla innych ciągów zawodzą, gdy sortowane tablice liczą miliony elementów.

Poniższy wykres przedstawia średnią liczbę porównań elementów w różnych wariantach sortowania Shella, dzieloną przez teoretyczne minimum, czyli   przy czym do ciągu 1, 4, 10, 23, 57, 132, 301, 701 dodano dalsze wyrazy zgodnie ze wzorem  

Korzystając z teorii złożoności Kołmogorowa, Jiang, Li i Vitányi udowodnili następujące dolne ograniczenia na rząd średniej liczby operacji w  -przebiegowym sortowaniu Shella:   przy   i   przy  [16]. Zatem algorytm ten ma szanse działać w średnim czasie rosnącym asymptotycznie jak   tylko z ciągami o liczbie odstępów rosnącej proporcjonalnie do logarytmu długości sortowanych tablic. Nie wiadomo jednak, czy sortowanie Shella może osiągnąć taki asymptotyczny rząd złożoności średniej, optymalny dla sortowań opartych na porównaniach.

Złożoność pesymistyczna dowolnej wersji sortowania Shella jest wyższego rzędu: Plaxton, Poonen i Suel wykazali, że rośnie ona co najmniej jak  [17].

ZastosowaniaEdytuj

Sortowanie Shella wykonuje więcej działań niż sortowanie szybkie, ponadto częściej od niego nie trafia w pamięć podręczną procesora przy odczytach z pamięci.

Ze względu na stosunkowo krótki kod i nieużywanie stosu bywa ono stosowane zamiast sortowania szybkiego w implementacjach funkcji qsort z biblioteki standardowej języka C przeznaczonych dla systemów wbudowanych. Używa go na przykład biblioteka uClibc[18]. Z podobnych przyczyn implementacja sortowania Shella była w jądrze systemu operacyjnego Linux[19] do 2017 roku[20].

Można też stosować sortowanie Shella jako podalgorytm sortowania introspektywnego używany do sortowania krótkich podtablic, a także gdy głębokość rekurencji przekroczy zadany limit, aby zapobiec patologicznemu spowolnieniu sortowania. Działa tak na przykład bzip2, jeden z programów do kompresji danych[21].

Zobacz teżEdytuj

PrzypisyEdytuj

  1. a b D.L. Shell. A High-Speed Sorting Procedure. „Communications of the ACM”. 2 (7), s. 30–32, 1959. DOI: 10.1145/368370.368387. 
  2. R.M. Frank, R.B. Lazarus. A High-Speed Sorting Procedure. „Communications of the ACM”. 3 (1), s. 20–22, 1960. DOI: 10.1145/366947.366957. 
  3. Thomas N. Hibbard. An Empirical Study of Minimal Storage Sorting. „Communications of the ACM”. 6 (5), s. 206–213, 1963. DOI: 10.1145/366552.366557. 
  4. А.А. Папернов, Г.В. Стасевич. Об одном методе упорядочивания информации в запоминающих устройствах цифровых машин. „Проблемы передачи информации”. 1 (3), s. 81–98, 1965 (ros.). 
  5. Vaughan Ronald Pratt: Shellsort and Sorting Networks (Outstanding Dissertations in the Computer Sciences). Garland, 1979. ISBN 0-824-04406-1.
  6. a b c Metoda Shella. W: Donald E. Knuth: Sztuka programowania. Wyd. 1. T. 3: Sortowanie i wyszukiwanie. WNT, 2002, s. 87–99. ISBN 83-204-2554-9.
  7. Janet Incerpi, Robert Sedgewick. Improved Upper Bounds on Shellsort. „Journal of Computer and System Sciences”. 31 (2), s. 210–224, 1985. 
  8. a b Robert Sedgewick. A New Upper Bound for Shellsort. „Journal of Algorithms”. 7 (2), s. 159–173, 1986. DOI: 10.1016/0196-6774(86)90001-5. 
  9. a b Shellsort. W: Gaston H. Gonnet, Ricardo Baeza-Yates: Handbook of Algorithms and Data Structures: In Pascal and C. Wyd. 2. Reading, Massachusetts: Addison-Wesley, 1991, s. 161–163. ISBN 0-201-41607-7.
  10. Naoyuki Tokuda: An Improved Shellsort. W: Jan van Leeuven: Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture. Amsterdam: North-Holland Publishing Co., 1992, s. 449–457. ISBN 0-444-89747-X.
  11. Marcin Ciura: Best Increments for the Average Case of Shellsort. W: Rusins Freiwalds: Proceedings of the 13th International Symposium on Fundamentals of Computation Theory. London: Springer-Verlag, 2001, s. 106–117. ISBN 3-540-42487-3.
  12. David Gale, Richard M. Karp. A Phenomenon in the Theory of Sorting. „Journal of Computer and System Sciences”. 6 (2), s. 103–115, 1972. DOI: 10.1016/S0022-0000(72)80016-3. 
  13. Terje O. Espelid. Analysis of a Shellsort Algorithm. „BIT Numerical Mathematics”. 13 (4), s. 394–400, 1973. DOI: 10.1007/BF01933401. 
  14. Andrew Chi-Chih Yao. An Analysis of  -Shellsort. „Journal of Algorithms”. 1 (1), s. 14–50, 1980. DOI: 10.1016/0196-6774(80)90003-6. 
  15. Svante Janson, Donald E. Knuth. Shellsort with Three Increments. „Random Structures and Algorithms”. 10 (1–2), s. 125–142, 1997. DOI: 10.1.1.54.9911. 
  16. Tao Jiang, Ming Li, Paul Vitányi. A Lower Bound on the Average-Case Complexity of Shellsort. „Journal of the ACM”. 47 (5), s. 905–911, 2000. DOI: 10.1.1.6.6508. 
  17. C. Greg Plaxton, Bjorn Poonen, Torsten Suel. Improved Lower Bounds for Shellsort. „Annual Symposium on Foundations of Computer Science”. 33, s. 226–235, 1992. DOI: 10.1.1.43.1393. 
  18. Manuel Novoa III: libc/stdlib/stdlib.c. [dostęp 2011-03-30].
  19. kernel/groups.c. [dostęp 2012-02-06].
  20. kernel/git/torvalds/linux.git - Linux kernel source tree, git.kernel.org [dostęp 2020-11-14].
  21. Julian Seward: bzip2/blocksort.c. [dostęp 2011-03-30].

BibliografiaEdytuj

Linki zewnętrzneEdytuj