Sortowanie Shella

Z Wikipedii

Sortowanie Shella (Shellsort) -W latach 50. ubiegłego wieku informatyk Donald Shell zauważył, iż algorytm sortowania przez wstawianie pracuje 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 szybkości czasu wykonania algorytm sortujący w klasie O(n2). Algorytm ten nosi również nazwę algorytmu sortowania przez wstawianie z malejącym odstępem (ang. Diminishing Increment Sort). 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 otrzymujemy 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)(http://www.i-lo.tarnow.pl/edu/inf/alg/algsort/pages/012.php) jeden z najstarszych algorytmów sortowania wynaleziony w 1959 przez Donalda L. Shella. Jest szybki w działaniu oraz łatwy w implementacji i zrozumieniu.

Jest rozszerzeniem metody sortowania przez wstawianie.

[edytuj] Przykład algorytmu

Przykład algorytmu sortowania Shella w C#.

public static void ShellSort(IComparable[] a, int[] h)
{
  int t = h.Length;

  // h[t - 1] == 1
  // t >= 1
  // h[1] > h[2] > h[3] > ... > 1
  if((t < 1) || (h[t - 1] != 1))
    throw new ArgumentException("Rozmiar tablicy *h* musi być równy co najmniej 1. Ostatni element tablicy musi byc równy 1.", "h");
  for(int i = 1; i < t; i++)
    if(h[i - 1] <= h[i])
      throw new ArgumentException("Elementy tablicy *h* muszą być posortowane malejąco.", "h");

  for(int m = 0; m < t; m++)
  {
    int k = h[m];
    for(int i = k; i < a.Length; i++)
    {
      IComparable x = a[i];
      int j = i - k;
      while((j >= 0) && (x.CompareTo(a[j]) < 0))
      {
        a[j + k] = a[j];
        j -= k;
      }
      a[j + k] = x;
    }
  }
}

Przykład algorytmu sortowania Shella w C.

int tabela[N];
int i, j, tmp;
void shell(){
        int h = 1;
        while (h < N) {
                h = 3*h+1;
                }
        h = h/3;
        for (h; h>0; h=h/3){
                for(i=0;i<N;i++)
                for (i=h; i<N; i=i+h){
                        j = i;
                        tmp = tabela[j];
                        while ((j>0) && (tmp<tabela[j-h])){
                                tabela[j] = tabela[j-h];
                                j = j - h;
                                }
                        tabela[j] = tmp;
                        }
                }
        }

To jest tylko zalążek artykułu z dziedziny informatyki. Jeśli możesz, rozbuduj go.