Lech Pławecki, 2004.r.

Lech Pławecki, 2004.r.

Plan zajęć

• Powtórzenie i sprawdzenie

wiadomości z poprzedniego
ćwiczenia.

• Metody sortowania

– metoda Shella
– sortowanie stogowe (drzewiaste)
– sortowanie szybkie (przez podział)

• Szacowanie złożoności metod

sortowania

Lech Pławecki, 2004.r.

Sortowanie

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

44 55 12 42 94 18 06 67

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

44 55 12 4

2

94 1 8 06 67

44 18 12 4

2

94 55 06 67

44 18 06 4

2

94 55 12 67

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

44 18 06 42 94 55 12

67

06 18 12 42 44 55
94 67

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

06 18 12 42 44 55 94 67

06 18 12 42 44 55 94 67

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

06 18 12 42 44 55
94 67

06 12 18 42 44 55
67 94

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

Metoda ta zwana jest też metodą

malejących przyrostów. Metoda ta daje

lepsze wyniki, gdy stosuje się przyrosty

różne od potęg liczby 2, pod warunkiem że

ostatni przyrost to 1.
Często stosuje się przyrosty 9,5,3,1.
Każde sortowanie musi oczywiście ustawić

własnego wartownika.
W związku z tym tablica sortowana będzie

powiększona o ilość elementów równą

wartości największego przyrostu.

Lech Pławecki, 2004.r.

Sortowanie metoda

Shella

a:array[-h1..n]
procedure SortowanieShella
begin h[1]:=9; h[2]:=5; h[3]:=3; h[4]:=1;
for m:=1 to 4 do
begin k:=h[m]; s:=-k; {miejsce wartownika}
for i:=k+1 to n do
begin x:=a[i]; j:=i=k

if s=0 then s:=-k; s:=s+1; a[s]:=x;
while x<a[j] do begin a[j+k]:=a[j]; j:=j-k end;
a[j+k]:=x;

end
end
end

Lech Pławecki, 2004.r.

Sortowanie stogowe

Stogiem, czyli kopcem (ang. heap)

nazywamy ciąg elementów:
h

1

, h

2

,..., h

i

, ..., h

p

taki że:

h

i

<= h

2i

h

i

<= h

2i+1

Taki ciąg elementów można przedstawić

w postaci tabeli lub w postaci drzewa.

Lech Pławecki, 2004.r.

Sortowanie stogowe

1

2

3

4

5

6

7

8

9

11

12

14

15

10

13

Przyporządkowanie elementów tablicy i

węzłów kopca

1

2

3

4

5

6

7

8

9

1

0

11

12 13 14 15

Lech Pławecki, 2004.r.

Sortowanie stogowe

Numery sąsiadów węzła w kopcu

k/2

k

2k+1

2k

Poprzedni

Bieżący

Następny lewy

Następny prawy

Lech Pławecki, 2004.r.

Sortowanie stogowe

Procedura przesiewania.
Procedura przesiewania polega na
dodaniu nowego elementu do szczytu
kopca, a następnie na przesuwaniu
go w dół kopca dopóki napotka na
element mniejszy. Jeżeli następne
elementy kopca (nr 2k i 2k+1) są oba
mniejsze, przesiewany element
przesuwamy poza mniejszy z nich.

Lech Pławecki, 2004.r.

Sortowanie stogowe

procedure przesiewanie(l,p:integer);
begin
i:=l; j:=2*i; x:=a[i];
while j <= p do
begin j:=2*i; {wybór węzła następnego lewego}

if j<n then if a[j] > a[j+j] then j:=j+1;

{Jeżeli węzeł następny prawy istnieje i jest

niemniejszy od lewego - wybieramy go}
if x <= a[j] then goto 13; {element jest na swoim

miejscu}

a[i]:=a[j]; i:=j; j:=2*i; {przesiewanie}
end;
13 :a[i]:=x;
end przesiewanie;

Lech Pławecki, 2004.r.

Sortowanie stogowe

Tworzenie kopca
Jak łatwo zauważyć ostatni rząd
drzewa, odpowiadający numerom
elementów większym od p/2 spełnia
warunki kopca.
Teraz możemy rozszerzać kopiec w
lewo, przesiewając elementy od p div
2 do 1.

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

44 55 12 42 94 18 06 67

44

55

12

42

94

18

06

67

Lech Pławecki, 2004.r.

67

Sortowanie stogowe

Przykład

44 55 12 42 94 18 06 67

44

55

12

42

94

18

06

67

- elementy.które już tworzą kopiec

przesiewamy 42

Lech Pławecki, 2004.r.

67

Sortowanie stogowe

Przykład

44 55 12 42 94 18 06 67

44

55

12

42

94

18

06

67

- elementy.które już tworzą kopiec

przesiewamy 12

Lech Pławecki, 2004.r.

67

Sortowanie stogowe

Przykład

44 55 06 42 94 18 12 67

44

55

06

42

94

18

12

67

- elementy.które już tworzą kopiec

przesiewamy 55

Lech Pławecki, 2004.r.

67

Sortowanie stogowe

Przykład

44 42 06 55 94 18 12 67

44

42

06

55

94

18

12

67

- elementy.które już tworzą kopiec

przesiewamy 44

Lech Pławecki, 2004.r.

67

Sortowanie stogowe

Przykład

44 42 06 55 94 18 12 67

44

42

06

55

94

18

12

67

- elementy.które już tworzą kopiec

przesiewamy 44

Lech Pławecki, 2004.r.

67

Sortowanie stogowe

Przykład

06 42 12 55 94 18 44 67

06

42

12

55

94

18

44

67

- elementy.które już tworzą kopiec

elementy tworzą

kopiec

Lech Pławecki, 2004.r.

Sortowanie stogowe

Algorytm tworzenia kopca:
(Algorytm Floyda)

l:= (p div2)+1;
While l>1 do
begin l:=l-1; przesiewanie(l,p) end

Lech Pławecki, 2004.r.

Sortowanie stogowe

Gdy mamy utworzony kopiec, do
posortowania go należy wykonać n
kroków przesiewania.
W każdym kroku należy zdjąć z
wierzchołka i przechować jeden element,
wstawić ostatni element na wierzchołek
stosu ostatni element i przesiać go a
następnie przechowany pierwszy element
wstawić na miejsce ostatniego.

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

06

42

12

55

94

18

44

67

06 42 12 55 94 18 44 67

67

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

67

42

12

55

94

18

44

06

67 42 12 55 94 18 44 06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

12

42

67

55

94

18

44

06

12 42 67 55 94 18 44 06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

12

42

18

55

94

67

44

06

12 42 18 55 94 67 44 06

44

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

44 42 18 55 94 67 12 06

44

42

18

55

94

67

12

06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

18 42 44 55 94 67 12 06

18

42

44

55

94

67

12

06

67

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

67 42 44 55 94 18 12 06

67

42

44

55

94

18

12

06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

42 55 44 67 94 18 12 06

42

55

44

67

94

18

12

06

94

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

94 55 44 67 42 18 12 06

94

55

44

67

42

18

12

06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

44 55 94 67 42 18 12 06

44

55

94

67

42

18

12

06

67

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

67 55 94 44 42 18 12 06

67

55

94

44

42

18

12

06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

67 55 94 44 42 18 12 06

67

55

94

44

42

18

12

06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

55 67 94 44 42 18 12 06

55

67

94

44

42

18

12

06

94

Lech Pławecki, 2004.r.

Sortowanie stogowe

Przykład

94 67 55 44 42 18 12 06

94

67

55

44

42

18

12

06

Lech Pławecki, 2004.r.

Sortowanie stogowe

Algorytm sortowania kopca:

while p>1 do
begin
x:=a[1]; a[1]:=a[p]; a[p]:=x;
p:=p-1; przesiewanie(1,p)
end

Lech Pławecki, 2004.r.

Sortowanie stogowe

procedure przesiewanie(l,p:integer);
begin
i:=l; j:=2*i; x:=a[i];
while j <= p do
begin j:=2*i; {wybór węzła następnego lewego}

if j<n then if a[j] > a[j+j] then j:=j+1;

{Jeżeli węzeł następny prawy istnieje i jest niemniejszy od lewego - wybieramy go}

if x <= a[j] then goto 13; {element jest na swoim miejscu}

a[i]:=a[j]; i:=j; j:=2*i; {przesiewanie}
end;
13 :a[i]:=x;
end przesiewanie;
{tworzenie kopca}
l:= (p div2)+1;
While l>1 do
begin l:=l-1; przesiewanie(l,p) end
{sortowanie kopca}
while p>1 do
begin
x:=a[1]; a[1]:=a[p]; a[p]:=x;
p:=p-1; przesiewanie(1,p)
end

Lech Pławecki, 2004.r.

Sortowanie szybkie

Zwane też sortowaniem przez podział
(ang. Quicksort) jest uważane za najszybszy

algorytm sortowania. Jest to algorytm

rekurencyjny w którym wybiera się element

środkowy a pozostałe elementy przestawia się

w ten sposób, aby mniejsze od elementu

środkowego znalazły się na początku tablicy.

a większe na końcu. Następnie dzieli się

tablicę na dwie części i wykonuję opisaną

procedurę dla każdej z części oddzielnie.

Powyższe powtarza się
aż do uzyskania ciągów zawierających tylko

jeden element.

Lech Pławecki, 2004.r.

Sortowanie szybkie

Przykład:

44 55 12 42 94 06 18 67

18 06 12 42 94 55 44 67

Lech Pławecki, 2004.r.

Sortowanie szybkie

procedure sortuj(l,p);
begin i:=l; j:=p;

x:=a[(l+p) div 2];
repeat
while a[i] < x do i:=i+1;
while a[j] > x do j:=j-1;
if i <= j then
begin
w:=a[i]; a[i]:=a[j]; a[j]:=w; i:=i+1; j:=j-1;
end;
until i>j;
if l<j then sortuj (l,j);
if p>i then sortuj (i,p);

end

Uruchom

Przycisk
działa tylko
w czasie
pokazu.

Lech Pławecki, 2004.r.

Ćwiczenie 1

Oszacuj złożoność obliczeniową

algorytmu sortowania
stogowego

Lech Pławecki, 2004.r.

Ćwiczenie 2

Oszacuj złożoność obliczeniową

algorytmu sortowania
szybkiego.