Politechnika Zielonogórska Wydział Elektryczny |
Marcin Gałkowski |
Gr. lab.
27A |
Nr ćwicz. 5 |
Ocena:
|
Laboratorium algorytmy i struktury danych. |
||||
Temat :
Wybrane metody sortowania 2. |
Data wykonania 22-11-99 |
Data oddania 29-11-99 |
Sprawdz. |
|
Cel ćwiczenia:
Celem ćwiczenia jest zapoznanie się z wybranymi metodami sortowania. Badane w ćwiczeniu metody sortowania: stogowe oraz przez scalanie.
Wstęp:
Sortowanie stogowe - stóg jest definiowany jako ciąg kluczy takich, że dla wszystkich f-cja dla każdego elementu i=l..p/2. W swojej formie przypomina drzewo binarne.
Sortowanie przez scalanie - jest to scalanie dwóch ciągów uporządkowanych w jeden ciąg uporządkowany. Aby go uzyskać robimy następująco: patrzymy na początki danych ciągów i do tworzonego ciągu przenosimy mniejszy z elementów czołowych lub którykolwiek z ciągów z nich gdy są równe przy czym kolejność przenoszenia elementów z ciągów do ciągu uporządkowanego zależy od ich wartości, które mogą powodować, że jeden z ciągów będzie można znacznie prędzej przeniesiony niż drugi.
2.1. Schemat blokowy sortowania stogowego.
Nie
Tak
Nie
Tak
Tak
Nie
2.2. Schemat blokowy sortowania przez scalanie.
Nie
Tak
Nie
Tak
Nie
Tak
2.3. Program w języku Pascal dla obu sortowań:
program stogowe_i_scalanie;
uses crt,dos;
type p=file of integer;
const n=1000;
var plik:p;
po,pr:longint;
t,ran,i,a:integer;
wybor,z:char;
h,m,s,st,h1,m1,s1,st1:word;
Procedure przesiewanie(var plik:p;r,b:longint);
var ok:boolean;
war,war2,buf:integer;
mc:longint;
begin
ok:=false;
while (2*r<=b) and not ok do
begin
if 2*r=b then mc:=2*r
else
begin
seek(plik,2*r);
read(plik,war);
seek(plik,2*r+1);
read(plik,war2);
if war>war2 then mc:=2*r
else mc:=2*r+1;
inc(po);
end;
seek(plik,r);
read(plik,war);
seek(plik,mc);
read(plik,war2);
if war<war2 then
begin
inc(po);
seek(plik,r);
read(plik,buf);
seek(plik,mc);
read(plik,war2);
seek(plik,r);
write(plik,war2);
inc(pr);
seek(plik,mc);
write(plik,buf);
inc(pr);
r:=mc
end
else ok:=true
end;
end;
Procedure sortstogowe(var plik:p);
var war,war2,buf:integer;
x:char;
i:longint;
begin
clrscr;
writeln('Sortuje stogowo');
pr:=0;po:=0;
gettime(h,m,s,st);
reset(plik);
for i:=((n-1) div 2) downto 0 do
przesiewanie(plik,i,n-1);
for i:=(n-1) downto 1 do
begin
seek(plik,0);
read(plik,war);
buf:=war;inc(pr);
seek(plik,i);
read(plik,war2);
seek(plik,0);
write(plik,war2);
inc(pr);
seek(plik,i);
write(plik,buf);
inc(pr);
przesiewanie(plik,0,i-1)
end;
close(plik);
writeln('znow sie udalo');
writeln('wcisnij cokolwiek');
readkey;
end;
procedure wypelnij(var plik:p);
var i:longint;
st:string;
begin
clrscr;
write('Podaj nazwe pliku:');
readln(st);
assign(plik,st);
rewrite(plik);
for i:=1 to n do
begin
ran:=random(64000)-32000;
write(plik,ran);
end;
close(plik);
end;
procedure przesowanie(var plik:p;l,p:longint);
var buf,buf2:integer;
begin
if l<p then
begin
seek(plik,l);
read(plik,buf);
inc(l);
end else
begin
seek(plik,l);
read(plik,buf);
end;
while l<=p+1 do
begin
seek(plik,l);
read(plik,buf2);
seek(plik,l);
write(plik,buf);
inc(pr);
buf:=buf2;
inc(l);
end;
end;
procedure sort_scal(var plik:p;l1,p1,l2,p2:longint);
var d1,d2,i:longint;
el1,el2:integer;
begin
i:=l1;
d1:=p1-l1+1;
d2:=p2-l2+1;
while (d1>0) and (d2>0) do
begin
seek(plik,l1);
read(plik,el1);
seek(plik,l2);
read(plik,el2);
inc(po);
if el1<=el2 then
begin
inc(l1);
dec(d1);
inc(i);
end else
begin
przesowanie(plik,l1,p1);
seek(plik,l1);
write(plik,el2);
inc(pr);
dec(d2);
inc(i);
inc(l1);
inc(p1);
inc(l2);
end;
end;
end;
procedure podzial(var plik:p;l,p:longint);
var s:longint;
begin
s:=(l+p)div 2;
if (p-l)>0 then
begin
podzial(plik,l,s);
podzial(plik,s+1,p);
end;
sort_scal(plik,l,s,s+1,p);
end;
procedure scalanie(var plik:p);
var x:char;
begin
clrscr;
writeln('Trwa sortowanie prez scalanie (to moze potrwac)');
pr:=0;po:=0;
podzial(plik,0,n-1);
writeln('Posortowalo (znow sie udalo)');
writeln('wcisnij cokolwiek');
readkey;
end;
begin
randomize;
repeat
clrscr;
writeln('1 - tworzenie i wypelnianie pliku ');
writeln('2 - sortowanie stogowe ');
writeln('3 - sortowanie przez scalanie ');
writeln('4 - wyswietlenie tablicy ');
writeln('5 - wyjscie ');
writeln;
readln(wybor);
case wybor of
'1': wypelnij(plik);
'2': sortstogowe(plik);
'3': begin
reset(plik);
scalanie(plik);
close(plik);
end;
'4':begin
reset(plik);
for i:=1 to n do
begin
read(plik,a);
write(' ',a);
end;
readln;
close(plik);
end;
'5': exit;
end;
until wybor='5'
end.
Wnioski.
W przypadku sortowania stogowego, w każdym kroku dołączany jest nowy obiekt i ustawiany prawidłowo dzięki procesowi przesiewania. Jest to proces czasochłonny.
Algorytm sortowania stogowego tworzy drzewo uporządkowane binarne, scalając następnie poprzez jego zwinięcie, elementy poszczególnych rozgałęzień. Oba algorytmy są w ogóle czasochłonne dla elementów nieposortowanych. W przypadku sortowania poprzez scalanie można go stosować w przypadku tworzenia uporządkowanego ciągu z podciągów już uprzednio uporządkowanych. W algorytmie sortowania przez scalanie można go również stosować do sortowania podciągów i ciągów różnorodych w ogóle, tyle, że proces sortowania nie należy do najszybszych czasowo dla dużych ilości elementów ciągu.
Sortowanie przeprowadzono na plikach zawierających elementy typu integer:
- losowe
|
Sortowanie stogowe |
Sortowanie przez scalanie |
||
Liczba elementów |
550 |
5500 |
550 |
5500 |
Czas sortowania |
2.91 sec |
1 min 5.19 sec |
11.71 sec |
31 min 25.59 sec |
Liczba przestawień |
10747 |
143625 |
79174 |
7531124 |
Liczba porównań |
9266 |
129051 |
4352 |
61481 |
- uporządkowane
|
Sortowanie stogowe |
Sortowanie przez scalanie |
||
Liczba elementów |
550 |
5500 |
550 |
5500 |
Czas sortowania |
3.13 sec |
1 min 9.37 sec |
2.37 sec |
8.57 sec |
Liczba przestawień |
11393 |
152151 |
0 |
0 |
Liczba porównań |
9786 |
135839 |
2591 |
35756 |
Metoda sortowania przez scalanie okazała się szybsza w przypadku, gdy plik źródłowy był już posortowany. W pozostałych przypadkach sortowanie stogowe było znacznie szybsze. Jest to spowodowane tym, że w przypadku sortowania przez scalanie nie użyto pomocniczych plików ani innych struktur danych. Powoduje to znaczne zapotrzebowanie na moc obliczeniową procesora ( w przypadku wolnego procesora i dużego pliku zastosowanie tak zaimplementowanej metody jest mało efektywne ), pozwala jednak na wykonanie programu przy wykorzystania niewielkiej ilości pamięci elektronicznej oraz bez dodatkowej pamięci masowej.
START
Wprowadź tablicę z danymi.
Wypisz tablicę posortowaną.
Odznacz „środkowy” element tablicy.
Przesiewanie dla tego elementu skończone?
Przesiewaj od tego elementu zaczynając od mniejszego elementu w stogu - tablicy
( zamieniaj je miejscami ).
Idź do kolejnego elementu wymagającego przesiania.
STOP
START
Wpisz dwa ciągi wejściowe.
Podziel każdy ciąg na „pół”.
Podziel każdy podciąg na „pół”.
Scalaj elementy do ciągów w odpowiedniej kolejności.
Utwórz ciąg wyjściowy.
Brak elementów w podciągach.
STOP
Zostały elementy do przesiania?
Przesiewanie skończone?
Przesiewaj od tego elementu.
Brak elementów do scalania.
Przenieś najmniejsze elementy dwóch ciągów wejściowych do ciągu wyjściowego uporządkowanie.
Ciągi puste?
Pozostałe elementy ciągu wejściowego dopisz do końca ciągu wyjściowego.
Wypisz ciąg wyjściowy.
Wyszukiwarka