|
|
|
Ćwiczenie numer: 1 Data oddania ćwiczenia: Temat: Algorytmy sortowania. |
||
Treść zadania.
Celem tego ćwiczenia jest zbadanie efektywności różnych algorytmów sortowania dla różnych rozkładów wartości elementów w tablicach: losowych, stałych, rosnących, malejących, malejąco - rosnących (parzystych i nieparzystych) .
Algorytmy, które będą przedmiotem analizy to:
sortowanie bąbelkowe (buble sort)
sortowanie szybkie (quick sort)
sortowanie kopcowe (heap sort)
- sortowanie proste wstawianie (insert sort).
- sortowanie proste wybieranie (selection sort)
sortowanie metodą malejących przyrostów (Shell sort)
W tym ćwiczeniu zajmę się dokładną analizą i badaniami następujących metod:
sortowanie bąbelkowe (buble sort)
sortowanie szybkie (quick sort)
sortowanie kopcowe (heap sort)
- sortowanie proste wstawianie (insert sort).
Omówienie poszczególnych algorytmów sortowania.
Sortowaniem nazywamy proces ustawienia zbioru obiektów w określonym porządku. Sortowanie stosuje się w celu ułatwienia późniejszego wyszukiwania elementów.
Jednym z najważniejszych wymagań przy sortowaniu tablic jest oszczędne korzystanie z pamięci komputera i szybkość sortowania, a także ważna jest liczba porównań i przesunięć. Efektywne algorytmy wymagają porównań rzędu n log n (n - liczba sortowanych elementów -w tym przypadku liczb), natomiast proste algorytmy wymagają liczby porównań rzędu n2.
Sortowanie bąbelkowe (bubble sort).
Jest algorytmem, którego chyba jedyna zaleta jest to, że charakteryzuje się dużą prostotą zapisu. Można go porównać do pęcherzyków powietrza w wodzie, które jako lżejsze unoszą się w górę. Tablica jest zawsze sprawdzana od dołu w górę, w której poprzez zamianę sąsiadujących ze sobą elementów najmniejsze elementy tablicy wędrują na jej początek (górę). W pierwszym przebiegu są sprawdzane indeksy tablicy od i do n w następnym już od i+1 do n i tak dalej. Wadą tego algorytmu jest to, że za jednym przebiegiem małej pętli posortowana zostaje tylko jedna liczba.
Przykład:
Etapy sortowania |
|||||||||
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
|
|
|
||||||
|
1 |
|
50 |
1 |
1 |
1 |
1 |
1 |
1 |
|
2 |
|
5 |
50 |
5 |
5 |
5 |
5 |
5 |
|
3 |
|
13 |
5 |
50 |
8 |
8 |
8 |
8 |
|
4 |
|
8 |
13 |
8 |
50 |
13 |
13 |
13 |
|
5 |
|
14 |
8 |
13 |
13 |
50 |
14 |
14 |
|
6 |
|
1 |
14 |
14 |
14 |
14 |
50 |
30 |
|
7 |
|
30 |
30 |
30 |
30 |
30 |
30 |
50 |
Jak widać na przykładzie algorytm ten bardzo wolno przemieszcza „ciężkie” elementy w dół (trzeba, aż 7 razy przejrzeć całą tablicę aby przenieść 50 z początku tablicy na koniec). Na podstawie tego przykładu można wysnuć wnioski, że algorytm ten w najgorszym przypadku może osiągnąć złożoność W(n)=O(n2).
Sortowanie szybkie (quick sort).
Algorytm ten jest najszybszym algorytmem ze wszystkich tutaj omawianych, jest on kilkadziesiąt razy szybszy od sortowania bąbelkowego. Działa on na zasadzie „dziel i zwyciężaj” tj. dzieli on tablicę na dwie części po lewej stronie elementy mniejsze od środkowego a po prawej większe. Następnie wywołuje rekurencyjnie siebie jeszcze raz dla lewej i prawej części. Element środkowy porównawczy może być wyznaczany losowo albo jako pierwszy element z tablicy, w tym ćwiczeniu wybierany jest element o indeksie równym (n div 2).
<x |
x |
>x |
l środek p |
||
Do przemiatania tablicy służą dwa indeksy i oraz j. Indeks i zwiększany jest o 1 aż do momentu gdy t[i]>=x a indeks j zmniejszany jest o 1 aż do momentu gdy t[j]<=x. Wówczas następuje zamiana elementów wskazywanych przez te indeksy dla i<j. Trwa to tak długo aż oba indeksy się spotkają, wówczas to zostanie wywołana procedura sortowania odpowiednio dla lewej lub prawej strony. Złożoność tego algorytmu wynosi W(n)=O(nlog2n).
Przykład :
7 |
14 |
20 |
19 |
50 |
10 |
5 |
1 |
6 |
42 |
3 |
31 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
3 |
6 |
1 |
5 |
|
50 |
19 |
20 |
42 |
14 |
31 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
20 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5 |
3 |
1 |
|
7 |
|
14 |
19 |
|
42 |
50 |
31 |
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
50 |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
|
5 |
|
|
|
|
|
31 |
42 |
|
|
sortowanie kopcowe (heap sort).
Sortowanie to polega na porządkowaniu kopca będącego drzewem binarnym, w węzłach którego znajdują się elementy reprezentowanego zbioru n. Kopiec jest uporządkowany wówczas, jeżeli węzeł x jest następnikiem węzła y, to element w węźle x jest nie większy niż w węźle y. Kopiec ma tą właściwość , że następnik węzła k ma wartość 2k lub 2k+1.
|
k/2 |
|
|
|
|
|
k |
|
|
|
|
2k |
|
2k+1 |
Algorytm ten składa się z dwóch procedur; jednej porządkującej kopiec a drugiej, która zamienia element ze szczytu kopca z ostatnim elementem kopca. Element na szczycie ma największą wartość i po uporządkowaniu
umieszczany jest na końcu tablicy a ostatni liść drzewa jest umieszczany w korzeniu drzewa (szczycie kopca) . Wówczas ponownie zostaje uruchomiana procedura porządkowania kopca ale o rozmiarze n-1, gdyż ostatni element jest już posortowany.
Przykład porządkowania kopca:
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
6 |
|
1 |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
3 |
4 |
|
|
|
11 |
|
|
|
|
Drzewo już uporządkowane wygląda następująco:
|
|
|
|
|
|
15 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
|
|
|
10 |
|
1 |
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
3 |
4 |
|
|
|
6 |
|
|
|
|
Następnie element 15 zamieniamy z 6 gdzie 15 jest już posortowane i nie będzie uczestniczyć w kolejnym porządkowaniu kopca. Trwa to tak długo, aż kopiec będzie zawierał same elementy puste.
Każdy z n kroków wymaga log2n porównań, stąd cały proces sortowania wymaga tylko rzędu n log n podstawowych operacji i n operacji potrzebnych algorytmowi na stworzenie drzewa.
Podsumowując - złożoność algorytmu nawet w najbardziej pesymistycznym przypadku będzie wynosić: W(n)=n log n.
d) sortowanie proste wstawianie (insert sort)
Metoda ta umożliwia posortowanie tablicy po jednorazowym jej przeczytaniu. Jeżeli jakiś element nie znajduje się na swoim miejscu, to wstawiamy go tam, gdzie powinien się znajdować, gdyby tablica była uporządkowana.
|
|
5 |
|
2 |
|
2 |
|
1 |
|
|
9 |
|
5 |
|
5 |
|
2 |
|
|
2 |
|
9 |
|
7 |
|
5 |
|
|
7 |
|
7 |
|
9 |
|
7 |
|
|
1 |
|
1 |
|
1 |
|
9 |
Łatwo można zauważyć, że liczba porównań wykonywanych w algorytmie jest proporcjonalna do liczby przestawień, czyli takich par, że t[i]>t[j] dla i=j. W przypadku, gdy tablica będzie posortowana, czyli liczba przestawień będzie równa zero, to pesymistyczna złożoność tego algorytmu będzie zależnością linową.
e) sortowanie proste wybieranie (selection sort)
Algorytm ten polega na wyszukiwaniu ze zbioru elementów o najmniejszej wartości i zamianie go miejscami z elementem, który znajduje się na pierwszej pozycji w zbiorze aktualnie badanym. Powtarzamy te operacje z pozostałymi n-1 obiektami, następnie z n-2, aż pozostanie tylko jeden obiekt największy.
W ten sposób otrzymany ciąg uporządkowany. Do właściwości szczególnych tego algorytmu należy to, że liczba koniecznych porównań nie zależy od początkowego ustawienia obiektów. Dla różnych ciągów o stałej długości liczba ta ma zatem tę samą wartość.
|
|
1 |
|
1 |
|
1 |
|
1 |
|
|
36 |
|
5 |
|
5 |
|
5 |
|
|
8 |
|
8 |
|
8 |
|
8 |
|
|
60 |
|
60 |
|
60 |
|
36 |
|
|
5 |
|
36 |
|
36 |
|
60 |
Analiza złożoności algorytmu jest następująca :
W(n)=(n-1)+(n-2)+(n-3)+...+1=n(n-1)/2 =1/2n2 -O(n)
f) sortowanie metodą malejących przyrostów (Shell sort)
Algorytm sortowania metodą Shella, przy kolejnym porządkowaniu tablicy, porównuje elementy oddalone od siebie o tak zwany przyrost. Podczas pierwszego przeglądania porównuje się z reguły pierwszy element z ostatnim (przyrost n), natomiast dla każdego następnego przyrost jest równy n/2. Ostatnia faza jest podobna do sortowania bąbelkowego, gdyż przyrost jest równy 1.
|
|
44 |
|
44 |
|
10 |
|
10 |
|
|
55 |
|
18 |
|
18 |
|
18 |
|
|
12 |
|
10 |
|
44 |
|
12 |
|
|
42 |
|
42 |
|
42 |
|
42 |
|
|
99 |
|
99 |
|
12 |
|
44 |
|
|
18 |
|
55 |
|
55 |
|
55 |
|
|
10 |
|
12 |
|
99 |
|
99 |
|
|
67 |
|
67 |
|
67 |
|
67 |
Złożoność tego algorytmu wynosi : W(n)=n1.2 , a wskazanie najlepszego podziału nadal nie jest rozwiązane.
Listing programu.
{$M,64000,0,64000}
{$R-,S-}
{kontrola przedziałów wylaczona, kontrola pojemnosci stosu wylaczona}
uses
crt,Dos;
const N=25000;
CONST WYS=0;
var
f:text;
KROK,ile,a,b,temp,max:integer;
koniec_,aa,ww,wybor,wybor2:byte;
end_:char;
g,m,s,ms:word;
nazwa:string;
Poczatek,koniec :LongInt;
t:array[1..N] of word;
czas1,czas2,czas_w_sek:real;
Function WlaczTimer :LongInt;
Var Reg :Registers;
Znacznik :Byte;
Begin
Znacznik:=0;
Reg.AH:=$83;
Reg.AL:=0;
Reg.CX:=$7FFF;
Reg.DX:=$FFFF;
Reg.BX:=Ofs(Znacznik);
Reg.ES:=Seg(Znacznik);
Intr($15,Reg);
WlaczTimer:=$7FFFFFFF;
End;
Function WylaczTimer :LongInt;
Var Reg :Registers;
Begin
WylaczTimer:=MemL[$0040:$009C];
Reg.AH:=$83;
Reg.AL:=1;
Intr($15,Reg);
End;
Function CzasWykonania :Real;
Var Czas :Real;
Begin
Czas:=(Poczatek-koniec);
CzasWykonania:=Czas;
End;
procedure Tablica_losowa;
var
K:integer;
begin
for k:=1 to N-ile do
T[k]:=random(65520);
end;
procedure Tablica_stala;
var
K:integer;
begin
for k:=1 to N-ile do
T[k]:=5; {dowolna liczba, ktora bedzie stala}
end;
procedure Tablica_malejaca;
var
K,a:integer;
begin
k:=n-ile;
for a:=1 to n-ile do
begin
T[a]:=k;
k:=k-1;
end;
end;
procedure Tablica_rosnaca;
var
K:integer;
begin
k:=n-ile;
for k:=1 to n-ile do
begin
T[k]:=k;
end;
end;
procedure Tablica_ros_mal2;
var
x,K,POLOWA:integer;
begin
polowa:=(n-ile) div 2;
x:=1;
for k:=polowa to n-ile do
begin
t[k]:=x;
x:=x+1;
end;
x:=0;
for k:=1 to polowa-1 do
begin
t[k]:=polowa-x;
x:=x+1;
end;
end;
procedure Tablica_ros_mal;
var
x,K,POLOWA:integer;
begin
polowa:=(n-ile) div 2;
x:=2;
for k:=polowa to n-ile do
begin
t[k]:=x;
x:=x+1;
end;
x:=-1;
for k:=1 to polowa-1 do
begin
t[k]:=polowa-x;
x:=x+1;
end;
end;
procedure wyswietl;
var k:integer;
begin
for k:=1 to n-ile do
write(' ',t[k]:2);
WRITELN;
end;
procedure bombelkowe;
begin
for a:=N-ile-1 downto 1 do
for b:=1 to a do
if t[b]>t[b+1] then
begin
temp:=t[b];
t[b]:=t[b+1];
t[b+1]:=temp;
end;
end;
procedure selectionsort;{proste wybieranie}
var
i,j,temp,min:integer;
begin
for i:=1 to n-ile-1 do
begin
min:=i;
for j:=i+1 to n do
if t[min]>t[j] then
begin
temp:=t[min]; t[min]:=t[j]; t[j]:=temp;
end;
end;
end;
procedure insertsort;{proste wstawianie}
var
i,j,temp:integer;
begin
for i:=1 to n-ile do
begin
j:=i;
temp:=t[j];
while ((j>1) and (temp<t[j-1])) do
begin
t[j]:=t[j-1];
j:=j-1;
end;
t[j]:=temp;
end;
end;
procedure quicksort(l,p:word);
var
i,j,srodek:word;
begin
srodek:=(l+p) div 2;
i:=l;j:=p;
repeat
while (t[i]<=t[srodek]) and (i<>srodek) do i:=i+1;
while (t[j]>=t[srodek]) and (j<>srodek) do j:=j-1;
if i<j then begin temp:=t[i];t[i]:=t[j];t[j]:=temp;end;
if i=srodek then srodek:=j else
if j=srodek then srodek:=i;
until j=i;
if i>l then Quicksort(l,i-1);
if j<p then Quicksort(i+1,p)
end;
procedure napraw(i:word); {do algorytmu Heap}
var
temp:integer;
begin
if(2*i)>max then exit;
if(2*i+1)>max then
begin
if (t[i]<t[2*i]) then
begin
temp:=t[i];t[i]:=t[2*i];t[2*i]:=temp;napraw(2*i);
end;
end
else
begin
if (t[i]<t[2*i]) or (t[i]<t[2*i+1]) then begin
if t[2*i]>t[2*i+1] then
begin
temp:=t[i];t[i]:=t[2*i];t[2*i]:=temp;napraw(2*i);
end
else
begin
temp:=t[i];t[i]:=t[2*i+1];t[2*i+1]:=temp;napraw(2*i+1);
end;
end
end;
end;
procedure Heapsort;
var
a,temp:integer;
begin
max:=n-ile;
for a:=max div 2 downto 1 do napraw(a);
repeat
temp:=t[1];t[1]:=t[max];t[max]:=temp;
max:=max-1;
napraw(1);
until max=1;
end;
{***************}
begin
repeat
randomize;
clrscr;
koniec_:=0;
ile:=n;
writeln('Programy sortujace');
writeln;
writeln('podaj nazwe pliku, do ktorego beda zapisywane wyniki:');
writeln('jesli enter to sort.txt');
readln(nazwa);
if nazwa=''then nazwa:='sort.txt';
writeln('Prosze wybrac rodzaj sortowania:');
writeln('1 - Bublesort');
writeln('2 - Quicksort');
writeln('3 - Heapsort');
writeln('4 - Selectionsort');
writeln('5 - Insertsort');
readln(wybor);
if wybor>5 then begin writeln('BLAD !!!'); halt end;
writeln ('Co ile zmieniac rozmiar tablicy?');
readln(krok);
if krok>n then begin writeln('BLAD !!!'); halt end;
assign(f,nazwa);
rewrite(f);
if wybor=1 then writeln(f,'Sortowanie bombelkowe');
if wybor=2 then writeln(f,'Sortowanie szybkie "quicksort"');
if wybor=3 then writeln(f,'Sortowanie kopcowe "heapsort"');
if wybor=4 then writeln(f,'Sortowanie przez proste wstawianie "selectionsort"');
if wybor=5 then writeln(f,'Sortowanie przez proste wybieranie "insertsort"');
writeln(f,'tablica losowa');
writeln('tablica losowa');
repeat
ile:=ile-krok;
tablica_losowa;
if wys=1 then wyswietl;
poczatek:= WlaczTimer;
case wybor of
1:bombelkowe;
2:quicksort(1,n-ile);
3:heapsort;
4:selectionsort;
5:insertsort;
end;
koniec:=wylaczTimer;
if wys=1 then wyswietl;
WRITELN;
writeln(f,n-ile:8,czaswykonania:10:0);
writeln('czas sortowania ',n-ile,' elementow wynosi: ',(czaswykonania/1000000):10:5);
until ((ile=0) or (koniec_=1));
ile:=n;
writeln(f,'tablica stala');
writeln('tablica stala');
repeat
ile:=ile-krok;
tablica_stala;
if wys=1 then wyswietl;
poczatek:= WlaczTimer;
case wybor of
1:bombelkowe;
2:quicksort(1,n-ile);
3:heapsort;
4:selectionsort;
5:insertsort;
end;
koniec:=wylaczTimer;
if wys=1 then wyswietl;
WRITELN;
writeln(f,n-ile:8,czaswykonania:10:0);
writeln('czas sortowania ',n-ile,' elementow wynosi: ',(czaswykonania/1000000):10:5);
until ((ile=0) or (koniec_=1));
ile:=n;
writeln(f,'tablica rosnaca');
writeln('tablica rosnaca');
repeat
ile:=ile-krok;
tablica_rosnaca;
if wys=1 then wyswietl;
poczatek:= WlaczTimer;
case wybor of
1:bombelkowe;
2:quicksort(1,n-ile);
3:heapsort;
4:selectionsort;
5:insertsort;
end;
koniec:=wylaczTimer;
if wys=1 then wyswietl;
WRITELN;
writeln(f,n-ile:8,czaswykonania:10:0);
writeln('czas sortowania ',n-ile,' elementow wynosi: ',(czaswykonania/1000000):10:5);
until ((ile=0) or (koniec_=1));
ile:=n;
writeln(f,'tablica malejaca');
writeln('tablica malejaca');
repeat
ile:=ile-krok;
tablica_malejaca;
if wys=1 then wyswietl;
poczatek:= WlaczTimer;
case wybor of
1:bombelkowe;
2:quicksort(1,n-ile);
3:heapsort;
4:selectionsort;
5:insertsort;
end;
koniec:=wylaczTimer;
if wys=1 then wyswietl;
WRITELN;
writeln(f,n-ile:8,czaswykonania:10:0);
writeln('czas sortowania ',n-ile,' elementow wynosi: ',(czaswykonania/1000000):10:5);
until ((ile=0) or (koniec_=1));
writeln(f,'tablica malejaco - rosnaca (parzysta)');
writeln('tablica malejaco - rosnaca( parzysta)');
ile:=n;
repeat
ile:=ile-krok;
tablica_ros_mal;
if wys=1 then wyswietl;
poczatek:= WlaczTimer;
case wybor of
1:bombelkowe;
2:quicksort(1,n-ile);
3:heapsort;
4:selectionsort;
5:insertsort;
end;
koniec:=wylaczTimer;
if wys=1 then wyswietl;
WRITELN;
writeln(f,n-ile:8,czaswykonania:10:0);
writeln('czas sortowania ',n-ile,' elementow wynosi: ',(czaswykonania/1000000):10:5);
until ((ile=0) or (koniec_=1));
writeln(f,'tablica malejaco - rosnaca (nieparzysta)');
writeln('tablica malejaco - rosnaca (nieparzysta)');
ile:=n;
repeat
ile:=ile-krok;
tablica_ros_mal2;
if wys=1 then wyswietl;
poczatek:= WlaczTimer;
case wybor of
1:bombelkowe;
2:quicksort(1,n-ile);
3:heapsort;
4:selectionsort;
5:insertsort;
end;
koniec:=wylaczTimer;
if wys=1 then wyswietl;
WRITELN;
writeln(f,n-ile:8,czaswykonania:10:0);
writeln('czas sortowania ',n-ile,' elementow wynosi: ',(czaswykonania/1000000):10:5);
until ((ile=0) or (koniec_=1));
close(f);
writeln('********KONIEC********');
writeln;
writeln('Czy jeszcze raz ? (domyslnie TAK)');
readln(end_);
if end_='' then end_:='t';
until ((end_='n') or (end_='N'));
end.
Wyniki eksperymentów.
SORTOWANIE BĄBELKOWE (BUBLESORT) |
|
|||||||
|
|
|
|
|
|
|
|
|
Tablica losowa |
Tablica stała |
Tablica rosnaca |
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.2159 |
|
1250 |
0.1299 |
|
1250 |
0.1299 |
|
2500 |
0.8656 |
|
2500 |
0.5159 |
|
2500 |
0.5159 |
|
3750 |
1.9491 |
|
3750 |
1.1597 |
|
3750 |
1.1607 |
|
5000 |
3.4752 |
|
5000 |
2.0722 |
|
5000 |
2.0712 |
|
6250 |
5.4761 |
|
6250 |
3.2651 |
|
6250 |
3.2642 |
|
7500 |
7.9000 |
|
7500 |
4.7297 |
|
7500 |
4.7297 |
|
8750 |
10.7753 |
|
8750 |
6.4609 |
|
8750 |
6.4619 |
|
10000 |
14.0893 |
|
10000 |
8.4589 |
|
10000 |
8.4598 |
|
11250 |
17.7941 |
|
11250 |
10.7236 |
|
11250 |
10.7236 |
|
12500 |
22.0861 |
|
12500 |
13.2540 |
|
12500 |
13.2540 |
|
13750 |
26.5998 |
|
13750 |
16.0521 |
|
13750 |
16.0521 |
|
15000 |
31.7144 |
|
15000 |
19.1160 |
|
15000 |
19.1160 |
|
16250 |
37.1172 |
|
16250 |
22.4466 |
|
16250 |
22.4466 |
|
17500 |
43.1121 |
|
17500 |
26.0419 |
|
17500 |
26.0419 |
|
18750 |
49.4821 |
|
18750 |
29.9060 |
|
18750 |
29.9050 |
|
20000 |
56.4325 |
|
20000 |
34.0348 |
|
20000 |
34.0348 |
|
21250 |
63.8753 |
|
21250 |
38.4303 |
|
21250 |
38.4303 |
|
22500 |
71.5662 |
|
22500 |
43.0925 |
|
22500 |
43.0925 |
|
23750 |
79.7730 |
|
23750 |
48.0205 |
|
23750 |
48.0205 |
|
25000 |
88.2456 |
|
25000 |
53.2162 |
|
25000 |
53.2152 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tablica malejąca |
Tablica malejąco rosnąca -parzysta -nieparzysta |
|
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.2833 |
|
1250 |
0.2061 |
|
1250 |
0.2061 |
|
2500 |
1.1333 |
|
2500 |
0.8246 |
|
2500 |
0.8246 |
|
3750 |
2.5519 |
|
3750 |
1.8553 |
|
3750 |
1.8563 |
|
5000 |
4.5460 |
|
5000 |
3.3081 |
|
5000 |
3.3081 |
|
6250 |
7.1253 |
|
6250 |
5.1937 |
|
6250 |
5.1928 |
|
7500 |
10.2859 |
|
7500 |
7.5043 |
|
7500 |
7.5043 |
|
8750 |
14.0209 |
|
8750 |
10.2370 |
|
8750 |
10.2370 |
|
10000 |
18.3305 |
|
10000 |
13.3908 |
|
10000 |
13.3898 |
|
11250 |
23.2145 |
|
11250 |
16.9646 |
|
11250 |
16.9656 |
|
12500 |
28.6740 |
|
12500 |
20.9596 |
|
12500 |
20.9596 |
|
13750 |
34.7079 |
|
13750 |
25.3756 |
|
13750 |
25.3756 |
|
15000 |
41.3154 |
|
15000 |
30.2118 |
|
15000 |
30.2118 |
|
16250 |
48.4973 |
|
16250 |
35.4680 |
|
16250 |
35.4680 |
|
17500 |
56.2547 |
|
17500 |
41.1444 |
|
17500 |
41.1454 |
|
18750 |
64.5875 |
|
18750 |
47.2419 |
|
18750 |
47.2419 |
|
20000 |
73.4938 |
|
20000 |
53.7614 |
|
20000 |
53.7604 |
|
21250 |
82.9747 |
|
21250 |
60.6991 |
|
21250 |
60.6991 |
|
22500 |
93.0309 |
|
22500 |
68.0578 |
|
22500 |
68.0578 |
|
23750 |
103.6607 |
|
23750 |
75.8377 |
|
23750 |
75.8377 |
|
25000 |
114.8649 |
|
25000 |
84.0376 |
|
25000 |
84.0376 |
|
SORTOWANIE SZYBKIE (QUICKSORT) |
||||||||
|
|
|
|
|
|
|
|
|
Tablica losowa |
Tablica stała |
Tablica rosnaca |
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.0059 |
|
1250 |
0.0029 |
|
1250 |
0.0029 |
|
2500 |
0.0117 |
|
2500 |
0.0068 |
|
2500 |
0.0059 |
|
3750 |
0.0195 |
|
3750 |
0.0088 |
|
3750 |
0.0098 |
|
5000 |
0.0254 |
|
5000 |
0.0117 |
|
5000 |
0.0127 |
|
6250 |
0.0332 |
|
6250 |
0.0156 |
|
6250 |
0.0156 |
|
7500 |
0.0401 |
|
7500 |
0.0186 |
|
7500 |
0.0186 |
|
8750 |
0.0479 |
|
8750 |
0.0215 |
|
8750 |
0.0215 |
|
10000 |
0.0528 |
|
10000 |
0.0254 |
|
10000 |
0.0254 |
|
11250 |
0.0625 |
|
11250 |
0.0293 |
|
11250 |
0.0293 |
|
12500 |
0.0713 |
|
12500 |
0.0322 |
|
12500 |
0.0322 |
|
13750 |
0.0772 |
|
13750 |
0.0352 |
|
13750 |
0.0361 |
|
15000 |
0.0850 |
|
15000 |
0.0391 |
|
15000 |
0.0391 |
|
16250 |
0.0948 |
|
16250 |
0.0420 |
|
16250 |
0.0420 |
|
17500 |
0.1036 |
|
17500 |
0.0459 |
|
17500 |
0.0459 |
|
18750 |
0.1065 |
|
18750 |
0.0489 |
|
18750 |
0.0489 |
|
20000 |
0.1192 |
|
20000 |
0.0518 |
|
20000 |
0.0528 |
|
21250 |
0.1241 |
|
21250 |
0.0557 |
|
21250 |
0.0557 |
|
22500 |
0.1329 |
|
22500 |
0.0596 |
|
22500 |
0.0596 |
|
23750 |
0.1407 |
|
23750 |
0.0635 |
|
23750 |
0.0635 |
|
25000 |
0.1466 |
|
25000 |
0.0664 |
|
25000 |
0.0674 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tablica malejąca |
Tablica malejąco rosnąca -parzysta -nieparzyste |
|
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.0039 |
|
1250 |
0.0088 |
|
1250 |
0.0078 |
|
2500 |
0.0068 |
|
2500 |
0.0186 |
|
2500 |
0.0166 |
|
3750 |
0.0098 |
|
3750 |
0.0391 |
|
3750 |
0.0283 |
|
5000 |
0.0137 |
|
5000 |
0.0401 |
|
5000 |
0.0508 |
|
6250 |
0.0176 |
|
6250 |
0.0537 |
|
6250 |
0.0479 |
|
7500 |
0.0215 |
|
7500 |
0.0694 |
|
7500 |
0.0616 |
|
8750 |
0.0234 |
|
8750 |
0.0879 |
|
8750 |
0.0811 |
|
10000 |
0.0283 |
|
10000 |
0.1925 |
|
10000 |
0.1036 |
|
11250 |
0.0322 |
|
11250 |
0.2110 |
|
11250 |
0.1231 |
|
12500 |
0.0352 |
|
12500 |
0.1231 |
|
12500 |
0.2462 |
|
13750 |
0.0391 |
|
13750 |
0.1251 |
|
13750 |
0.3273 |
|
15000 |
0.0420 |
|
15000 |
0.1593 |
|
15000 |
0.2648 |
|
16250 |
0.0459 |
|
16250 |
0.1651 |
|
16250 |
0.1495 |
|
17500 |
0.0508 |
|
17500 |
0.1739 |
|
17500 |
0.1690 |
|
18750 |
0.0537 |
|
18750 |
0.2237 |
|
18750 |
0.1759 |
|
20000 |
0.0576 |
|
20000 |
0.3634 |
|
20000 |
0.2081 |
|
21250 |
0.0616 |
|
21250 |
0.2443 |
|
21250 |
0.2228 |
|
22500 |
0.0655 |
|
22500 |
0.3068 |
|
22500 |
0.2306 |
|
23750 |
0.0703 |
|
23750 |
0.4269 |
|
23750 |
0.2579 |
|
25000 |
0.0743 |
|
25000 |
0.5393 |
|
25000 |
0.4895 |
|
SORTOWANIE KOPCOWE (HEAPSORT) |
||||||||
|
|
|
||||||
Tablica losowa |
Tablica stała |
Tablica rosnąca |
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.0215 |
|
1250 |
0.0029 |
|
1250 |
0.0225 |
|
2500 |
0.0459 |
|
2500 |
0.0049 |
|
2500 |
0.0489 |
|
3750 |
0.0723 |
|
3750 |
0.0068 |
|
3750 |
0.0762 |
|
5000 |
0.0997 |
|
5000 |
0.0088 |
|
5000 |
0.1055 |
|
6250 |
0.1290 |
|
6250 |
0.0117 |
|
6250 |
0.1358 |
|
7500 |
0.1573 |
|
7500 |
0.0137 |
|
7500 |
0.1651 |
|
8750 |
0.1876 |
|
8750 |
0.0166 |
|
8750 |
0.1964 |
|
10000 |
0.2179 |
|
10000 |
0.0186 |
|
10000 |
0.2286 |
|
11250 |
0.2491 |
|
11250 |
0.0205 |
|
11250 |
0.2609 |
|
12500 |
0.2804 |
|
12500 |
0.0234 |
|
12500 |
0.2931 |
|
13750 |
0.3117 |
|
13750 |
0.0244 |
|
13750 |
0.3244 |
|
15000 |
0.3429 |
|
15000 |
0.0274 |
|
15000 |
0.3566 |
|
16250 |
0.3752 |
|
16250 |
0.0293 |
|
16250 |
0.3879 |
|
17500 |
0.4074 |
|
17500 |
0.0313 |
|
17500 |
0.4221 |
|
18750 |
0.4397 |
|
18750 |
0.0342 |
|
18750 |
0.4563 |
|
20000 |
0.4729 |
|
20000 |
0.0361 |
|
20000 |
0.4905 |
|
21250 |
0.5061 |
|
21250 |
0.0381 |
|
21250 |
0.5256 |
|
22500 |
0.5403 |
|
22500 |
0.0401 |
|
22500 |
0.5588 |
|
23750 |
0.5735 |
|
23750 |
0.0420 |
|
23750 |
0.5930 |
|
25000 |
0.6067 |
|
25000 |
0.0440 |
|
25000 |
0.6272 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tablica malejąca |
Tablica malejąco rosnąca -parzysta -nieparzyste |
|
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.0195 |
|
1250 |
0.0195 |
|
1250 |
0.0195 |
|
2500 |
0.0430 |
|
2500 |
0.0430 |
|
2500 |
0.0430 |
|
3750 |
0.0674 |
|
3750 |
0.0694 |
|
3750 |
0.0694 |
|
5000 |
0.0948 |
|
5000 |
0.0948 |
|
5000 |
0.0948 |
|
6250 |
0.1221 |
|
6250 |
0.1211 |
|
6250 |
0.1202 |
|
7500 |
0.1485 |
|
7500 |
0.1495 |
|
7500 |
0.1505 |
|
8750 |
0.1768 |
|
8750 |
0.1759 |
|
8750 |
0.1759 |
|
10000 |
0.2061 |
|
10000 |
0.2061 |
|
10000 |
0.2052 |
|
11250 |
0.2345 |
|
11250 |
0.2325 |
|
11250 |
0.2325 |
|
12500 |
0.2628 |
|
12500 |
0.2618 |
|
12500 |
0.2628 |
|
13750 |
0.2941 |
|
13750 |
0.2960 |
|
13750 |
0.2951 |
|
15000 |
0.3244 |
|
15000 |
0.3253 |
|
15000 |
0.3253 |
|
16250 |
0.3537 |
|
16250 |
0.3537 |
|
16250 |
0.3537 |
|
17500 |
0.3840 |
|
17500 |
0.3830 |
|
17500 |
0.3830 |
|
18750 |
0.4152 |
|
18750 |
0.4133 |
|
18750 |
0.4133 |
|
20000 |
0.4475 |
|
20000 |
0.4455 |
|
20000 |
0.4455 |
|
21250 |
0.4778 |
|
21250 |
0.4748 |
|
21250 |
0.4748 |
|
22500 |
0.5100 |
|
22500 |
0.5032 |
|
22500 |
0.5032 |
|
23750 |
0.5393 |
|
23750 |
0.5334 |
|
23750 |
0.5334 |
|
25000 |
0.5745 |
|
25000 |
0.5667 |
|
25000 |
0.5667 |
|
SORTOWANIE PRZEZ PROSTE WSTAWIANIE |
||||||||
|
|
|
|
|
|
|
|
|
Tablica losowa |
Tablica stała |
Tablica rosnaca |
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.1319 |
|
1250 |
0.0020 |
|
1250 |
0.0010 |
|
2500 |
0.5207 |
|
2500 |
0.0020 |
|
2500 |
0.0020 |
|
3750 |
1.1656 |
|
3750 |
0.0020 |
|
3750 |
0.0029 |
|
5000 |
2.0331 |
|
5000 |
0.0029 |
|
5000 |
0.0029 |
|
6250 |
3.2094 |
|
6250 |
0.0039 |
|
6250 |
0.0039 |
|
7500 |
4.6984 |
|
7500 |
0.0039 |
|
7500 |
0.0039 |
|
8750 |
6.3739 |
|
8750 |
0.0039 |
|
8750 |
0.0039 |
|
10000 |
8.2830 |
|
10000 |
0.0039 |
|
10000 |
0.0039 |
|
11250 |
10.4334 |
|
11250 |
0.0049 |
|
11250 |
0.0049 |
|
12500 |
12.9013 |
|
12500 |
0.0059 |
|
12500 |
0.0059 |
|
13750 |
15.7873 |
|
13750 |
0.0059 |
|
13750 |
0.0059 |
|
15000 |
18.6021 |
|
15000 |
0.0059 |
|
15000 |
0.0068 |
|
16250 |
22.1730 |
|
16250 |
0.0068 |
|
16250 |
0.0068 |
|
17500 |
25.4489 |
|
17500 |
0.0078 |
|
17500 |
0.0068 |
|
18750 |
29.1771 |
|
18750 |
0.0078 |
|
18750 |
0.0078 |
|
20000 |
33.1809 |
|
20000 |
0.0078 |
|
20000 |
0.0078 |
|
21250 |
37.5285 |
|
21250 |
0.0088 |
|
21250 |
0.0078 |
|
22500 |
42.1224 |
|
22500 |
0.0088 |
|
22500 |
0.0088 |
|
23750 |
46.9673 |
|
23750 |
0.0088 |
|
23750 |
0.0098 |
|
25000 |
52.1073 |
|
25000 |
0.0098 |
|
25000 |
0.0098 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Tablica malejąca |
Tablica malejąco rosnąca -parzysta -nieparzyste |
|
||||||
Liczba elem. Czas |
|
Liczba elem. Czas |
|
Liczba elem. Czas |
|
|||
1250 |
0.2188 |
|
1250 |
0.1104 |
|
1250 |
0.1094 |
|
2500 |
0.8705 |
|
2500 |
0.4357 |
|
2500 |
0.4357 |
|
3750 |
1.9608 |
|
3750 |
0.9790 |
|
3750 |
0.9790 |
|
5000 |
3.4908 |
|
5000 |
1.7410 |
|
5000 |
1.7400 |
|
6250 |
5.4751 |
|
6250 |
2.7209 |
|
6250 |
2.7209 |
|
7500 |
7.9039 |
|
7500 |
3.9197 |
|
7500 |
3.9197 |
|
8750 |
10.7763 |
|
8750 |
5.3374 |
|
8750 |
5.3374 |
|
10000 |
14.0883 |
|
10000 |
6.9807 |
|
10000 |
6.9807 |
|
11250 |
17.8449 |
|
11250 |
8.8516 |
|
11250 |
8.8516 |
|
12500 |
22.0411 |
|
12500 |
10.9492 |
|
12500 |
10.9483 |
|
13750 |
26.6799 |
|
13750 |
13.2677 |
|
13750 |
13.2677 |
|
15000 |
31.7603 |
|
15000 |
15.8079 |
|
15000 |
15.8079 |
|
16250 |
37.2823 |
|
16250 |
18.5689 |
|
16250 |
18.5698 |
|
17500 |
43.2479 |
|
17500 |
21.5507 |
|
17500 |
21.5516 |
|
18750 |
49.6521 |
|
18750 |
24.7542 |
|
18750 |
24.7542 |
|
20000 |
56.4999 |
|
20000 |
28.1786 |
|
20000 |
28.1777 |
|
21250 |
63.7903 |
|
21250 |
31.8228 |
|
21250 |
31.8228 |
|
22500 |
71.5203 |
|
22500 |
35.6888 |
|
22500 |
35.6888 |
|
23750 |
79.6939 |
|
23750 |
39.7756 |
|
23750 |
39.7746 |
|
25000 |
88.3081 |
|
25000 |
44.0832 |
|
25000 |
44.0822 |
|
5. Wyniki eksperymentów.
Przeprowadziłem badania następujących metod:
Metoda sortowania przez wstawianie (insert sort)
Metoda sortowania przez prostą zamianę tzw. Sortowanie bąbelkowe (bubble sort)
Metoda sortowania szybkiego (quick sort)
Metoda sortowania kopcowego (heap sort)
Sortowane elementy w tablicach miały różny rozkład wartości tj. :
Losowy
Stały
Rosnący
Malejący
Rosnąco - malejący o środkowym elemencie parzystym i nieparzysty
Po wykonaniu szeregu długich, wyczerpujących pomiarów i obliczeń chciałbym przedstawić pokrótce swoje spostrzeżenia dotyczące każdego z tych algorytmów.
Sortowanie przez proste wstawianie (insert sort).
Algorytm sortowania przez proste wstawianie jest algorytmem klasy O(n2) co zalicza go do algorytmów raczej dość wolnych. Nie nadaje się on do sortowania dużych tablic a raczej do małych, gdzie zależy programiście na algorytmie prostym i przejrzystym. Zależność liczby elementów a czasu sortowania ma charakter wykładniczy wyjątkiem tutaj jest tablica o rozkładzie elementów rosnącym (tablica już uporządkowana) i tablica o rozkładzie o stałym elementów (w przypadku mojego programu same „5”). W obu tych przypadkach algorytm ten nie miał sobie równych był po prostu najszybszy (pobił również quick sorta !). Spowodowane to jest tym, że algorytm ten szuka w ciągu liczb posortowanych miejsca do wstawienia liczby z zbioru liczb nieposortowanych. W tych przypadkach po sprawdzeniu tablicy i stwierdzeniu, że jest ona już posortowana insert sort kończy pracę.
Najgorszym przypadkiem jest tablica odwrotnie uporządkowana, gdyż algorytm musi przemieścić wszystkie elementy wówczas liczba porównań wynosi:
Pomax=1/2(n2+n)-1 a liczba przesunięć Prmax=1/2(n2+3n-4).
Przypadkiem średnim jest tablica o losowym rozkładzie elementów wówczas liczba porównań wynosi:
Pośr=1/4(n2+n-2) a liczba przesunięć Prśr=1/4(n2+9n-10).
Przypadkiem najlepszym jest tablica o stałym lub rosnącym rozkładzie elementów wówczas liczba porównań wynosi:
Pomin=n-1 a liczba przesunięć Prmin=2(n-1).
Reasumując metoda sortowania przez wstawianie jest algorytmem raczej wolnym ale wyśmienicie się nadaje wszędzie tam gdzie mamy doczynienia z tablicami już posortowanymi lub prawie posortowanymi i takimi gdzie elementy występujące w tablicy bardzo często się powtarzają. Jeśli będziemy sortować małe tablice i zależy nam na prostocie to algorytm insert sort jest idealny.
Sortowanie bąbelkowe.
Podobnie jak insert sort algorytm sortowania bąbelkowego charakteryzuje się prostotą budowy, tym co różni go zasadniczo od poprzednika jest to, że przy każdym rozkładzie elementów w tablicy jest on zabójczo wolny! Jest on również algorytmem klasy O(n2).
Do wad tego algorytmu można zaliczyć:
„puste przejścia” - nie jest dokonywana żadna wymiana bo tablica jest już posortowana.
Wrażliwość na konfigurację danych np.: jeżeli tablica będzie już prawie uporządkowana ale zamiast elementu o najmniejszej wartości na początku tablicy znajduje się element największy a reszta jest już na swoim miejscu to element za każdym krokiem pętli przesunie się o 1 co przy tablicy 25000 elementów oznacza 25000 przesunięć!
Duża ilość iteracji, a co za tym się wiąże duża złożoność obliczeniowa.
Do zalet można zaliczyć:
Bardzo prosta budowa wręcz śmiesznie prosta.
Metoda nie wymaga dużo czasu na wykonanie pojedynczego przejścia, co w pewnym sensie rekompensuje straty podczas wielu iteracji.
Liczba porównań w tym algorytmie wynosi : Po=1/2(n2-n) dla wszystkich przypadków.
Natomiast najmniejsza liczba przesunięć Prmin=0 dotyczy tablic o rozkładzie rosnącym i stałym. Średnia liczba przesunięć Prśr=3/4(n2-n) dotyczy tablic o rozkładzie losowym i rosnąco malejącym. Maksymalna liczba przesunięć Prmax=3/2(n2-n), dotyczy tablicy o rozkładzie malejącym (odwrotnie uporządkowanym).
Sortowanie szybkie (quick sort).
Sortowanie to jest najbardziej efektywną metodą ze wszystkich tutaj omówionych, w większości tablic nie miało sobie równych. Jest wiele sposobów implementacji tej metody. W mojej metodzie tablica dzielona jest wówczas, gdy indeksy i oraz j spotkają się co trochę przyspieszyło działanie tego algorytmu oraz wyeliminowało problem zawieszania się komputera przy sortowaniu tablicy o malejąco - rosnącym rozmieszczeniu elementów. Z moich obserwacji zawieszanie to było spowodowane przejściem któregoś z indeksów za tablicę i modyfikację np.: kodu programu umieszczonego w pamięci. Algorytm ten chociaż jest taki szybki to odbiega od ideału, gdyż :
Niezbyt szybko jak tego można byłoby się spodziewać działa dla małych n - związane jest to z jego bardziej zawiłą implementacją
Koszt w przypadku najgorszym wynosi O(n2)
Prawie wykładnicza charakterystyka t=f(n) przy malejąco - rosnącym rozmieszczeniu elementów w tablicy
Pewną wadą też jest użycie rekursji, która jest tłumaczona na operacje na stosie. W złożoności pamięciowej musimy uwzględnić również pamięć potrzebną na obsługę stosu. Jeżeli chodzi o przypadek pesymistyczny, głębokość rekursji wynosi n-1, a zatem S(n)=O(n). Aby algorytm działał prawidłowo w kompilatorze trzeba było ustawić wartość stosu na max czyli 65 kb.
Zaletą tego algorytmu jest szybkości jeszcze raz szybkość przy dużych n.
Bardzo intersującym zjawiskiem jest przesunięcie „pików” jakie występuje pomiędzy dwoma sortowanymi tablicami o rozmieszczeniu malejąco - rosnącym elementów. Spowodowane to jest przesuniętym trafianiem w najgorszy przypadek dla tych tablic. Każdy taki pik przedstawia sytuację, w której tablica prawie każdorazowa zostaje podzielona w stosunki 1 : n-1 wówczas trzeba wykonać n podziałów i stąd efektywność wynosi n2
Jeżeli jako element środkową utrafimy element o wartości środkowej to tablica zastanie podzielona na dwie równe części a liczba wymian elementów będzie wynosiła n/6 i wówczas liczba przejść potrzebnych do posortowania tablicy będzie wynosić n log n a całkowita liczba wymian w całym procesie sortowania będzie równa n/6 log n. Taka sytuacja to przypadek najlepszy.
W rzeczywistości szansa na jej trafienie jest równa jak 1/n. Efektywność średnia wynosi n log n.
Sortowanie kopcowe (heap sort)
Na pierwszy rzut oka analizując kod algorytmu metoda ta sprawia wrażenie dość zawiłej i niezbyt szybkiej jednak jest inaczej. Może nie jest to metoda szybsza od quick sorta ale przebija inne metody takie jak metody klasy O(n2) oraz Shella. Zadziwiająca w tej metodzie jest odporność algorytmu na sposób rozmieszczenia elementów w tablicy prawie wszystkie charakterystyki niemal się pokrywają (wykres strona 22). Wyjątkiem są tablice posortowane, gdzie przebija prędkościowa quick sorta. Dwu trzy krotnie gorzej wypada w tablicach z rozmieszczeniem losowym i malejącym ale przy rozmieszczeniu malejąco - rosnącym „depcze quick sortowi po piętach” . Sama procedura heapsort w tym algorytmie za wiele nie robi, głównym czynnikiem sortującym jest porządkowanie kopca (w programie nazywa się ona napraw) . Procedura heapsort jedynie umieszcza już posortowane elementy na swoim miejscu w tablicy i steruje dalszym sortowaniem.
Uważam, że algorytm ten jest godnym uwagi programisty bo efektywnością jest zbliżony do quick sorta a jednocześnie czas sortowanie nie zależy w tak dużym stopniu od rodzaju rozmieszczenia elementów w tablicy i nie robi takich niespodzianek jak quicksort w postaci pików i prawie wykładniczej charakterystyki w tablicach malejąco - rosnących.
Średnia ilość przesunięć jest dość trudna do określenia ale w przybliżeniu wynosi : ½ n log n. Podsumowując - złożoność algorytmu nawet w najbardziej pesymistycznym przypadku będzie wynosić: W(n)=n log n.
Reasumując - mając do posortowania małe tablice to najlepszym rozwiązaniem jest sortowanie bąbelkowe, jeśli spodziewamy się tablicy już posortowanej to najlepszy będzie algorytm sortowania przez proste wstawianie. Sortując duże tablice o rozkładach losowych to najlepszy do tego będzie quick sort, a jeśli zależy nam na tym aby algorytm był mało wrażliwy na rodzaj sortowanej tablicy nawet w najbardziej pesymistycznym przypadku to idealny jest heap sort.
12
2
Wyszukiwarka
Podobne podstrony:
algorytmy sortowanie
kozik,projektowanie algorytmów,ALGORYTMY SORTOWANIA
Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących, ALGORYTMY
Algorytmy sortowania, programowanie
kilka programów, sort3, Sprawozdanie - Algorytmy sortowania
kilka programów, sorts, Sprawozdanie - Algorytmy sortowania
kilka programów, sorts1, Sprawozdanie - Algorytmy sortowania
algorytmy sortowanie
Algorytmy sortowania
Algorytmy sortowania
Algorytmy sortowania
Algorytm sortowania przez wybór w porządku rosnącym
Algorytmy i struktury danych 03 Algorytmy sortowania i przeszukiwania
Ściaga sortowania, algorytmy i struktury danych
ALS - 009-005 - Program Sortowanie INSERTION SORT, Informatyka - uczelnia, WWSI i WAT, wwsi, SEM II,
jak wykonac sortowanie przez zamiane wymiane wybor algorytm selection sort, PHP Skrypty
ALS - 009-000 - Zajęcia - Sortowanie bąbelkowe, Informatyka - uczelnia, WWSI i WAT, wwsi, SEM II, Al
jak wykonac sortowanie przez wstawianie algorytm inserion sort, PHP Skrypty
więcej podobnych podstron