Sortowanie
Sortowanie
Bartman Jacek
[e-mail]
Algorytmy i struktury danych
Algorytmy i struktury danych
Sortowanie przez proste wstawianie  przykład
Sortowanie przez proste wstawianie  przykład
41 56
41 56 17 39 88 24 03 72
41 56 17 39 88 24 03 72
56 17
17 56 39
17 41 56 39 88 24 03 72
17 39 41 56 88 24 03 72
17 39 41 56 88 24 03 72
39 56 88
39 56 88
88 24
17 39 41 56 88 24 03 72
17 24 39 41 56 88 03 72
24 03
03 72
03 17 24 39 41 56 88 72
03 17 24 39 41 56 72 88
72
Sortowanie przez proste wybieranie  przykład
Sortowanie przez proste wybieranie  przykład
41 03
41 56 17 39 88 24 03
03
72
41
03 56 17
03 56 17 39 88 24 41 72
03 56 39 88 24 41 72
56
56
17
17 24
03 17 24 39 88 41 72
03 17 24 39 88 41 72
24 39
24 39
56
56
56
56
39
39
03 17 24 88 56 41 72
88 41
03 17 24 39 41 56 88 72
41 56 88
03 17 24 39 41 56 88 72
56 88 72
03 17 24 39 41 56 72
72
88
88
Sortowanie przez prostą zamianę  przykład
Sortowanie przez prostą zamianę  przykład
03 03
03
41
41
41 03 03 03 03
03
< 41
17 17
17
56
56 41
56 17
17 17
03 < 56
17
17
17 41 24
56 24
24 24 24
03 < 17
39
41
39 39 39 39
39 39 39 39
39 17
39 17
39 17 56
39 17 56
03 < 39
03 < 39
41 41
41
24 56 41 41
24
24
88
88
88 39
03 < 88
56
56 56 56
56 56
39 39
39 39
88
24
24
24
03 < 24
88
72
03
03 24 72 72
03 24 72 72 72 72 72
72
03 < 72
88
88
88
88
88 88
72 88 88 88
72 88
72
72 72
72 72
Sortowanie za pomocą malejących przyrostów 
Sortowanie za pomocą malejących przyrostów 
metoda Shella
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:
hk-1 = 3hk + 1, ht = 1, t = log3n-1 Ò! ... 121, 40, 13, 4, 1
lub:
hk-1 = 2hk + 1, ht = 1, t = log2n-1 Ò! ... 31, 15, 7, 3, 1
Efektywność metody: Po, Pr ~ n1,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 Ai, że Aie"x,
e"
e"
e"
przegląda się zbiór od strony  prawej , aż znajdzie się element Aj, taki
przegląda się zbiór od strony  prawej , aż znajdzie się element Aj, taki
że Ajd"x,
d"
d"
d"
zamienia siÄ™ miejscami elementy Ai i Aj ,
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
Uzyskany zapis spełnia
wymogi stawiane stogowi
10 42 12 55 94 18 44
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:
10 42 12 55 94 18 44 67
pobraniu z wierzchołka
67 42 12 55 94 18 44 10
elementu i usunięciu go ze
67 42 12 55 94 18 44 10
stogu
przesianiu przez
przesianiu przez
12 42 67 55 94 18 44 10
zmniejszony stóg elementu
12 42 18 55 94 67 44 10
ostatniego
w miejsce ostatniego
elementu umieszczenie
elementu zdjętego z
wierzchołka
44 42 18 55 94 67 12 10
44 42 18 55 94 67 12 10 67 55 94 44 42 18 12 10
18 42 44 55 94 67 12 10
55 67 94 44 42 18 12 10
18 42 44 55 94 67 12 10
55 67 94 44 42 18 12 10
67 42 44 55 94 18 12 10 94 67 55 44 42 18 12 10
42 67 44 55 94 18 12 10 67 94 55 44 42 18 12 10
42 55 44 67 94 18 12 10 67 94 55 44 42 18 12 10
94 55 44 67 42 18 12 10
44 55 94 67 42 18 12 10 94 67 55 44 42 18 12 10
44 55 94 67 42 18 12 10