ĆWICZENIE 2

WYBRANE METODY SORTOWANIA WEWĘTRZNEGO

Sortowanie to proces polegający na ustawieniu elementów zbioru w określonej kolejności najczęściej od najmniejszego do największego (lub odwrotnie). Jest on stosowany w celu ułatwienia późniejszego wyszukiwania elementów. W wielu dziedzinach ta działalność jest podstawowa i w zasadzie jedyna. Przykłady to tworzenie katalogów bibliotecznych, książek telefonicznych itp. Istnieje wiele sposobów (algorytmów) sortowania. Wybór zależy od struktury przetwarzanych danych. Rozróżniamy metody sortowania tablic (metody wewnętrzne), ponieważ tablice przechowywane są najczęściej w wewnętrznej pamięci operacyjnej, metody sortowania plików (metody zewnętrzne) - pliki są najczęściej przechowywane w wolniejszych lecz bardziej pojemnych pamięciach zewnętrznych. Istnieje wiele algorytmów sortowania, jedne wolniejsze inne szybsze. Przy określaniu szybkości algorytmu podaje się liczbę koniecznych porównań.

1. SORTOWANIE BĄBELKOWE

Algorytm ten polega na przeglądaniu sortowanej tablicy n - elementowej i zamianie miejscami sąsiadujących ze sobą elementów, jeżeli są one w kolejności odwrotnej tzn. pierwszy element jest mniejszy (lub większy) od następnego. Operację tę powtarzamy n razy.

Algorytm:

1. Wykonaj co następuje n-1 razy (i=n-1,...,1)

2. Wskaż na ostatni element;

3. Wykonaj co następuje i razy

Porównaj wskazany element z elementem poprzednim

Jeśli porównane elementy są w niewłaściwej kolejności, zamień je miejscami

Wskaż na następny element;

procedure bubble(var tab:ttab);

var i,j,kopia:integer;

porow,przes:longint;

begin

porow:=0;

przes:=0;

for i:=2 to n do

for j:=n downto i do

begin

inc(porow);

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

begin

kopia:=tab[j-1];

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

tab[j]:=kopia;

inc(przes,3);

end;

end;

end;

2. SORTOWANIE PRZEZ PROSTE WSTAWIANIE

Algorytm ten polega na przeglądaniu sortowanej tablicy zaczynając od j=2..n. Wartość Tab[j] wstawiana jest w odpowiednie miejsce pomiędzy Tab[1],Tab[2], ... , Tab[j-1].Wstawianie przeprowadzane jest w następujący sposób: wartość Tab[j] tymczasowo podstawia się pod pewną zmienną np. kopia, aby nie utracić wartości tam zapisanej. Następnie wartości w tablicy są przesuwane o odpowiednią ilość pozycji.

Algorytm:

1. Wykonaj co następuje począwszy od indeksu j=2 do j=n

2. Wskaż na i-ty element

3. Wstaw i-ty element w odpowiednim miejscu w tablicy

procedure wstaw(var tab:ttab);

var min,i,j,kopia,minpos:integer;

porow,przes:longint;

begin

min:=32767; {górna granica przedziału}

for i:=1 to n do if tab[i]<min then

begin

min:=tab[i];

minpos:=i; end;

tab[minpos]:=tab[1];

tab[1]:=min;

porow:=0;

przes:=0;

for j:=2 to n do

begin

i:=j-1;

Kopia:=tab[j];

inc(przes);

inc(porow);

while kopia<tab[i] do

begin

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

inc(przes);

i:=i-1;

end;

tab[i+1]:=kopia;

inc(przes);

end;

end;

3. SORTOWANIE PRZEZ PROSTE WYBIERANIE

Algorytm ten polega na wyznaczeniu najmniejszego (największego) elementu w tablicy Tab[1..n], oraz zamianie go z pierwszy elementem tablicy. Następnie wyszukujemy najmniejszy (największy) element w tablicy Tab[2..n] i zamieniamy go z drugim elementem w tablicy, itd. aż do posortowania całej tablicy.

Algorytm:

1. Wykonaj co następuje n-1 razy (j=1 do j=n-1)

2. Wskaż na najmniejszy element spośród Tab[1...n]

3. Wymień go z pierwszym

procedure wybierz(var tab:ttab);

var kopia,min,minpos,a,i:integer;

porow,przes:longint;

begin

a:=1;

porow:=0;

przes:=0;

while (a<>n-1) do

begin

min:=32767;

for i:=a to n do

begin

inc(porow);

if tab[i]<min then

begin;

min:=tab[i];

minpos:=i;

inc(przes);

end;

end;

kopia:=tab[a];

tab[a]:=min;

tab[minpos]:=kopia;

inc(a);

inc(przes,3);

end;

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 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.

Wybierzmy losowo obiekt i nazwijmy go x; przeglądajmy tablicę od lewej strony aż znajdziemy obiekt a_i>x, a następnie przeglądajmy tablicę od prawej strony aż znajdziemy obiekt a_j<x. Wymieńmy teraz te dwa obiekty i kontynuujmy proces "przeglądania i zamiany", aż nastąpi spotkanie gdzieś w środku tablicy. W rezultacie otrzymamy tablicę podzieloną na lewą część z kluczami mniejszymi od x oraz prawą część z kluczami większymi od x. Jeżeli na przykład za x wybierzemy środkowy klucz 42, to w tablicy kluczy:

44 55 12 42 94 6 18 67

trzeba dokonać dwóch wymian, aby otrzymać tablicę podzieloną

18 6 12 42 94 55 44 67

Ostatnie wartości indeksów są i=5 oraz j=3. Klucze a₁...a_i-1 są mniejsze bądź równe kluczowi 42, klucze a_j+1...a_n są większe bądź równe temu kluczowi. Wynika stąd, że otrzymaliśmy podział na dwie części, a mianowicie:

ak.klucz< x.klucz dla k=1...i-1

ak.klucz >x.klucz dla k=j+1...n

ak.klucz =x.klucz dla k=j+1...i-1

Następnie powtarzamy tę operację dla obu wcześniej utworzonych podciągów.

Algorytm:

Istnieje ciąg liczb x_l, x_l+1, x_p,

Krok1: Przyjmij za element podziału element v znajdujący się w pobliżu środka ciągu i podziel tym elementem dany ciąg;

Oznacza to, że v znajdzie się na pozycji elementu x_k, dla pewnego k spełniającego l≤ k≤ p, i elementy na lewo będą od niego większe, a elementy na prawo od niego będą mniejsze.

Krok2: Zastosuj ten sam algorytm do (l, k-1, x)

Krok2: Zastosuj ten sam algorytm do (k+1, p, x)

Algorytm ten jest bardzo prosty i efektywny, ponieważ zmienne i, j oraz x mogą być w czasie przeglądania tablicy trzymane w szybkich rejestrach maszyny cyfrowej.

procedure qsort(var tab: tablica; l,p:byte; var por:byte; var pre:byte);

var i,j:byte;

x,w:integer;

begin

x:=tab[(l+p) div 2];

i:=l;

j:=p;

repeat

while tab[i]<x do

begin

i:=i+1;

inc (por); {por=porównania}

end;

while x<tab[j] do

begin

j:=j-1;

inc (por);

end;

if i<=j then

begin

w:=tab[i];

tab[i]:=tab[j];

tab[j]:=w;

i:=i+1;

j:=j-1;

inc (pre); {pre=przestawienia}

end;

until i>j;

if l<j then qsort(tab,l,j,por,pre);

if i<p then qsort(tab,i,p,por,pre);

end;

ĆWICZENIE DO WYKONANIA:

W celu porównania algorytmów sortowania proszę napisać program, który:

• wczytuje losowo do tablicy elementy całkowite (liczba elementów musi być duża np.1000; 2000; 3000; 4000; 5000; 6000; 7000);

• sortuje n - elementową tablicę przy pomocy każdego z wyżej wymienionego algorytmu;

• Podczas trwania operacji sortowania mierzymy: czas pracy algorytmu - procedura GetTime(godzina, minuta, sekunda, setna-część-sekundy); liczbę porównań oraz liczbę przestawień jaką wykonał algorytm.

• program powinien wyświetlać tablicę nieposortowaną; liczbę porównań; ilość przestawień; czas sortowania, tablicę posortowaną oraz zapisywać na dysk posortowaną tablicę do innego pliku niż plik źródłowy

• napisać sprawozdanie z porównania tych metod sortowania.

Metoda sortowania	Liczba elementów n	Liczba przesunięć	Liczba porównań	Czas pracy [s]
Bąbelkowa	1 000 2 000 3 000 4 000 5 000 6 000 7 000	714 192 3 056 346 ............... ...............	999 000 3 998 000 ...............	0,17 0,49 ..............
Wstawianie
Wybieranie
Szybkie

tabela1. Porównanie algorytmów sortowania

WNIOSKI :

W wyniku przeprowadzonych pomiarów (patrz: tabela1): liczby porównań, liczby przestawień oraz czasu wykonywania się algorytmu stwierdzono, że najwolniejszym algorytmem jest algorytm.................................. Algorytm charakteryzował się najdłuższym czasem sortowania, największą liczbą porównań oraz przesunięć.

Renata Supranowicz

---