Sortowanie Shella
           Shell Sort


Podrozdziały    

Algorytm

W latach 50-tych 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 (sprawdź wyniki naszych badań czasów sortowania dla tego algorytmu). 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ą Instertion 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).

 

Przykład:

Posortujemy metodą Shella zbiór ośmiu liczb: { 4 2 9 5 6 3 8 1 } w porządku rosnącym. Zbiór posiada osiem elementów, zatem przyjmiemy na wstępie odstęp h równy 4. Taki odstęp podzieli zbiór na 4 podzbiory, których elementy będą elementami zbioru wejściowego odległymi od siebie o 4 pozycje. Każdy z otrzymanych podzbiorów sortujemy algorytmem sortowania przez wstawianie. Ponieważ zbiory te są dwuelementowe, to sortowanie pędzie polegało na porównaniu pierwszego elementu podzbioru z elementem drugim i ewentualną zamianę ich miejsc, jeśli będą w niewłaściwym porządku.

Podział, h=4 Sortowanie Wynik
   
 4  2  9  5  6  3  8  1  
- Zbiór wejściowy
1
 4           6 
  4   6   
 4           6 
2
    2           3 
  2   3  
    2           3 
3
       9           8 
  8   9  
       8           9 
4
          5           1 
  1   5  
          1           5 
Zbiór wyjściowy -
 4  2  8  1  6  3  9  5  

 

Zmniejszamy odstęp h o połowę, więc h = 2. Zbiór podstawowy zostanie podzielony na dwa podzbiory. Każdy z tych podzbiorów sortujemy przez wstawianie:

 

Podział, h=2 Sortowanie Wynik
   
 4  2  8  1  6  3  9  5 
- Zbiór wejściowy
1
 4     8     6     9 
  4   6   8   9  
 4     6     8     9 
2
    2     1     3     5 
  1   2   3   5 
    1     2     3     5  
Zbiór wyjściowy -
 4  1  6  2  8  3  9  5 

 

Zmniejszamy odstęp h o połowę, h = 1. Taki odstęp nie dzieli zbioru wejściowego na podzbiory, więc teraz będzie sortowany przez wstawianie cały zbiór. Jednak algorytm sortujący ma ułatwioną pracę, ponieważ dzięki poprzednim dwóm obiegom zbiór został częściowo uporządkowany - elementy małe zbliżyły się do początku zbioru, a elementy duże do końca.

 

Podział, h=1 Sortowanie Wynik
   
 4  1  6  2  8  3  9  5  
- Zbiór wejściowy
1
 4  1  6  2  8  3  9  5 
 1  2  3  4  5  6  8  9  
 1  2  3  4  5  6  8  9  
Zbiór wyjściowy -
 1  2  3  4  5  6  8  9 

 

Dobór optymalnych odstępów

Donald Knuth
prof. Donald Knuth

Kluczowym elementem wpływającym na efektywność sortowania metodą Shella jest właściwy dobór ciągu odstępów. Okazuje się, iż ciąg zaproponowany przez twórcę algorytmu jest jednym z najgorszych, ponieważ w kolejnych podzbiorach uczestniczą wielokrotnie te same elementy (możesz to prosto sprawdzić w podanym powyżej przykładzie).

Dotąd problem optymalnych odstępów w algorytmie sortowania metodą Shella nie został rozwiązany matematycznie, ponieważ w ogólnym przypadku jest niezwykle trudny. Wielu badaczy proponowało na wybór tych odstępów różne ciągi liczbowe otrzymując lepsze lub gorsze rezultaty.

Na przykład profesor Donald Knuth (autor "Sztuki Programowania Komputerów" - "The Art of Computer Programming") zbadał bardzo dokładnie algorytm sortowania metodą Shella i doszedł do wniosku, iż dobry ciąg odstępów dla n elementowego zbioru można wyznaczyć następująco:

Przyjmujemy h1 = 1
obliczamy hs = 3hs-1 + 1 aż do momentu gdy hs n
Ostatecznie h = [hs : 9]

 

Przykład:

Obliczmy pierwszy odstęp dla zbioru o n = 200 elementach:

 

h1 = 1
h2 = 3h1 + 1 = 3 + 1 = 4
- mniejsze od  200, kontynuujemy
h3 = 3h2 + 1 = 12 + 1 = 13 - kontynuujemy
h4 = 3h3 + 1 = 39 + 1 = 40 - kontynuujemy
h5 = 3h4 + 1 = 120 + 1 = 121 - kontynuujemy
h6 = 3h5 + 1 = 363 + 1 = 364 - stop, ponieważ jest większe od 200

h = [h6 : 9] = [364 : 9] = [40 4/9] = 40 (zwróć uwagę, iż jest to zawsze element wcześniejszy o dwie pozycje, czyli h4)

 

Kolejne odstępy obliczamy dzieląc całkowitoliczbowo bieżący odstęp przez 3. Taki właśnie sposób wyliczania odstępów przyjmiemy w naszym algorytmie.

 

Specyfikacja problemu

Dane wejściowe

n - liczba elementów w sortowanym zbiorze, n N
d[ ] - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n.

Dane wyjściowe

d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

i - indeks elementu listy uporządkowanej,   i N
j - zmienna sterująca pętli,  j N
h - odstęp pomiędzy kolejnymi elementami podzbiorów,  h N
x - zawiera wybrany ze zbioru element

 

Lista kroków

K01: h ← 1
K02: Powtarzaj h ← 3h + 1, hn
K03: hh div 9
K04: Jeśli h = 0, to h ← 1
K05: Dopóki h > 0: wykonuj K06...K10
K06:     Dla j = n - h, n - h - 1, ..., 1: wykonuj K07...K09
K07:         x ← d[j];   ij + h
K08:         Dopóki (in) i (x > d[i]): wykonuj d[i - h] ← d[i];   ii + h
K09:         d[i - h] ← x
K10:     hh div 3
K11: Zakończ

 

Schemat blokowy

flow

Algorytm sortowania metodą Shella jest ulepszonym algorytmem sortowania przez wstawianie. Aby się o tym przekonać, wystarczy spojrzeć na schemat blokowy. Kolorem szarym zaznaczyliśmy na nim bloki, które dokładnie odpowiadają algorytmowi sortowania przez wstawianie. Jedyną modyfikacją jest wprowadzenie odstępu h zamiast liczby 1.

Na początku algorytmu wyznaczamy wartość początkowego odstępu h. Wykorzystujemy tu sugestie prof. Donalda Knutha.

Po wyznaczeniu h rozpoczynamy pętlę warunkową nr 1. Pętla ta jest wykonywana dotąd, aż odstęp h przyjmie wartość 0. Wtedy kończymy algorytm, zbiór będzie posortowany.

Wewnątrz pętli nr 1 umieszczony jest opisany wcześniej algorytm sortowania przez wstawianie, który dokonuje sortowania elementów poszczególnych podzbiorów wyznaczonych przez odstęp h. Po zakończeniu sortowania podzbiorów odstęp h jest zmniejszany i następuje powrót na początek pętli warunkowej nr 1.


 
Uwaga techniczna:

Każdy obieg pętli nr 2 sortuje przemiennie jeden element z kolejnych podzbiorów. Najpierw będą to elementy przedostatnie w kolejnych podzbiorach wyznaczonych odstępem h, później wcześniejsze i wcześniejsze. Takie podejście znacząco upraszcza algorytm sortowania.

 

Programy

Efekt uruchomienia programu
 Sortowanie metoda Shella
--------------------------
  (C)2005 Jerzy Walaszek

Przed sortowaniem:

  65  89  49  99  57   2  35   2  86  48  90  54  89  20  32   6  52  20  40  17

Po sortowaniu:

   2   2   6  17  20  20  32  35  40  48  49  52  54  57  65  86  89  89  90  99

 

DevPascal
// Sortowanie Metodą Shella
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

program Shell_Sort;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Program główny
//---------------

var
  h,i,j,x : integer;
begin
  writeln(' Sortowanie metoda Shella ');
  writeln('--------------------------');
  writeln('  (C)2005 Jerzy Walaszek  ');
  writeln;

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  randomize;
  for i := 1 to N do d[i] := random(100);
  writeln('Przed sortowaniem:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;

// Wyznaczamy wartość początkowego przesunięcia

  h := 1;
  repeat
    h := 3 * h + 1;
  until h >= N;
  h := (h div 9);
  if h = 0 then h := 1; // istotne dla małych N, dla większych można pominąć!

// Sortujemy

  while h > 0 do
  begin
    for j := N - h downto 1 do
    begin
      x := d[j];
      i := j + h;
      while (i <= N) and (x > d[i]) do
      begin
        d[i - h] := d[i];
        inc(i, h);
      end;
      d[i - h] := x;
    end;
    h := h div 3;
  end;

// Wyświetlamy wynik sortowania

  writeln('Po sortowaniu:'); writeln;
  for i := 1 to N do write(d[i] : 4);
  writeln;
  writeln('Nacisnij Enter...');
  readln;
end.
Code::Blocks
// Sortowanie metodą Shella
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <cmath>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <time.h>

using namespace std;

const int N = 20; // Liczebność zbioru.

// Program główny
//---------------

int main()
{
  int d[N],h,i,j,x;
  
  cout << " Sortowanie metoda Shella\n"
          "--------------------------\n"
          "  (C)2005 Jerzy Walaszek\n\n"
          "Przed sortowaniem:\n\n";

// Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi
// a następnie wyświetlamy jej zawartość

  srand((unsigned)time(NULL));

  for(i = 0; i < N; i++) d[i] = rand() % 100;
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;

// Wyznaczamy wartość początkowego przesunięcia

  for(h = 1; h < N; h = 3 * h + 1);
  h /= 9;
  if(!h) h++; // istotne dla małych N, dla większych można pominąć!

// Sortujemy

  while(h)
  {
    for(j = N - h - 1; j >= 0; j--)
    {
      x = d[j];
      i = j + h;
      while((i < N) && (x > d[i]))
      {
        d[i - h] = d[i];
        i += h;
      }
      d[i - h] = x;
    }
    h /= 3;
  }

// Wyświetlamy wynik sortowania

  cout << "Po sortowaniu:\n\n";
  for(i = 0; i < N; i++) cout << setw(4) << d[i];
  cout << endl;
  return 0;
}
Free Basic
' Sortowanie Metodą Shella
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

  OPTION EXPLICIT
  
  CONST N = 20 ' Liczebność zbioru.

  DIM d(1 TO N) AS INTEGER
  DIM h AS INTEGER, i AS INTEGER, j AS INTEGER, x AS INTEGER

  PRINT " Sortowanie metoda Shella "
  PRINT "--------------------------"
  PRINT "  (C)2005 Jerzy Walaszek  "
  PRINT

' Najpierw wypełniamy tablicę d() liczbami pseudolosowymi
' a następnie wyświetlamy jej zawartość

  RANDOMIZE TIMER
  FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT
  PRINT "Przed sortowaniem:"
  PRINT
  FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
  PRINT

' Wyznaczamy wartość początkowego przesunięcia

  h = 1
  DO
    h = 3 * h + 1
  LOOP UNTIL h >= N
  h = INT(h / 9)
  IF h = 0 THEN h = 1 ' istotne dla małych N, dla większych można pominąć!

' Sortujemy

  WHILE h > 0
    FOR j = N - h TO 1 STEP -1
      x = d(j)
      i = j + h
      WHILE (i <= N) AND (x > d(i))
        d(i - h) = d(i)
        i = i + h
      WEND
      d(i - h) = x
    NEXT
    h = INT(h / 3)
  WEND

' Wyświetlamy wynik sortowania

  PRINT "Po sortowaniu:"
  PRINT
  FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
  PRINT
  PRINT "Nacisnij Enter..."
  SLEEP
  END
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmshellsort">
      <h3 style="text-align: center">Sortowanie Metodą Shella</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Sortuj" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Sortowanie Metodą Shella
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var N = 20; // Liczebność zbioru.

function main()
{
  var d = new Array(N);
  var i,j,ip,ik,x,t;

  // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi

  for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100);
  t = "Przed sortowaniem:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  t += "<BR><BR>";

  // Wyznaczamy początkowe przesunięcie

  for(h = 1; h < N; h = 3 * h + 1);
  h = Math.floor(h / 9);
  if(!h) h++; // istotne dla małych N, dla większych można pominąć!

  // Sortujemy

  while(h)
  {
    for(j = N - h - 1; j >= 0; j--)
    {
      x = d[j];
      i = j + h;
      while((i < N) && (x > d[i]))
      {
        d[i - h] = d[i];
        i += h;
      }
      d[i - h] = x;
    }
    h = Math.floor(h / 3);
  }

  // Wyświetlamy wynik sortowania

  t += "Po sortowaniu:<BR><BR>";
  for(i = 0; i < N; i++) t += d[i] + " ";
  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Sortowanie Metodą Shella

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

 

Einstein
DLA
GENIUSZA

Badania algorytmów sortowania

W celach badawczych testujemy czas wykonania algorytmu sortowania metodą Shella w środowisku opisanym we wstępie. Ponieważ algorytm jest bardzo szybki, zdecydowaliśmy się przetestować go na pełnym zakresie danych od 1000 do 128000 elementów. Program testujący jest następujący:

 

DevPascal
// Program testujący czas sortowania dla
// danego algorytmu sortującego
//--------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// w Tarnowie
//--------------------------------------

program TestCzasuSortowania;

uses Windows;

const
  NAZWA = 'Sortowanie metodą Shella';
  K1    = '-----------------------------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 8; // określa ostatnie LN
  LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000);

var
  d         : array[1..128000] of real; // sortowana tablica
  n         : integer;                  // liczba elementów
  qpf,tqpc  : int64;                    // dane dla pomiaru czasu
  qpc1,qpc2 : int64;

// Tutaj umieszczamy procedurę sortującą tablicę d
//-------------------------------------------------------
function Sort : extended;
var
  i,j,h : integer;
  x     : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  h := 1;
  repeat
    h := 3 * h + 1;
  until h >= n;
  h := (h div 9);
  while(h > 0) do
  begin
    for j := n - h downto 1 do
    begin
      x := d[j];
      i := j + h;
      while (i <= n) and (x > d[i]) do
      begin
        d[i - h] := d[i];
        i += h;
      end;
      d[i - h] := x;
    end;
    h := h div 3;
  end;
  QueryPerformanceCounter(addr(qpc2));
  Sort := (qpc2 - qpc1 - tqpc) / qpf;
end;

// Program główny
//---------------
var
  i,j,k               : integer;
  tpo,tod,tpp,tpk,tnp : extended;
  f                   : Text;
begin
  if QueryPerformanceFrequency(addr(qpf)) then
  begin
    QueryPerformanceCounter(addr(qpc1));
    QueryPerformanceCounter(addr(qpc2));
    tqpc := qpc2 - qpc1;

    assignfile(f,'wyniki.txt'); rewrite(f);

// Wydruk na ekran

    writeln('Nazwa: ',NAZWA);
    writeln(K1);
    writeln(K2);
    writeln;
    writeln(K3);

// Wydruk do pliku

    writeln(f,'Nazwa: ',NAZWA);
    writeln(f,K1);
    writeln(f,K2);
    writeln(f,'');
    writeln(f,K3);
    for i := 1 to MAX_LN do
    begin
      n := LN[i];

// Czas sortowania zbioru posortowanego

      for j := 1 to n do d[j] := j;
      tpo := Sort;

// Czas sortowania zbioru posortowanego odwrotnie

      for j := 1 to n do d[j] := n - j;
      tod := Sort;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na początku - średnia z 10 obiegów

      tpp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[1] := random * n + 1;
        tpp += Sort;
      end;
      tpp /= 10;

// Czas sortowania zbioru posortowanego
// z przypadkowym elementem na końcu - średnia z 10 obiegów

      tpk := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := k;
        d[n] := random * n + 1;
        tpk += Sort;
      end;
      tpk /= 10;

// Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów

      tnp := 0;
      for j := 1 to 10 do
      begin
        for k := 1 to n do d[k] := random;
        tnp += Sort;
      end;
      tnp /= 10;

      writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
      writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6);
    end;
    writeln(K4);
    writeln(f,K4);
    writeln(f,'Koniec');
    closefile(f);
    writeln;
    writeln('Koniec. Wyniki w pliku WYNIKI.TXT');
  end
  else writeln('Na tym komputerze program testowy nie pracuje !');
  writeln;
  write('Nacisnij klawisz ENTER...'); readln;
end.

 

Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):

 

Zawartość pliku wygenerowanego przez program
Nazwa: Sortowanie metodą Shella
-----------------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.000296 0.000509 0.000317 0.000320 0.000733
2000 0.000703 0.001106 0.000747 0.000781 0.001714
4000 0.001600 0.002938 0.001697 0.001707 0.005099
8000 0.003368 0.006315 0.003527 0.003490 0.008908
16000 0.007572 0.012641 0.009127 0.009796 0.020476
32000 0.016916 0.026260 0.017641 0.017699 0.046787
64000 0.034763 0.056447 0.036213 0.036643 0.104610
128000 0.076624 0.123158 0.080277 0.080089 0.236036
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Podsumowanie

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu binarnego sortowania przez wstawianie wyciągamy następujące wnioski:

 

Cechy Algorytmu Sortowania Metodą Shella
klasa złożoności obliczeniowej optymistyczna O(n1,14)
klasa złożoności obliczeniowej typowa O(n1,15)
klasa złożoności obliczeniowej pesymistyczna
Sortowanie w miejscu TAK
Stabilność NIE

 

Klasy złożoności obliczeniowej szacujemy następująco:

Własności algorytmu
Algorytm tpo tod tpp tpk tnp
Sortowanie metodą Shella z odstępami Knutha O(n1,14) O(n1,14) O(n1,14) O(n1,14) O(n1,14)
tpo   3 tod
5
tpp tpk tnp 2tod
  1. Wszystkie badane czasy sortowania są dosyć dobrze proporcjonalne do O(n1,12...1,16). Przyjęliśmy wartość średnią O(n1,14) - jest to oszacowanie przybliżone, które należy brać z pewną rezerwą.
  2. Czas sortowania zbioru uporządkowanego odwrotnie jest krótszy od czasu sortowania zbioru nieuporządkowanego. Wynika stąd, iż nie jest to przypadek pesymistyczny dla tego algorytmu.
  3. Zbiory w znacznym stopniu uporządkowane są sortowane dużo szybciej od zbiorów nieuporządkowanych.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp

Sortowanie przez wstawianie

Sortowanie metodą Shella

  1 n-0,14
3
źle
  1 n0,86
37
dobrze
  2 n-0,14
5
źle
  1 n-0,14
3
źle
  1 n0,86
142
dobrze
  1. Z oszacowań wzrostu prędkości wynika, iż algorytm sortowania metodą Shella jest bezkonkurencyjny w klasie O(n2) algorytmów sortujących przy sortowaniu zbiorów nieuporządkowanych i zbiorów posortowanych odwrotnie, czyli w przypadku ogólnym. Jednakże przy sortowaniu zbiorów w dużym stopniu uporządkowanych lepszym okazuje się poprzednio opisany algorytm sortowania przez wstawianie. Oszacowania wyznaczonych wzrostów prędkości nie należy traktować jako wzorów matematycznych - to tylko próba dopasowania pewnych funkcji, które w przyszłości należy dokładniej zweryfikować.

Zadania dla ambitnych

  1. Dlaczego algorytm sortowania metodą Shella nie jest stabilny jeśli chodzi o zachowanie kolejności elementów równych w sortowanym zbiorze?
  2. Wyjaśnij, dlaczego algorytm sortowania przez wstawianie szybciej sortuje zbiory uporządkowane od algorytmu sortowania metodą Shella.
  3. Porównaj wzrost prędkości algorytmu sortowania metodą Shella w stosunku do algorytmów sortowania bąbelkowego i sortowania przez wybór. Wyciągnij odpowiednie wnioski.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.