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).
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 62 2 3 2 3 2 33 9 8 8 9 8 94 5 1 1 5 1 5Zbiór wyjściowy - 4 2 8 1 6 3 9 5Zmniejszamy 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
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]
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 = 360 + 1 = 361 - stop, ponieważ jest większe od 200h = [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.
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
krok 1: h 1 krok 2: Powtarzaj h 3 h + 1, aż h n krok 3: h h div 9 krok 4: Jeśli h = 0, to h 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 d[j]; i j + h krok 8: Dopóki (i n) i (x > d[i]): wykonuj d[i - h] d[i]; i i + h krok 9: d[i - h] x krok 10: h h div 3 krok 11: Zakończ algorytm
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.
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 |
---|
// 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.
// 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;
}
' 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 "
' 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:"
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
' 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:"
FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT
PRINT "Nacisnij Enter..."
SLEEP
END
<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 Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):
|
(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)
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) | |||
| tpp tpk | tnp 2tod |
- 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ą.
- 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.
- 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 |
|
|
|
|
|
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ć.
Dlaczego algorytm sortowania metodą Shella nie jest stabilny jeśli chodzi o zachowanie kolejności elementów równych w sortowanym zbiorze?
Wyjaśnij, dlaczego algorytm sortowania przez wstawianie szybciej sortuje zbiory uporządkowane od algorytmu sortowania metodą Shella.
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