Sortowanie
A
lg
o
ryt
m
y
i
st
ru
kt
u
ry
d
an
ych
Sortowanie
Bartman Jacek
jbartman@univ.rzeszow.pl
A
lg
o
ryt
m
y
i
st
ru
kt
u
ry
d
an
ych
Sortowanie
A
lg
o
ryt
m
y
i
st
ru
kt
u
ry
d
an
ych
Sortowanie
Bartman Jacek
jbartman@univ.rzeszow.pl
A
lg
o
ryt
m
y
i
st
ru
kt
u
ry
d
an
ych
Sortowanie przez proste wstawianie – przykład
Sortowanie przez proste wstawianie – przykład
41
88
24
39
56
17
72
41
56
41
56
88
24
39
17
03
72
56
17
17
41
56
56
88
24
39
03
72
17
39
17
39
41
56
56
88
24
03
72
39
88
03
03
17
39
41
56
56
88
24
03
72
39
88
17
39
41
56
88
24
03
72
88
24
17
24
41
56
39
88
03
72
03
03
24
17
39
41
56
88
72
24
03
17
24
39
41
56
72
72
88
72
Sortowanie przez proste wybieranie – przykład
Sortowanie przez proste wybieranie – przykład
41
88
24
39
56
17
41
03
03
03
03
88
24
39
56
17
72
03
41
41
17
56
17
56
03
88
24
39
72
41
56
24
56
24
56
72
17
03
39
88
41
72
17
56
24
39
24
56
72
17
03
39
88
41
56
24
39
39
03
17
24
88
56
41
72
39
41
88
41
88
03
17
24
39
56
72
41
88
56
56
03
17
24
39
72
41
88
56
72
88
72
88
03
17
24
39
41
56
72
88
Sortowanie przez prostą zamianę – przykład
Sortowanie przez prostą zamianę – przykład
41
39
56
17
39
03
03
39
39
<
39
03
17
17
<
17
17
03
56
56
<
56
03
56
41
<
41
41
41
17
03
41
56
24
03
17
41
17
03
17
24
39
03
17
24
39
03
17
24
39
03
17
24
88
24
39
03
72
72
03
03
72
<
41
39
72
72
03
03
24
<
24
24
03
24
88
88
<
88
88
03
39
39
<
39
39
17
72
24
56
24
39
88
72
72
72
56
39
88
88
72
39
24
17
39
24
72
56
88
41
88
72
56
41
39
72
56
88
88
72
56
56
41
39
88
72
88
72
72
56
41
88
88
Sortowanie za pomocą malejących przyrostów –
metoda Shella
Sortowanie za pomocą malejących przyrostów –
metoda Shella
Metoda jest rozwini
ę
ciem metody sortowania przez wstawianie.
W metodzie tej, najpierw grupuje si
ę
i sortuje oddzielnie wszystkie
elementy oddalone o pewn
ą
odległo
ść
(przyrost) h (tj. oddalone „co
h”). W pierwszym kroku metody tworzy si
ę
wi
ę
c n-podzbiorów,
które sortowane s
ą
metod
ą
przez wstawianie.
które sortowane s
ą
metod
ą
przez wstawianie.
W nast
ę
pnych krokach powtarza si
ę
tak
ą
operacj
ę
dla coraz
mniejszych odległo
ś
ci h, a
ż
do momentu gdy h=1, co odpowiada
normalnemu sortowaniu całego zbioru (elementy oddalone „co
jeden”).
Sortowanie metodą Shella - przykład
Sortowanie metodą Shella - przykład
Sortowanie metodą Shella – przykład
Sortowanie metodą Shella – przykład
Sortowanie metodą Shella
Sortowanie metodą Shella
Metoda ta jest bardzo efektywna, pomimo,
ż
e wyst
ę
puje kilka
wst
ę
pnych procesów sortowa
ń
.
Dla du
ż
ych warto
ś
ci odst
ę
pu h, sortowane zbiory maj
ą
mało
elementów.
Dla małych h zbiory s
ą
ju
ż
znacznie uporz
ą
dkowane.
W obu tych przypadkach sortowanie takich zbiorów za pomoc
ą
metody przez wstawiane jest bardzo szybkie.
Metoda działa najlepiej gdy przyrosty h nie s
ą
swoimi dzielnikami.
Zaleca si
ę
stosowanie nast
ę
puj
ą
cych przyrostów:
h
k-1
= 3h
k
+ 1, h
t
= 1, t = log
3
n-1
⇒
... 121, 40, 13, 4, 1
lub:
h
k-1
= 2h
k
+ 1, h
t
= 1, t = log
2
n-1
⇒
... 31, 15, 7, 3, 1
Efektywno
ść
metody: Po, Pr ~ n
1,2
Sortowanie przez podział - sortowanie szybkie
Sortowanie przez podział - sortowanie szybkie
Algorytm post
ę
powania
wybiera si
ę
losowo jaki
ś
element
x
z sortowanego zbioru,
przegl
ą
da si
ę
zbiór
od strony „lewej”
, a
ż
znaleziony zostanie taki
element A
i
,
ż
e
A
i
≥≥≥≥
x
,
przegl
ą
da si
ę
zbiór
od strony „prawej”
,
a
ż
znajdzie si
ę
element A
j
, taki
przegl
ą
da si
ę
zbiór
od strony „prawej”
,
a
ż
znajdzie si
ę
element A
j
, taki
ż
e
A
j
≤≤≤≤
x
,
zamienia si
ę
miejscami elementy A
i
i A
j
,
kontynuuje si
ę
proces przegl
ą
dania i zamiany, a
ż
nast
ą
pi spotkanie
gdzie
ś
w
ś
rodku tablicy.
Sortowanie przez podział - sortowanie szybkie
Sortowanie przez podział - sortowanie szybkie
Miejsce spotkania wyznacza punkt podziału tablicy na dwie
cz
ęś
ci. „Lewa” cz
ęść
składa si
ę
z elementów nie wi
ę
kszych ni
ż
wybrany element x, „prawa” za
ś
z elementów nie mniejszych
ni
ż
x.
Takie cz
ęś
ci sortuje si
ę
nast
ę
pnie oddzielnie w sposób
opisany powy
ż
ej.
opisany powy
ż
ej.
Powtarzanie tych operacji a
ż
do momentu gdy cz
ęś
ci tablicy
b
ę
d
ą
składały si
ę
z jednego elementu, doprowadzi do
posortowania całej tablicy.
Efektywno
ść
metody: Po ~ n*log(n), Pr ~ n
Sortowanie przez podział – przykład
Sortowanie przez podział – przykład
Sortowanie przez podział – przykład
Sortowanie przez podział – przykład
Sortowanie stogowe
Sortowanie stogowe
Drzewo porówna
ń
Dla n-elementowej tablicy mo
ż
na wyznaczy
ć
„drzewo porówna
ń
”
za pomoc
ą
n-1 operacji porówna
ń
kluczy elementów
Ka
ż
dy w
ę
zeł jest elementem o mniejszym kluczu z dwóch
s
ą
siaduj
ą
cych w drzewie
Na wierzchołku drzewa zawsze znajduje si
ę
element o
najmniejszym kluczu !
Sortowanie drzewiaste - przykład
Sortowanie drzewiaste - przykład
Sortowanie drzewiaste
Sortowanie drzewiaste
Sortowanie tablicy, dla której utworzono drzewo wymaga:
pobrania elementu z wierzchołka (zawsze najmniejszy klucz)
zast
ą
pienie pobranego elementu elementem o mniejszym kluczu z
ni
ż
szego w
ę
zła
Procedura taka pozwala odczyta
ć
z drzewa posortowane elementy
tablicy
tablicy
Otrzymanie posortowanej tablicy wymaga n operacji odczytu z
drzewa
Ka
ż
dy odczyt (wybieranie elementu z drzewa wymaga log2(n)
porówna
ń
i przesuni
ęć
Cały proces sortowania przez wybieranie z drzewa wymaga wi
ę
c
n*log(n) operacji (oraz n-1 operacji potrzebnych do utworzenia
drzewa)
Stóg
Stóg
Stóg jest struktur
ą
drzewiast
ą
, której ka
ż
dy element jest nie wi
ę
kszy
od dwóch elementów bezpo
ś
rednio pod nim (potomków)
Pomi
ę
dzy elementami na tym samym poziomie nie zachodz
ą
ż
adne
relacje
Tworzenie struktury stogu wymaga (jak poprzednio n*log(n) operacji
Sortowanie stogowe
Sortowanie stogowe
Sortowanie stogowe polega na pobraniu elementu z wierzchołka,
przesuwaniu elementów o mniejszych kluczach w gór
ę
drzewa i
eliminacji jednego elementu z dołu struktury (li
ś
cia)
Struktura stogu usprawnia sortowanie drzewiaste, poniewa
ż
eliminuje niepotrzebne porównania elementu, który jest eliminowany
z drzewa
Stóg – reprezentacja tablicowa
Stóg – reprezentacja tablicowa
Dodawanie elementów do stogu – przesiewanie
Dodawanie elementów do stogu – przesiewanie
Dodanie elementu musi utrzyma
ć
warunek stogu (li
ś
cie potomne s
ą
nie wi
ę
ksze ni
ż
ich rodzic).
Nowy element wstawiany jest na
wierzchołek drzewa, a nast
ę
pnie
„przesiewany” przez w
ę
zły
mniejszych elementów
stogu,które podnosz
ą
si
ę
przez to
do góry.
do góry.
44
42
10
55
94
18
12
44
42
10
55
94
18
12
44
42
10
55
94
18
12
Dodawanie elementów do stogu – przesiewanie
Dodawanie elementów do stogu – przesiewanie
44
42
10
55
94
18
12
?
?
10
42
44
55
94
18
12
44
42
10
55
94
18
12
10
42
44
55
94
18
12
10
42
12
55
94
18
44
Uzyskany zapis spełnia
wymogi stawiane stogowi
Dodawanie elementów do stogu – podsumowanie
Dodawanie elementów do stogu – podsumowanie
Dla tablicy n elementowej,
elementy
od (n div 2)+1
do n
tworz
ą
stos.
Sortowanie stogowe
Sortowanie stogowe
Maj
ą
c tablice o strukturze
stogu, sortowanie polega
na:
pobraniu z wierzchołka
elementu i usuni
ę
ciu go ze
stogu
przesianiu przez
10
42
12
55
94
18
44
67
67
42
12
55
94
18
44
10
67
42
12
55
94
18
44
10
przesianiu przez
zmniejszony stóg elementu
ostatniego
w miejsce ostatniego
elementu umieszczenie
elementu zdj
ę
tego z
wierzchołka
12
42
67
55
94
18
44
10
12
42
18
55
94
67
44
10
44
42
18
55
94
67
12
10
44
42
18
55
94
67
12
10
18
42
44
55
94
67
12
10
18
42
44
55
94
67
12
10
67
42
44
55
94
18
12
10
67
55
94
44
42
18
12
10
55
67
94
44
42
18
12
10
55
67
94
44
42
18
12
10
94
67
55
44
42
18
12
10
42
67
44
55
94
18
12
10
42
55
44
67
94
18
12
10
94
55
44
67
42
18
12
10
44
55
94
67
42
18
12
10
44
55
94
67
42
18
12
10
67
94
55
44
42
18
12
10
67
94
55
44
42
18
12
10
94
67
55
44
42
18
12
10