6583


Laboratorium :Algorytmy i struktury danych.

Temat:

Wybrane metody sortowania wewnętrznego

Wykonał:

Mariusz Daszkiewicz

Data:99-11-2521

Gr.27

Ocena:

1.1: Sortowanie przez proste wstawienie:

Sortowanie przez proste wstawienie odbywa się w następujący sposób: dla każdego i = 2, 3, ... , n trzeba powtarzać wstawianie a[i] <= ... <=a[i-1].

1.2: Algorytm:

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

2. Wskaż na i-ty element

3. Wstaw i-ty element w odpowiednim miejscy w a1...ai

1.3: Procedura wykonująca sortowanie:

procedure Dahoo1;

Begin

For i:=2 to n do

begin

if (tab[i]<tab[i+1]) then

begin

j:=-1;

repeat;

j:=j+1;

until(tab[j]<=tab[i]) and (tab[i]<=tab[i+1]);

z:=tab[i];

for x:=i downto j+2 do

begin

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

end;

tab[j+1]:=z;

end;

end;

1.4: Schemat blokowy algorytmu:

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

2.2: Algorytm:

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

2 Wskaż na najmniejszy element spośród a[i]...a[n];

3 Wymień go z a

2.3: Procedura wykonująca sortowanie:

Procedure Dahoo2;

Begin

For i:=0 to n do

For j:=i+1 to n do

begin

if ( tab[i]>tab[j]) then

begin

z:=tab[i];

tab[i]:=tab[j];

tab[j]:=z;

end;

end;

end;

2.4: Schemat blokowy algorytmu:

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

3.2: Algorytm:

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

2. Wskaż na najmniejszy element spośród a[i]...a[n];

3. Wymień go z ai

3.3: Procedura wykonująca sortowanie:

Procedure Dahoo3;

Begin

repeat

spr:=false;

j:=j+1;

for i:=u downto j do

begin

if (tab[i]<tab[i-1]) then

begin

z:=tab[i];

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

tab[i-1]:=z;

spr:=true;

end;

end;

until not(spr);

3.4: Schemat blokowy algorytmu:

4.1: Sortowanie szybkie (Quick sort):

To metoda, w której stosuje się zasadę zamiany. W metodzie tej korzysta się z faktu, że w celu zapewnienia efektywności powinno się wymieniać obiekty położone daleko od siebie. Założyć można, ż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.

4.3: Procedura wykonująca sortowanie:

Procedure Dahoo4(l,r:integer);

begin

v:=tab[l];

i:=l;

j:=r+1;

repeat

repeat

i:=i+1;

inc(iloscporownan);

until tab[i]>=v;

repeat

j:=j-1;

inc(iloscporownan);

until v>=tab[j];

if j>i then

begin

x:=tab[i];

tab[i]:=tablica[j];

tab[j]:=x;

inc(iloscprzestawien);

end;

until i>=j;

tab[l]:=tab[j];

tab[j]:=v;

if j-1>=l then sortowanie(l,j-1);

if r>=j+1 then sortowanie(j+1,r);

end;

4.4: Schemat blokowy algorytmu:

5: Wnioski:

Metoda sortowania przez proste wstawianie nie jest metodą która sprawdza się dobrze w maszynach cyfrowych - wstawianie elementu, a następnie przesuwanie całego wiersza elementów o jedną pozycję jest bardzo nieekonomiczne.

Metoda sortowanie przez proste wybieranie jest metodą, która ma najmniejszą ilość przestawień, bo dokładnie tyle ile ma dana tablica-1 ale charakteryzuje się dość duża liczbą porównań . Spowodowane jest to tym, że w tej metodzie przeskakujemy w tablicy po kolejnych pozycjach i za każdym razem przeglądamy pozostałą część tablicy poszukując najmniejszego elementu, który zamieniamy z elementem tablicy na którego pozycji aktualnie się znajdujemy.

Kolejna metoda sortowania : sortowanie bąbelkowe jest najwolniejszą metodą sortowania. Polega ono na tym , że rozpoczynając od końca tablicy sprawdzamy po dwa elementy i jeśli pierwszy jest większy od drugiego to są one zamieniane miejscami. Po sprawdzeniu całej tablicy, jeśli były jakieś zmiany sortowanie rozpoczyna się od nowa i jest powtarzane tak długo aż zostanie posortowana cała tablica. Ten sposób sortowania wykonał największą liczbę porównań ze wszystkich metod i podobną liczbę przestawień jak algorytm przez proste wstawianie .

Spośród badanych metod najszybsza okazała się metoda quicksortu. Dzięki jednoczesnemu sortowaniu prawej i lewej strony tablicy (patrząc z punktu widzenia element kluczowego) czas sortowania ulega znacznemu skróceniu gdyż elementy są przenoszone między dwoma połowami tablicy a więc są od siebie dość oddalone co znacznie przyśpiesza czas sortowania. Gdy mamy już podzieloną tablicę na dwie połowy to powyższy algorytm stosujemy do każdej z połówek i tak aż do posortowania całej tablicy. Algorytm ten posortował zadaną tablicę w najmniejszej liczbie porównań i prawie najmniejszej liczbie przestawień.



Wyszukiwarka

Podobne podstrony:
6583
6583
6583
6583
praca-magisterska-6583, Dokumenty(8)
sciaga 6583
6583
6583
6583

więcej podobnych podstron