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. Algorytm ten bywa też nazywany sortowaniem przez wstawianie z malejącym odstępem (ang. diminishing increment sort)[1].
Zasada działania
Shell zauważył, iż algorytm
sortowania przez wstawianie
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, że sortowany ciąg jest dzielony na podciągi, których elementy są odległe od siebie w sortowanym zbiorze o pewien odstęp h. Każdy z tych podzbiorów jest sortowany jakimś innym algorytmem; Shell używał sortowania przez wstawianie. Z każdym krokiem odstęp h jest zmniejszany, do czasu osiągnięcia wartości 1. Wraz ze zmianą h zmniejsza się liczba podciągów, lecz rośnie ich długość, jednak ciąg jest coraz bardziej uporządkowany.
Pseudokod:
- dobierz odległości
- dla wszystkich h: = hi powtarzaj:
- podziel sortowany ciąg na h podciągów
- każdy z nich posortuj
- (h = 1) ostatecznie posortuj ciąg
Efektywność sortowania zależy w dużym stopniu od wybranych odległości. Odstępy powinny być dobierane tak, aby w skład podciągów wchodziły elementy z jak największej liczby podciągów z kroków wcześniejszych - aby porównywać jak najwięcej par elementów z tablicy wejściowej. Dlatego zaleca się unikania odległości będących wielokrotnością jakieś liczby (np. dla 2: [8,4,2,1], czy 3: [12,9,6,3,1]). 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). Badania wykazały, że dobre efekty uzyskuje się dla odległości wyznaczonych wg wzorów h1 = 1,hi + 1 = 3hi + 1[2]. W przypadku zastosowania innego podziału, na przykład wg wzoru
Knutha
, można uzyskać algorytm sortowania nawet klasy O(n1,15)[3].
Przykład sortowania
sortowany ciąg | 11 | 20 | 1 | 14 | 4 | 3 | 7 | 8 | 19 | 15 | 16 | 17 | 6 | 18 | 9 | 5 | 13 | 2 | 12 | 10 |
h = 5 |
---|
przed sortowaniem |
---|
| 11 | 20 | 1 | 14 | 4 | 3 | 7 | 8 | 19 | 15 | 16 | 17 | 6 | 18 | 9 | 5 | 13 | 2 | 12 | 10 |
podciąg1 | 11 | | | | | 3 | | | | | 16 | | | | | 5 | | | | |
podciąg2 | | 20 | | | | | 7 | | | | | 17 | | | | | 13 | | | |
podciąg3 | | | 1 | | | | | 8 | | | | | 6 | | | | | 2 | | |
podciąg4 | | | | 14 | | | | | 19 | | | | | 18 | | | | | 12 | |
podciąg5 | | | | | 4 | | | | | 15 | | | | | 9 | | | | | 10 |
po sortowaniu |
---|
| 3 | 7 | 1 | 12 | 4 | 5 | 13 | 2 | 14 | 9 | 11 | 17 | 6 | 18 | 10 | 16 | 20 | 8 | 19 | 15 |
podciąg1 | 3 | | | | | 5 | | | | | 11 | | | | | 16 | | | | |
podciąg2 | | 7 | | | | | 13 | | | | | 17 | | | | | 20 | | | |
podciąg3 | | | 1 | | | | | 2 | | | | | 6 | | | | | 8 | | |
podciąg4 | | | | 12 | | | | | 14 | | | | | 18 | | | | | 19 | |
podciąg5 | | | | | 4 | | | | | 9 | | | | | 10 | | | | | 15 |
h = 3 |
---|
przed sortowaniem |
---|
| 3 | 7 | 1 | 12 | 4 | 5 | 13 | 2 | 14 | 9 | 11 | 17 | 6 | 18 | 10 | 16 | 20 | 8 | 19 | 15 |
podciąg1 | 3 | | | 12 | | | 13 | | | 9 | | | 6 | | | 16 | | | 19 | |
podciąg2 | | 7 | | | 4 | | | 2 | | | 11 | | | 18 | | | 20 | | | 15 |
podciąg3 | | | 1 | | | 5 | | | 14 | | | 17 | | | 10 | | | 8 | | |
po sortowaniu |
---|
| 3 | 2 | 1 | 6 | 4 | 5 | 9 | 7 | 8 | 12 | 11 | 10 | 13 | 15 | 14 | 16 | 18 | 17 | 19 | 20 |
podciąg1 | 3 | | | 6 | | | 9 | | | 12 | | | 13 | | | 16 | | | 19 | |
podciąg2 | | 2 | | | 4 | | | 7 | | | 11 | | | 15 | | | 18 | | | 20 |
podciąg3 | | | 1 | | | 5 | | | 8 | | | 10 | | | 14 | | | 17 | | |
h = 1 |
---|
| 3 | 2 | 1 | 6 | 4 | 5 | 9 | 7 | 8 | 12 | 11 | 10 | 13 | 15 | 14 | 16 | 18 | 17 | 19 | 20 |
po sortowaniu |
---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Implementacje
Implementacja w języku
C++
- podział według algorytmu Knutha.
void shell_sort_with_gap(int tab[], unsigned max, unsigned h) { //Dla każdego n wewnątrz przedziału //n jest indeksem wewnątrz każdego z przedziałów for (unsigned n=0; n<h; n++) for (unsigned i=n+h; i<max; i+=h) for(int j=i-h; j>=0 && tab[j]>tab[j+h]; j-=h) std::swap(tab[j+h],tab[j]);} void shell_sort(int tab[], unsigned max) { //Szukanie początkowego "skoku" dla przedziału unsigned h = 1; while (h<=max) h = h*3+1; h /= 9; //Sortujemy z coraz mniejszymi przedziałami dopóki są większe niż 0 while (h>0) { shell_sort_with_gap(tab, max, h); h /= 3; }}
Przypisy