JustPaste.it

Algorytmy sortujące - sortowanie motodą Shella

ccf98d087afe5637ab0de415d982481b.gif
 

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

97f73f30abc626541b297f1e16c6b1cc.gif

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

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


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 0f3edf48d7105d90b64e62b60465293f.gif n
Ostatecznie h = [hs : 9]

97f73f30abc626541b297f1e16c6b1cc.gifObliczmy 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 = 360 + 1 = 361 - stop, ponieważ jest większe od 200

h = [h6 : 9] = [361 : 9] = [40 1/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.

68edd3035210510abf94448b03dc40c0.gif

Dane wejściowe

n - liczba elementów w sortowanym zbiorze, n fcf29b5fb23d29abe7cda1c46ef2d90b.gif 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 fcf29b5fb23d29abe7cda1c46ef2d90b.gif N
 j - zmienna sterująca pętli,  j fcf29b5fb23d29abe7cda1c46ef2d90b.gif N
h - odstęp pomiędzy kolejnymi elementami podzbiorów,  h fcf29b5fb23d29abe7cda1c46ef2d90b.gif N
x - zawiera wybrany ze zbioru element

a5598ae70eef7f24033d7213a8d92d0e.gif

krok 1: h 06b8289c202f8386d983d78a0696921c.gif 1
krok 2: Powtarzaj h 06b8289c202f8386d983d78a0696921c.gif 3 b3a4eae19eb48210a1b6e59a103dbce8.gif h + 1, aż h 0f3edf48d7105d90b64e62b60465293f.gif n
krok 3: h 06b8289c202f8386d983d78a0696921c.gif h div 9
krok 4: Jeśli h = 0, to h 06b8289c202f8386d983d78a0696921c.gif 1
krok 5: Dopóki h > 0: wykonuj kroki 6...10
krok 6:     Dla j = n - h, n - h - 1, ..., 1: wykonuj kroki 7...9
krok 7:         x 06b8289c202f8386d983d78a0696921c.gif d[j];   i 06b8289c202f8386d983d78a0696921c.gif j + h
krok 8:         Dopóki (i 053fcb6d1767d9511b058cf3bdcafd1b.gif n) i (x > d[i]): wykonuj d[i - h] 06b8289c202f8386d983d78a0696921c.gif d[i];   i 06b8289c202f8386d983d78a0696921c.gif i + h
krok 9:         d[i - h] 06b8289c202f8386d983d78a0696921c.gif x
krok 10:     h 06b8289c202f8386d983d78a0696921c.gif h div 3
krok 11: Zakończ algorytm

dc2f7dfc8aa086a5e06c702025fa1014.gif

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:

Zwróć uwagę, iż 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.

2b8e1ff1fba746f9bb63fc85e08db833.gif

757dfa7f5c993180ae8b7c776bb96be4.gif    
   
   

138f74e51e5bfd79169638c797c2bf47.gif

Poniższe, przykładowe programy są praktyczną realizacją omawianego w tym rozdziale algorytmu. Zapewne można je napisać bardziej efektywnie. To już twoje zadanie. Dokładny opis stosowanych środowisk programowania znajdziesz we wstępie. Programy przed opublikowaniem w serwisie edukacyjnym zostały dokładnie przetestowane. Jeśli jednak znajdziesz jakąś usterkę (co zawsze może się zdarzyć), to prześlij o niej informację do autora. Pozwoli to ulepszyć nasze artykuły. Będziemy Ci za to wdzięczni.

 
       
Efekt uruchomienia programu

d21b9dda3cee1c02bdc72d763222ca8b.gif

// Sortowanie Metodą Shella
//-------------------------------------------------
// (C)2005 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.

9158d3c9671a0cc3dcdefb77b79f380b.gif

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

#include <cmath>
#include <iostream>
#include <iomanip>

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;
system("PAUSE"); return 0;
}

16413325c18c3b8c387a94497f7a760f.gif

' Sortowanie Metodą Shella
'-------------------------------------------------
' (C)2005 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

3fb20db18bfd66379151a26d72dd75b0.gif

<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)2005 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)2005 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>
 

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:

 

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

program TestCzasuSortowania;

uses Windows;

const
NAZWA = 'Sortowanie metodą Shella';
K1 = '----------------------------------------------------';
K2 = '(C)2005 mgr J.Wałaszek I LO 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)2005 mgr J.Wałaszek I LO 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)

d2e96160aa1889aa362a7f9c2faac553.gif

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:

  • optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów tpo, tpp, tpk
  • typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu tnp
  • pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu tod.
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 bcc018a9d63587cafc2fb5e91d8acd74.gif  3 tod
5
tpp bcc018a9d63587cafc2fb5e91d8acd74.gif tpk tnp bcc018a9d63587cafc2fb5e91d8acd74.gif 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

bcc018a9d63587cafc2fb5e91d8acd74.gif  1 n-0,14
3
źle
bcc018a9d63587cafc2fb5e91d8acd74.gif  1 n0,86
37
dobrze
bcc018a9d63587cafc2fb5e91d8acd74.gif  2 n-0,14
5
źle
bcc018a9d63587cafc2fb5e91d8acd74.gif  1 n-0,14
3
źle
bcc018a9d63587cafc2fb5e91d8acd74.gif  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ć.

2089eb08ed4a42c59919ce1295bba7c8.gif

  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.

 Dokument ten rozpowszechniany jest zgodnie z zasadami licencji

GNU Free Documentation License.

 

Źródło: mgr Jerzy Wałaszek