Sortowanie Shella

Sortowanie Shella (ang. Shellsort) to algorytm sortowania, który działa w miejscu i wykorzystuje porównania elementów. Jest to rozwinięcie sortowania przez wstawianie, umożliwiające jednoczesne porównania i zamiany elementów oddalonych od siebie. Algorytm ten, opracowany przez Donalda Shella w 1959 roku, najpierw sortuje elementy oddalone od siebie, a następnie zmniejsza odstępy między nimi, co przyspiesza proces sortowania w porównaniu do standardowego sortowania przez wstawianie.

Opis algorytmu

Sortowanie Shella jest algorytmem wieloprzebiegowym, gdzie każdy przebieg polega na sortowaniu przez wstawianie elementów oddalonych o ustaloną liczbę miejsc (h-sortowanie). Przykład sortowania tablicy z odstępami 5, 3 i 1 pokazuje, jak algorytm działa w kolejnych krokach.

Po 5-sortowaniu: fragmenty tablicy są sortowane oddzielnie, co prowadzi do częściowego uporządkowania.
Po 3-sortowaniu: kolejne fragmenty są sortowane, co skutkuje dalszym uporządkowaniem tablicy.
Po 1-sortowaniu: prowadzi do pełnego uporządkowania tablicy.

Algorytm nie jest stabilny i wykazuje lepsze wyniki dla częściowo uporządkowanych danych.

Ciągi odstępów

Różne ciągi odstępów wpływają na efektywność algorytmu. Każdy ciąg zakończony jedynką prowadzi do poprawnie działającego algorytmu, jednak ich właściwości mogą być różne. Przykłady ciągów to:

Ciąg Gonneta i Baezy-Yatesa o ilorazie 2,2.
Ciąg Tokudy, który można stosować do praktycznych zastosowań.

W przypadku potęg dwójki, złożoność w najgorszym przypadku wynosi $\Theta(N^2)$ . W praktyce, efektywne ciągi odstępów to 1, 4, 10, 23, 57, 132, 301, 701, które zostały znalezione doświadczalnie.

Złożoność obliczeniowa

Właściwości złożoności algorytmu są interesujące. Po $h_2$ -sortowaniu tablica pozostaje $h_1$ -posortowana. Złożoność pesymistyczna sortowania Shella wynosi co najmniej $\Omega(N(\log N/\log \log N)^2)$ .

Zastosowania

Sortowanie Shella, mimo że wykonuje więcej operacji niż sortowanie szybkie, jest wykorzystywane w systemach wbudowanych z powodu swojego krótkiego kodu i braku potrzeby używania stosu. Przykłady zastosowań obejmują implementacje funkcji qsort w bibliotece standardowej języka C oraz w jądrze systemu Linux do 2017 roku. Dodatkowo, sortowanie Shella można stosować jako podalgorytm w sortowaniu introspektywnym dla krótkich tablic.

Najnowsze aktualności:

Sortowanie Shella