Politechnika Zielonogórska Wydział Elektryczny	Marcin Gałkowski	Gr. lab. 27A	Nr ćwicz. 4	Ocena:
Laboratorium algorytmy i struktury danych.
Temat : Wybrane metody sortowania wewnętrznego.		Data wykonania 15-11-99	Data oddania 22-11-99	Sprawdz.

1. Sortowanie przez proste wstawianie.

Sortowanie przez proste wstawianie odbywa się w następujący sposób: dla każdego i = 2, 3, ..., n trzeba powtarzać wstawianie a[i] w już uporządkowaną część tablicy a[1] ≤ ... ≤ a[i-1]. W metodzie tej obiekty podzielone są umownie na dwa ciągi: ciąg wynikowy a₁...a_i-1 oraz ciąg źródłowy a_i...a_n. W każdym kroku począwszy od i=2 i zwiększając i o jeden, i-ty element ciągu źródłowego przenosi się do ciągu wynikowego, wstawiając go w odpowiednim miejscu.

1. Schemat blokowy sortowania przez proste wstawianie.

Nie Tak

2. Program w języku pascal.

program sortowanie_przez_proste_wstawianie;

uses crt,dos;

const n = 1000;

type tablica = array[0..n] of integer;

var plik : text;

T : tablica;

procedure zczytaj(var tab : tablica);

var i:integer;

begin

assign(plik,'tabin.txt');

reset(plik);

i:=1;

while not eof(plik) do

begin

readln(plik,tab[i]);

inc(i);

end;

close(plik);

clrscr;

for i:=1 to n do

begin

write(tab[i],', ');

delay(1);

end;

readln;

end;

procedure sortuj(var tab : tablica);

var i,x,j:integer;

przest,por : word;

h1,m1,s1,set1,h2,m2,s2,set2:word;

begin

clrscr;

write('Sortowanie...');

gettime(h1,m1,s1,set1);

przest:=0; por:=0;

for i:=2 to n do

begin

x:=tab[i];

tab[0]:=x;

j:=i-1;

while x<tab[j] do

begin

inc(por);

tab[j+1]:=tab[j];

inc(przest);

j:=j-1;

end;

tab[j+1]:=x;

inc(por);

end;

gettime(h2,m2,s2,set2);

writeln('OK');

writeln('Czas sortowania : ');

writeln('>> Czas rozpoczecia : ',h1,':',m1,':',s1,',',set1);

writeln('>> Czas konca : ',h2,':',m2,':',s2,',',set2);

writeln('Ilosc porownan : ',por);

writeln('Ilosc przestawien : ',przest);

readln;

end;

procedure zapisz(tab : tablica);

var i : integer;

plikout : text;

begin

clrscr;

assign(plikout,'tabout.txt');

rewrite(plikout);

for i:=1 to n do

begin

writeln(plikout,tab[i]);

write(tab[i],', ');

delay(1);

end;

close(plikout);

readln;

end;

BEGIN

zczytaj(T);

sortuj(T);

zapisz(T);

END.

2. Sortowanie przez proste wybieranie.

Sortowanie przez proste wybieranie polega na wyznaczeniu najmniejszego elementu w ciągu; zamianie go z pierwszym elementem w ciągu, wyznaczeniu najmniejszego elementu w a[2,n] i zamianie go z drugim elementem: wyznaczeniu najmniejszego elementu w a[3,n] i zamianie go z trzecim elementem itd. aż do posortowania całkowitego ciągu.

1. Schemat blokowy sortowania przez proste wybieranie.

2.2. Program w języku pascal.

program sortowanie_przez_proste_wybieranie;

uses crt,dos;

const n = 1000;

type tablica = array[1..n] of integer;

var plik : text;

T : tablica;

procedure zczytaj(var tab : tablica);

var i:integer;

begin

assign(plik,'tabin.txt');

reset(plik);

i:=1;

while not eof(plik) do

begin

readln(plik,tab[i]);

inc(i);

end;

close(plik);

clrscr;

for i:=1 to n do

begin

write(tab[i],', ');

delay(1);

end;

readln;

end;

procedure sortuj(var tab : tablica);

var i,k,x,j:integer;

h1,m1,s1,set1,h2,m2,s2,set2:word;

przest,por : word;

begin

clrscr;

write('Sortowanie...');

gettime(h1,m1,s1,set1);

przest:=0; por:=0;

for i:=1 to n-1 do

begin

k:=i;

x:=tab[i];

for j:=i+1 to n do

if tab[j]<x then

begin

inc(por);

k:=j;

x:=tab[j];

end;

inc(por);

inc(przest);

tab[k]:=tab[i];

tab[i]:=x;

end;

gettime(h2,m2,s2,set2);

writeln('OK');

writeln('Czas sortowania : ');

writeln('>> Czas rozpoczecia : ',h1,':',m1,':',s1,',',set1);

writeln('>> Czas konca : ',h2,':',m2,':',s2,',',set2);

writeln('Ilosc porownan : ',por);

writeln('Ilosc przestawien : ',przest);

readln;

end;

procedure zapisz(tab : tablica);

var i : integer;

plikout : text;

begin

clrscr;

assign(plikout,'tabout.txt');

rewrite(plikout);

for i:=1 to n do

begin

writeln(plikout,tab[i]);

write(tab[i],', ');

delay(1);

end;

close(plikout);

readln;

end;

BEGIN

zczytaj(T);

sortuj(T);

zapisz(T);

END.

3. Sortowanie bąbelkowe.

Sortowanie bąbelkowe polega na przeglądaniu od końca sortowanej tablicy i zamianie miejscami elementów jeśli są one w kolejności odwrotnej tj. pierwszy jest mniejszy od drugiego. Po zakończeniu pierwszego przejścia element najmniejszy powinien się znajdować na odpowiednim dla niego miejscu czyli na początku tablicy.

1. Schemat blokowy sortowania bąbelkowego.

Nie

Tak

Nie

Tak Nie

Tak

2. Program w języku pascal.

program sortowanie_babelkowe;

uses crt,dos;

const n = 1000;

type tablica = array[1..n] of integer;

var plik : text;

T : tablica;

procedure zczytaj(var tab : tablica);

var i:integer;

begin

assign(plik,'tabin.txt');

reset(plik);

i:=1;

while not eof(plik) do

begin

readln(plik,tab[i]);

inc(i);

end;

close(plik);

clrscr;

for i:=1 to n do

begin

write(tab[i],', ');

delay(1);

end;

readln;

end;

procedure sortuj(var tab : tablica);

var i,j,bufor:integer;

h1,m1,s1,set1,h2,m2,s2,set2:word;

przest,por : word;

begin

clrscr;

write('Sortowanie...');

gettime(h1,m1,s1,set1);

przest:=0; por:=0;

for i:=1 to n-1 do

begin

for j:=n downto 2 do

begin

if tab[j]<tab[j-1] then

begin

bufor:=tab[j-1];

tab[j-1]:=tab[j];

tab[j]:=bufor;

inc(przest);

end;

inc(por);

end;

end;

gettime(h2,m2,s2,set2);

writeln('OK');

writeln('Czas sortowania : ');

writeln('>> Czas rozpoczecia : ',h1,':',m1,':',s1,',',set1);

writeln('>> Czas konca : ',h2,':',m2,':',s2,',',set2);

writeln('Ilosc porownan : ',por);

writeln('Ilosc przestawien : ',przest);

readln;

end;

procedure zapisz(tab : tablica);

var i : integer;

plikout : text;

begin

clrscr;

assign(plikout,'tabout.txt');

rewrite(plikout);

for i:=1 to n do

begin

writeln(plikout,tab[i]);

write(tab[i],', ');

delay(1);

end;

close(plikout);

readln;

end;

BEGIN

zczytaj(T);

sortuj(T);

zapisz(T);

END.

4. Sortowanie szybkie ( Quick Sort ).

Jest to metoda, w której stosuje się zasadę zamiany. W metodzie sortowania szybkiego korzysta się z faktu, że w celu zapewnienia efektywności powinno się wymieniać obiekty położone daleko od siebie. Załóżmy że dane jest n obiektów ustawionych w odwrotnym porządku kluczy. Można posortować je wykonując tylko n/2 wymian, biorąc najpierw obiekty - skrajny z lewej strony i skrajny z prawej strony, a następnie posuwać się stopniowo do środka z obu stron. Oczywiście takie postępowanie możliwe jest tylko dlatego, że uporządkowanie było dokładnie odwrotne.

1. Schemat blokowy sortowania szybkiego.

Tak

Nie

Nie

Tak

Nie

Tak

4.2. Program w języku pascal.

program sortowanie_QUICKSORT;

uses crt,dos;

const n = 1000;

type tablica = array[1..n] of integer;

var plik : text;

T : tablica;

procedure zczytaj(var tab:tablica);

var i:integer;

begin

assign(plik,'tabin.txt');

reset(plik);

i:=1;

while not eof(plik) do

begin

readln(plik,tab[i]);

inc(i);

end;

close(plik);

clrscr;

for i:=1 to n do

begin

write(tab[i],', ');

delay(1);

end;

readln;

end;

procedure sort(var tab : tablica);

var h1,m1,s1,set1,h2,m2,s2,set2:word;

przest,por : word;

procedure sortuj(min,max:integer);

var j,i,pomoc,buf:integer;

begin

pomoc:=tab[(min+max) div 2];

i:=min;

j:=max;

repeat

while tab[i]<pomoc do begin inc(i); inc(por); end;

while tab[j]>pomoc do begin dec(j); inc(por); end;

if i<=j then

begin

buf:=tab[i];

tab[i]:=tab[j];

tab[j]:=buf;

inc(przest);

inc(i);

dec(j);

end;

until i>j;

if min<j then sortuj(min,j);

if i<max then sortuj(i,max);

end;

begin

clrscr;

write('Sortowanie...');

przest:=0; por:=0;

gettime(h1,m1,s1,set1);

sortuj(1,n);

gettime(h2,m2,s2,set2);

writeln('OK');

writeln('Czas sortowania : ');

writeln('>> Czas rozpoczecia : ',h1,':',m1,':',s1,',',set1);

writeln('>> Czas konca : ',h2,':',m2,':',s2,',',set2);

writeln('Ilosc porownan : ',por);

writeln('Ilosc przestawien : ',przest);

readln;

end;

procedure zapisz(tab : tablica);

var i : integer;

plikout : text;

begin

clrscr;

assign(plikout,'tabout.txt');

rewrite(plikout);

for i:=1 to n do

begin

writeln(plikout,tab[i]);

write(tab[i],', ');

delay(1);

end;

close(plikout);

readln;

end;

BEGIN

zczytaj(T);

sort(T);

zapisz(T);

END.

5. Wnioski.

SORTOWANIE	CZAS SORTOWANIA	ILOŚĆ PORÓWNAŃ	ILOŚĆ PRZESTAWIEŃ
Bombelkowe	2.04 sekundy	15569	43770
Quick-sort	0.06 sekundy	30916	8791
Przez wstawianie	0.49 sekundy	46749	43770
Przez wybieranie	0.44 sekundy	23045	2999

Metoda sortowania przez proste wstawianie nie wydaje się być metodą która sprawdza się dobrze w maszynach cyfrowych - wstawianie elementu i następnie przesuwanie całego wiersza elementów o jedną pozycję jest bardzo nieekonomiczne, a do tego wolne w swoim działaniu.

Liczba porównań P kluczy w i-tym przesiewaniu wynosi co najwyżej i-1, co najmniej 1 oraz ( przy założeniu że wszystkie permutacje n kluczy są równie prawdopodobne ) średnio i/2. Liczba podstawień elementów wynosi P+2. Liczby porównań i podstawień są najmniejsze wtedy, gdy elementy są uporządkowane już w ciągu źródłowym, największe zaś, gdy początkowo ustawione są w odwrotnej kolejności. W tym sensie sortowanie przez proste wstawianie wykazuje działanie naturalne.

Lepszych wyników będzie można się jednak spodziewać po metodach, w których przemieszcza się pojedyncze obiekty na większą odległość. Tak mniej więcej wygląda zasada działania metody sortowania przez proste wybieranie.

W algorytmie tym liczba porównań kluczy nie zależy od początkowego ustawienia tych kluczy. Z tego względu można uznać działanie tej metody za mniej naturalne niż prostego wstawiania.

Algorytm prostego wybierania jest przeważnie lepszy od prostego wstawiania, lecz w przypadkach , w których klucze są już posortowane lub prawie posortowane - proste wstawianie jest jednak nieco szybsze.

Metoda sortowania bąbelkowego ze względu na sprawność jest jednym z gorszych algorytmów, jednak jest on i tak „stosunkowo” lepszy od dwóch przedstawionych powyżej

Metoda szybkiego sortowania ( quick sort ) jest najszybszą metodą przedstawioną tutaj.

Jednakże i metoda sortowania szybkiego ma swoje słabe strony. Tak jak wszystkie nowoczesne metody sortowania niezbyt dobrze działa dla małych wartości.

Jej przewaga nad pozostałymi metodami polega na możliwości łatwego wstawiania prostej metody sortowania działającej na małych podziałach. Decydującym krokiem w tym sortowaniu jest wybór ograniczenia - gdyż przy wyborze za każdym razem największej wartości z podziału jako ograniczenia, w rezultacie dokonuje się n podziałów zamiast log n, co daje efektywność w najgorszym przypadku jest rzędu n². Metoda ta również nie jest zachęcająca dla zadań trywialnych, gdy tablica jest początkowo uporządkowana.

START

Wprowadź dane do tablicy źródłowej.

Utwórz tablicę wynikową.

Ustaw na początku tablicy źródłowej.

Wszystkie elementy z tablicy źródłowej pobrane.

Wstaw element tablicy źródłowej do tablicy wynikowej w odpowiednie miejsce.

Przesuń na następny

element tablicy

źródłowej.

STOP

START

Wprowadź dane

do tablicy.

Szukaj elementu minimalnego.

Element minimalny na początek tablicy.

Zmniejsz ciąg o jeden.

Przesuń na następny element tablicy źródłowej.

Czy koniec tablicy

( brak elementów ).

STOP

START

Wprowadź dane

do tablicy.

Idź do ostatniego elementu tablicy.

Porównaj kolejne elementy występujące po sobie.

Zamień elementy miejscami.

Kolejność właściwa

Idź do następnego elementu.

STOP

Początek tablicy.

Tablica posortowana

Wyświetl posortowaną tablicę.

START

Wprowadź dane

do tablicy.

Wybierz środkowy element tablicy.

Na „prawo” liczby większe,

na „lewo” liczby mniejsze.

Skrajne el. dobrze ustawione.

Wybierz środkowy element każdego z podciągów.

Zamień te elementy.

Tablica posortowana

Koniec tablicy?

Wyświetl posortowaną tablicę.

STOP

---