Sortowanie Turbo Pascal.doc

Sortowaniem nazywamy ustawianie określonego zbioru obiektów w określonym porządku. Najlepszym przykładem z życia będą encyklo­pedie, słowniki, książki telefoniczne itp.; ułożone są one alfabetycznie w celu ułatwienia wyszukiwania konkretnych informacji. Pisząc kiedyś bazę danych, czytelnik z pewnością zetknie się z problemem sortuwania danych.

Sortowanie z punktu widzenia programisty jest doskonałym przykładem zastosowania różnych algorytmów do tego samego celu. W roz­dziale tym przytoczę trzy różne algorytmy. Dwa pierwsze sposoby cha­rakteryzują się prostotą w konstrukcji, ale jednocześnie są one dosyć wolne. Ostatni jest bardziej skomplikowany, ale za to bardzo szybki. -

Pierwsza metoda nazywa się sortowaniem bąbelkowym i klasyfi­kowana jest do algorytmów sortowania przez prostą zamianę. Polega on na porównywaniu i zamianie par sąsiadujących liczb. Rozważmy to na przykładzie.

Zaczynamy sprawdzać od końca, jeśli wartość końcowa jest mniej­sza od przedostatniej, to zamieniamy je ze sobą. Sprawdzamy kolejnego sąsiada i w ten sposób wędrujemy z liczbą w lewą stronę, aż natkniemy się na mniejszą, np.:

              44              12              72              55              45 —              początkowe ustawienie
              44              12              72              45              55 —              pierwsze porównanie 55>45
              44              12              45              72              55 —              drugie porównanie 45>75
              12              44              45              72              55—.              trzecie45>44, a1e 44>l2

Operację rozpoczynamy od nowa, aż do uporządkowania całej tablicy. W programie umieścimy wpierw pętlę, w której zapełnimy tablicę przypadkowymi wartościami (polecenie random i randomize). Wygodnie jest się posłużyć stałą w programie. Deklaracja takiej zmien­nej następuje po słowie const i podajemy stałą wartość (liczbową, teksto­wą itd), której później w programie nie możemy zmieniać. Jest to bardzo

wygodne ze względu na ewentualne modyfikacje w programie. W przed­stawionym programie wystarczy zmienić wartość n, jeśli chcemy, aby sortowanie odbywało się na tablicy innej wielkości. Gdybyśmy nie posłu­giwali się stałą, należałoby dokonywać zmian we wszystkich procedurach operujących na tej tablicy.

program sortowanie_babelkowe;

uses crt;

const

n =1000; {tysiac elementow do posortowania}

var tablica : array(1. .n] of integer;

              i              : integer;

procedure losuj;

begin

randomize;

{zainicjuj generator liczb losowych} for i:=1 to n do

tablica[i] :=random(1000);

(wypelnij tablice przypadkowymi liczbami od O do 1000}

end;

procedure sortuj;

var j,a : integer;

begin

for i:=2 to n do

for j:=n downto i do

if tablica[j—1]>tablica(j] then

begin

a:=tablica[j—1];

(zamien ze soba sasiadujace elementy}

tablica[ j—11 :=tablica[j];

tablica[j) :a;

end;

end;

procedure wyswietl;

begin .

for i:=1 to n do write(tablica[i],’   ‘);

end;

begin

clrscr;

losuj;

wyswietl;

readln;

clrscr;

sortuj;

wyswietl;

readln;

end.

Kolejny algorytm to sortowanie przez proste wybieranie. Polega on na wybieraniu najmniejszego elementu i zamianie z elementem porównywanym. Tym razem posuwamy się od początku tablicy. Odnaj­dujemy najmniejszą wartość i zamieniamy miejscami z n-tym elementem z pętli. Oto przykład:

              67              53              23              44              —              ustawienie początkowe
              23              53              67              44              —              pierwsze przejście
              23              44              67              53              —              drugie przejście
              23              44              53              67              —              trzecie przejście

program sortowanie_przez_proste wybieranie;

uses crt;

const

n = 1000; (tysiac elementow do posortowania}

yar tablica : array(1. .n] of integer;

              i              : integer;

procedure losuj;

begin

randomize; (inicjuj generator liczb losowych}

for i:=1 to n do

tablica[i] :=random( 1000); {losuj}

end;

proc edure wyswietl;

var x,y: integer;

begin

x:0; y:l; {wysWietl w kolumnach}

for i:=1 to n do begin

x:=x+5;

if x>75 then begin y:=y+l; x:=5; end;

if              y>25 then begin readln;

clrscr;

end;

gotoxy(X,y);

write(tabliCa[i]);

end;

end;

begin 

clrscr; 

losuj;

wyswietl;

readln;

clrscr;

sortuj;

wyswietl;

readln;

end.

Dla porównania skuteczności sortowań przedstawię czasy wyko­nywania programów dla różnych wielkości tablic. Test przeprowadzany był na komputerze IBM AT-286 z zegarem 12Mhz. Wyniki podane w formacie: minuty : sekundy : setne.

Wielkość tablicy

              100              1000              10000
1) sortowanie bąbelkowe              00:00:05              00:04:83              08:04:55

2) sortowanie przez proste wybieranie              00:00:01              00:02:69              04:26:77

3) sortowanie szybkie                                   00:00:00            00:00:10         00:01:15

W programie sortowania szybkiego znalazł się typ rekordowy. Jest to złożona struktura danych, podzielona na poszczególne poła przypisane przez programistę. W naszym konkretnym przypadku mamy do czynie­nia z dwoma polarni, przy czym obydwa są typu integer. Nie jest to zbyt rozbudowana struktura i nie nadaje się do obrazowego zilustrowania tworzenia rekordów. Wyobraźmy więc sobie kartkę, na której znajduje się kilka danych, np. dane osobowe. Niech to będzie: nazwisko, wiek, miejsce zamieszkania. Nie ma sensu tworzenie osobnych zmiennych, ponieważ mogłaby wtedy wystąpić trudność w powiązaniu ze sobą da­nych (zwłaszcza w przypadku tablic). Zadeklarujemy zmienną rekordo­wą kartka i przypiszemy jej odpowiednie pola.

              kartka              record

              nazwisko              : string[45] ;
              wiek              : integer;

miejsce_zam : string[100];

end;

Wywołanie poszczególnego pola odbywa się w następujący sposób:

naz : =kartka . nazwisko

lub jeśli spodziewamy się kilku operacji na rekordzie:

with kartka do

begin

........

end;

Ponieważ sortowanie samych liczb jest raczej bezcelowe, możemy wykorzystać podane algorytmy do porządkowania określonych danych. Wygodnie jest wtedy właśnie założyć rekord, np.

tablica: array 1. .100] of record

nr_ewidencyjny: integer; nazwisko : string;

itd...

end;

Wówczas będziemy mogli sortować według pola tablica[i].nr_ewi­dencyjny. Zaprezentowane metody sortowania z pewnością dadzą się bez problemu zaadaptować do poważniejszych programów, np. baz danych. Niestety są one przystosowane do niewielkich ilości danych, co związane jest z ograniczeniem pamięci komputera. Natomiast sortowanie plików sekwencyjnych odbywa się za pomocą innych algorytmów.

procedure sortuj; var j,a,k: integer;

begin

for i:1 to n-1 do

begin

k:=i; a:=tabłica[i];

for j:=i+1 to n do

if tablica[j]<a then

begin

k:=j; a:=tablica[j]; {wybierz element} end;

tablica(kJ :=tabłica[i];

{zalnien go z testowanym}

tablica[i] :=a;

end;

end;

proc edure wyswietl;

var x,y: integer;

begin

x:=0; y:=1; {wyswietl wyniki w kolumnach)

for i:=1 to n do begin

x :x+5

if              x>75 then begin y:=y+1; x:=5; end;

if              y>25 then begin

readln;

             clrscr;

y:=1

end;

gotoxy(x,y);

write(tablica[i]);

end;

end;

begin

clrscr;

losuj;

Wyswietl;

readln;

clrscr;

sortuj;

Wyswietl;

readłn;

end.

Ostatnia metoda, którą omówię, nosi nazwę sortowania szybkiego. Należy ona do nowoczesnych algorytmów i jest najlepszym znanym sposobem sortowania tablic. Wymyślona została przez CAR Hoare. Zazwyczaj rozwiązywana jest rekurencyjnie, ponieważ jednak rekurencja to niejako „wyższa szkoła jazdy”, przedstawię program pracujący iteracyjnie.

              46              72              31              35              31              55              1              19

Początkowo wybieramy obiekt a (problem wyboru omówię za chwilę), przyjmijmy, że będzie to środkowy element tablicy. Następnie, zaczynając od lewej strony tablicy, odnajdujemy obiekt większy od a; od prawej strony szukamy obiektu mniejszego od a. Zamieniamy je ze sobą i kontynuujemy przeszukiwanie, aż nastąpi przejście połowy.

a

              46              72              31              35              31              55              1              19

...