LAK - ćwiczenia nr 2
1. Analiza wydajności algorytmów sortowania
Mamy zbiór elementów z kluczami. Sortujemy wg tych kluczy. Sortowanie jest
stabilne, jeśli zachowuje kolejność elementów o tych samych kluczach.
Wydajność mierzy się liczbą porównań lub zamian w funkcji n.
Proste algorytmy mają wydajność n2, lepsze n log n.
1.1. Sortowanie przez selekcję (Selection-Sort)
Dla każdego i-tego elementu w ciągu trzeba wśród elementów ai, ai+1, . . . , an
znalez
ć najmniejszy i wstawić go w miejsce elementu ai, czyli na koniec posor-
towanego kawałka tablicy.
Tu liczba porównań jest <" n2, ale liczba zamian jest <" n. Jeśli zatem elementy
są duże i trzeba je zamieniać, co jest kosztowne, to Selection-Sort może okazać
się najtańszy. Liczba porównań nie zależy od uporządkowania wejściowego.
Algorithm 1 Selection-Sort
proceduraselection_sort(a(n))
powtarzaj od i = 1don - 1
min �! i
powtarzaj odj �! i + 1don:
ifaj < amin
min �! j
zakończ iterację
zamień(ai, amin)
zakończ iterację
zakończ procedurę
1.2. Sortowanie przez wstawianie - karciane (Insertion-Sort)
Algorithm 2 Insertion-Sort
procedurainsertion_sort(a(n))
powtarzaj odi = 2don
tmp �! ai
j �! i
dopóki (j > 1 oraz aj-1 > tmp) powtarzaj:
aj �! aj-1
j �! j - 1
zakończ iterację
aj �! tmp
zakończ iterację
zakończ procedurę
1
1.3. Sortowanie szybkie (Quick-Sort)
Konstrukcja oparta jest o zasadę  dziel i zwyciężaj : aby posortować tablicę,
dzielimy ją na dwie części (tak by wszystkie elementy lewej części były mniejsze
od wszystkich elementów prawej części) i sortujemy każdą z tych części nieza-
leżnie.
Algorithm 3 Quick-Sort
proceduraquick_sort(a, L, P)
jeśliL e" P
przerwij wykonywanie procedury
w p.p.
S �! L
powtarzaji = L + 1doP
jeśliai < aL
S �! S + 1
zamień(aS, ai)
zakończ iterację
zamień(aS, aL)
quick_sort(a, L, S - 1)
quick_sort(a, S + 1,P)
zakończ procedurę
1.4. Sortowanie przez scalanie (Merge-Sort)
Sortowanie przez scalanie jest również algorytmem typu  dziel i zwyciężaj .
Ideą działania algorytmu jest dzielenie zbioru danych na mniejsze zbiory, aż do
uzyskania n zbiorów jednoelementowych, które same z siebie są posortowane.
Następnie zbiory te są łączone (scalane) w coraz większe zbiory posortowane,
aż do uzyskania jednego, posortowanego zbioru n -elementowego.
Algorithm 4 Merge-Sort
proceduramerge_sort(a, L, P)
jeśliL e" P
przerwij wykonywanie procedury
w p.p.
L+P
S �!
2
merge_sort(a, L, S )
merge_sort(a, S + 1, P)
scal(a, L, S, P) // procedurascal udostępniona przez prowadzącego
zakończ procedurę
Zadanie
Zakoduj w Scilabie trzy wybrane algorytmy sortowania.
Przeprowadz
analizę ich wydajności w przypadku gdy:
1. wejściowa tablica jest uporządkowana rosnąco,
2. wejściowa tablica jest uporządkowana malejąco,
3. wejściowa tablica jest częściowo uporządkowana,
4. wejściowa tablica jest losowa.
Wyniki doświadczeń zbierz w postaci tabelarycznej, a także na wykresach w
skalach liniowo-liniowej i logarytmiczno-logarytmicznej.
2