Lech Pławecki, 2004.r.
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.