Startuj z nami!

www.szkolnictwo.pl

praca, nauka, rozrywka....

mapa polskich szkół
Nauka Nauka
Uczelnie Uczelnie
Mój profil / Znajomi Mój profil/Znajomi
Poczta Poczta/Dokumenty
Przewodnik Przewodnik
Nauka Konkurs
uczelnie

zamów reklamę
zobacz szczegóły
uczelnie

Sortowanie Shella

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].

Spis treści

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 h_i = {h_n, \ldots, 1}
  • 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ąg1120114437819151617618951321210
h = 5
przed sortowaniem
1120114437819151617618951321210
podciąg1113165
podciąg22071713
podciąg31862
podciąg414191812
podciąg5415910
po sortowaniu
3711245132149111761810162081915
podciąg1351116
podciąg27131720
podciąg31268
podciąg412141819
podciąg5491015
h = 3
przed sortowaniem
3711245132149111761810162081915
podciąg131213961619
podciąg274211182015
podciąg3151417108
po sortowaniu
3216459781211101315141618171920
podciąg136912131619
podciąg224711151820
podciąg3158101417
h = 1
3216459781211101315141618171920
po sortowaniu
1234567891011121314151617181920

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

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


Inne hasła zawierające informacje o "Sortowanie Shella":

Sortowanie ...

Kod pocztowy ...

Sortowanie bąbelkowe ...

Sortowanie przez scalanie ...

Sortowanie przez zliczanie ...

Sortowanie kubełkowe ...

Sortowanie pozycyjne ...

Sortowanie biblioteczne ...

Sortowanie przez wybieranie ...

Sortowanie Shella Sortowanie Shella ( ang. Shell sort) — algorytm sortowania , uogólnienie metody sortowania przez ...


Inne lekcje zawierające informacje o "Sortowanie Shella":

Zagrożenia gleb (plansza 21) ...

Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór (plansza 3) ...

Algorytmy sortujące - sortowanie bąbelkowe, część II (plansza 10) ...





Zachodniopomorskie Pomorskie Warmińsko-Mazurskie Podlaskie Mazowieckie Lubelskie Kujawsko-Pomorskie Wielkopolskie Lubuskie Łódzkie Świętokrzyskie Podkarpackie Małopolskie Śląskie Opolskie Dolnośląskie