Laboratorium 12

Wybrane algorytmy sortowania

*wiczenie 1

• Napisz procedur* sortuj*ca tablic* jednowymiarow* wypełnion* liczbami calkowitymi. Zastosuj algorytm sortowania przez proste wstawianie.

Proces sortowania przez wstawianie polega na wyszukaniu odpowiedniego miejsca w tablicy wynikowej dla kolejnych elementów tablicy. W każdym kroku począwszy od i=2 i zwiększając i o jeden , i-ty element tablicy źródłowej (nazwijmy go x) przenosi się do tablicy wynikowej wstawiając go w odpowiednie miejsce. Podczas znajdowania odpowiedniego miejsca rozpatruje się tylko jeden kolejny element tablicy i wszystkie elementy tej części tablicy, która jest już uporządkowana (po lewej stronie rozpatrywanego elementu). Rozpatrywany element tablicy (x) porównuje się z każdym elementem a_j na lewo od x i albo wstawia się x albo przesuwa w prawo element a_j. Zakończenie procesu wyszukiwania miejsca dla danego elementu x może wystąpić z dwóch powodów:

Element a_j jest mniejszy od x

Osiągnięto lewy koniec uporządkowanej tablicy.

Aby zapewni* prawidłowe przesuwanie element*w tablicy nale*y rozszerzy* zakres indeks*w tablicy do 0..n, do elementu a[0] wpisa* element x.

Poni*ej przedstawiono proces sortowania przez wstawianie dla 8 liczb losowych.

44 55 12 42 94 18 06 67

44 55 12 42 94 18 06 67 i=2

12 44 55 42 94 18 06 67 i=3

12 42 44 55 94 18 06 67 i=4

12 42 44 55 94 18 06 67 i=5

12 18 42 44 55 94 06 67 i=6

06 12 18 42 44 55 94 67 i=7

06 12 18 42 44 55 67 94 i=8

const m=20;

type t=array[0..m] of integer;

{************************}

procedure swstaw (var a:t;n:integer);

{sortowanie przez wstawienie}

var i,j:integer;

begin

writeln ('sortowanie przez wstawienie');

for i:=2 to n do

begin x:=a[i]; a[0]:=x; j:=i-1;

while x<a[j] do

begin a[j+1]:=a[j]; j:=j-1;

end;

a[j+1]:=x

end;

end;{procedury wstawian}

• w programie zadeklaruj tablic* typu t

• wprowadź liczb* n-zakres tablicy

• wypelnij tablic* liczbami losowymi ( zakres tablicy [1..n], zastosuj procedur*)

• wy*wietl tablic* (zastosuj procedur*)

• posortuj tablic*

• ponownie wy*wietl tablic* (zastosuj procedur*)

Ćwiczenie 2

• Napisz procedur* sortuj*ca tablic* jednowymiarow* wypełnion* liczbami całkowitymi. Zastosuj algorytm sortowania przez proste wybieranie.

Sortowanie przez proste wybieranie

W tej metodzie sortowania przy*to nast*pując* zasad* :

• wybieramy najmniejszy element tablicy

• wymieniamy go z pierwszym elementem tablicy

• z pozostałych n-1 element*w tablicy wybieramy najmniejszy i zamieniamy go z 2 elementem tablicy

• powtarzamy t* operacj* tak długo a* pozostanie nam ostatni najwi*kszy element

Poni*ej przedstawiono proces sortowania przez wstawianie dla 8 liczb losowych.

44 55 12 42 94 18 06 67

06 55 12 42 94 18 44 67

06 12 55 42 94 18 44 67

06 12 18 42 94 55 44 67

06 12 18 42 94 55 44 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 94 67

06 12 18 42 44 55 67 94

procedure swybier(var a:t;n:integer);

{sortowanie przez proste wybieranie}

var i,j:integer;

begin

writeln ('sortowanie przez proste wybieranie');

for i:=1 to n-1 do

begin k:=i;x:=a[i];

for j:=i+1 to n do

if a[j]<x then

begin k:=j; x:=a[j]

end;

a[k]:=a[i]; a[i]:=x;

end;

end; {procedury swybiet}

• sprawdź działanie procedury w programie

Ćwiczenie 3

Napisz procedur* sortuj*ca tablic* jednowymiarow* wypełnion* liczbami całkowitymi. Zastosuj algorytm sortowania bąbelkowego.

Sortowanie b*belkowe

Algorytm sortowania bąbelkowego polega na por*wnaniu i zamianie par s*siaduj*cych ze sobą par element*w tak długo a*

44 55 12 42 94 18 06 67

06 44 55 12 42 94 18 67 i=2

06 12 44 55 18 42 94 67 i=3

06 12 18 44 55 42 67 94 i=4

06 12 18 42 44 55 67 94 i=5

06 12 18 42 44 55 67 94 i=6

06 12 18 42 44 55 67 94 i=7

06 12 18 42 44 55 67 94 i=8

procedure sbabelko(var a:t;n:integer);

var i,j:integer;

begin

writeln ('sortowanie przez prosta zamiane- babelkowe');

for i:=2 to n do

begin for j:=n downto i do

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

begin x:=a[j-1]; a[j-1]:=a[j]; a[j]:=x

end

end

end; {procedury sbabelko}

• sprawdź działanie procedury w programie

• zmodyfikuj procedur* tak, aby nie wykonywała przej**, kt*re nie maj* wpływu na kolejno** element*w ( w przykładzie trzy ostatnie przebiegi)

Ćwiczenie 4

Zastosuj dowoln* procedur* sortowania do posortowania wszystkich wierszy tablicy dwuwymiarowej.

W tym celu nale*y:

• zadeklarowa* tablic* dwuwymiarow* jako tablic* tablic jednowymiarowych

const m=20;

n=20;

type t=array[0..m] of integer;

t1=array[0..n] of t;

var tab1:t1;

i,k,l:integer;

• W programie nale*y zdefiniowa* procedury:

wypelniania tablicy jednowymiarowej init_tab (var tab:t; m:integer)

wy*wietlania tablicy jednowymiarowej wy*wietl(tab:t;m:integer)

sortowania tablicy jednowymiarowej sort (tab:t; m:integer)

lub wykorzysta* modul, kt*ry zawiera te procedury

• przykladowy fragment programu :

{*******************wypelnianie tablicy******************}

for i:=1 to k do

init_tab(tab1[i],l);

{*******************wy*wietlanie tablicy******************}

for i:=1 to k do

wyswietl (tab1[i],l);

{'*******************sortowanie wierszy tablicy************'}

for i:=1 to k do

sort(tab1[i],l);

{*******************wy*wietlanie tablicy po posortowaniu*****}

for i:=1 to k do

wyswietl(tab1[i],l);

---