Sortowanie Shella
Z Wikipedii
 |
Ten artykuł wymaga dopracowania zgodnie z zaleceniami edycyjnymi. Dokładniejsze informacje o tym, co należy poprawić, być może znajdziesz na stronie dyskusji tego artykułu. Po naprawieniu wszystkich błędów można usunąć tę wiadomość. |
Sortowanie Shella (ang. Shell sort) — algorytm sortowania, uogólnienie metody sortowania przez wstawianie, opisany po raz pierwszy w latach 50. XX w. przez informatyka Donalda Shella.
[edytuj] Zasada działania
Shell zauważył, iż algorytm sortowania przez wstawianie (ang. insertion sort) działa bardzo efektywnie w przypadku, gdy zbiór jest w dużym stopniu uporządkowany. Z kolei algorytm ten pracuje nieefektywnie w zbiorach nieuporządkowanych, ponieważ elementy są przesuwane w każdym obiegu o jedną pozycję przy wstawianiu elementu wybranego na listę uporządkowaną.
Pomysł Shella polegał na tym, iż sortowany zbiór dzielimy na podzbiory, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h. Każdy z tych podzbiorów sortujemy algorytmem przez wstawianie. Następnie odstęp zmniejszamy. Powoduje to powstanie nowych podzbiorów (będzie ich już mniej). Sortowanie powtarzamy i znów zmniejszamy odstęp, aż osiągnie on wartość 1. Wtedy sortujemy już normalnie za pomocą Insertion Sort. Jednakże z uwagi na wcześniejsze obiegi sortujące mamy ułatwione zadanie, ponieważ zbiór został w dużym stopniu uporządkowany. Dzięki początkowym dużym odstępom elementy były przesuwane w zbiorze bardziej efektywnie – na duże odległości. W wyniku otrzymujemy najlepszy pod względem czasu wykonania algorytm sortujący w klasie O(n2).
Efektywność algorytmu sortowania metodą Shella zależy w dużym stopniu od ciągu przyjętych odstępów. Pierwotnie Shell proponował pierwszy odstęp równy połowie liczby elementów w sortowanym zbiorze. Kolejne odstępy otrzymuje się dzieląc odstęp przez 2 (dzielenie całkowitoliczbowe). W przypadku zastosowania innego podziału, na przykład wedle wzoru Knutha, można uzyskać algorytm sortowania nawet klasy O(n1,15)[1].
Algorytm ten bywa też nazywany sortowaniem przez wstawianie z malejącym odstępem (ang. diminishing increment sort)[2].
