Sortowanie Shella


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 powtarzaj:
    • podziel sortowany ciąg na podciągów
    • każdy z nich posortuj
  • () 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: , czy 3: ). 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 [2]. W przypadku zastosowania innego podziału, na przykład wg wzoru Knutha, można uzyskać algorytm sortowania nawet klasy [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;
  }
}


  1. diminishing increment sort
  2. Adam Drozdek, Struktury danych w języku C, str. 370.
  3. Algorytmy Sortujące - Sortowanie metodą Shella