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