Laboratorium :Algorytmy i struktury danych. |
|||
Temat: |
Wybrane metody sortowania wewnętrznego |
||
Wykonał: |
Mariusz Daszkiewicz
|
Data:99-12-13 Gr.27 |
Ocena: |
Cel ćwiczenia:
Ćwiczenie ma na celu zapoznanie z metodami sortowania: sortowanie stogowe, sortowanie przez scalanie.
2.1: Sortowanie stogowe:
Definicja stogu: Ciąg kluczy: h1, hi+1, ... , hp takich, że hi h2i, hi h2i+1 dla wszystkich
i - l ... p/2.
W celu posortowania elementów stogu, trzeba wykonać n kroków przesiewania, w każdym kroku należy zdjąć ze stogu jego ostatni element, np. x, przechować wierzchołkowy element w zwolnionym przez x miejscu i przesiać x na właściwe miejsce. Do posortowania elementów potrzebnych jest n-1 kroków.
2.2: Procedury implementujące przesiewanie oraz sortowanie stogowe w języku pascal:
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;
pr:=0;po:=0;
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);
end;
2.3: Schemat blokowy sortowania:
3.1: Sortowanie przez scalanie
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.
3.2: Procedury implementujące sortowanie przez scalanie w języku pascal:
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;
3.3: Schemat blokowy sortowania:
4.Wnioski:
Oba typy sortowań okazały się bardziej złożone od sortowań z poprzedniego ćwiczenia zarówno pod względem złożoności algorytmów jak i ich implementacji. Jednocześnie czas wykonywania tych algorytmów jest znacznie dłuższy od wspomnianych wcześniej algorytmów. W metodzie sortowania stogowego za każdym razem następuje przesianie elementów stogu, co bardzo wydłuża czas sortowania. Podobnie jest z metodą sortowania przez scalanie, gdzie najpierw należy najpierw uporządkować sortowane ciągi metodą „dziel i zwyciężaj”. Metody z ćwiczenia poprzedniego są znacznie bardziej efektywne od poznanych obecnie metod.
Schematy blokowe