Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  proste metody sortowania tablic
16 kwietnia 2009
PROSTE METODY SORTOWANIA TABLIC
1. Wstęp
Sortowaniem (sorting) nazywamy proces ustawiania elementów pewnego niepustego
zbioru według danego porządku (order). Inaczej mówiąc sortowanie polega na ustawianiu
pewnego zbioru skończonego w ciąg.
Aby to zrealizować w rozważanym zbiorze musi być określona relacja liniowego porządku
(patrz Dodatek).
Metody sortowania dzielimy na metody sortowania tablic i metody sortowania plików
sekwencyjnych, przy czym często te klasy metod sortowania nazywamy odpowiednio sorto-
waniem wewnętrznym (internal sorting) i sortowaniem zewnętrznym (external sorting).
Dalej zajmiemy się prostymi algorytmami sortowania tablic. Przyjmiemy, że elementami
zbioru, który chcemy sortować są rekordy, w których jedną składową jest klucz elementu
(key). Klucze są porównywalne, a więc są danymi typu, w którym określono relację liniowego
porządku. Prowadzi to do deklaracji:
type Element is record
Klucz : Typ_Klucza;
Dane : Typ_Danych;
end record;
Składowa Dane zawiera informacje nieistotne przy formułowaniu algorytmów sortowania
tablic i dalej nie będzie brana pod uwagę. Zakładamy też, że klucze elementów są wyzna-
czone.
Tablica, którą chcemy sortować może być następującego typu:
type Tablica is array (Typ_Indeksu range <>) of Element;,
przy czym Typ_Indeksu musi być typem dyskretnym, podtypem dyskretnym, albo zakre-
sem typu dyskretnego (porównaj definicję tablic jednowymiarowych).
Przyjmiemy dalej w tym punkcie, że Typ_Indeksu jest typem Integer.
Mówimy, że tablica
A : Tablica (1..N);
gdzie N jest daną liczbą całkowitą taką, że zakres 1..N nie określa pustej tablicy, jest posor-
towana w porządku rosnącym, jeżeli dla dowolnego indeksu I " 1..(N - 1) mamy
A(I).Klucz d" A(I +1).Klucz.
Jeżeli relację d" zastąpimy relacją e" , to otrzymamy uporządkowanie malejące. Dalej bę-
dziemy się zajmować wyłącznie sortowaniem według porządku rosnącego.
Przypuśćmy, że mamy dwa rekordy R1, R2 umieszczone w A(I) i A(J). Mówimy, że
R1 poprzedza R2, jeżeli I < J.
Jeżeli w nieposortowanej tablicy rekord R1 poprzedza rekord R2 i ich klucze są równe,
czyli R1.Klucz = R2.Klucz, to w tablicy posortowanej metodą stabilną również rekord
R1 poprzedza rekord R2.
Sortowanie zachowujące względne położenie rekordów o tych samych wartościach kluczy
nazywamy sortowaniem stabilnym (stable sorting). Położenie względne może wynikać z
poprzednio wykonanego sortowania według innego klucza (Sedgewick, 1983).
Sortowaniem w miejscu, albo in situ nazywamy sortowanie, w którym tablice
nieuporządkowana i uporządkowana zajmują ten sam obszar pamięci, przy czym do realizacji
algorytmu sortowania dopuszcza się wykorzystanie pewnego, niewielkiego obszaru pomocni-
czego. Inaczej mówiąc, w przypadku sortowania in situ nie wykonuje się kopii sortowanej ta-
blicy.
Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  proste metody sortowania tablic
16 kwietnia 2009
2. Sortowanie przez wybór
Sortowanie przez wybór (selection sort) jest łatwym do zrozumienia algorytmem
sortowania tablic, skutecznym przy ich niewielkich rozmiarach (Sedgewick, 1983).
Przypuśćmy, że mamy daną deklarację
A : Tablica (1..N);,
przy czym tablica wypełniona jest rekordami o wyznaczonych kluczach. Tablicę tę należy
uporządkować rosnąco.
Algorytm sortowania przez wybór rozpoczynamy od wykonania dwóch etapów podstawo-
wych:
1. Wybieramy z tablicy A element o najmniejszej wartości klucza,
2. Zamieniamy go miejscami z A(1).
Następnie powtarzamy te etapy w przypadku tablicy 2..N, czyli N-1 elementowej, 3..N,
czyli N-2 elementowej, aż pozostanie tablica jednoelementowa, zawierająca element o naj-
większym kluczu. Zamiana elementów następuje wtedy, gdy najmniejszy znaleziony klucz
jest mniejszy od klucza elementu, z którym porównujemy klucze elementów nieposortowanej
części tablicy.
Przykład. (Wirth, 2001). Mamy daną tablicę A: Tablica (1..8) z następującymi
kluczami elementów:
1) 44 55 12 42 94 18 6 67 Nc = 7, Ne = 1.
W pierwszym etapie okazuje się, że najmniejszy klucz ma rekord A(7), przy czym
A(7).Klucz < A(1).Klucz. Następuje więc zamiana rekordu A(7) z rekordem A(1).
Wynikiem tego jest tablica z następującym układem kluczy:
2) 6 55 12 42 94 18 44 67 Nc = 6, Ne = 1.
Teraz przeglądamy tablicę w zakresie 2..8. Najmniejszy klucz ma rekord A(3), przy czym
klucz ten jest mniejszy od klucza rekordu A(2). Dokonujemy zamiany rekordów i otrzymu-
jemy ciąg kluczy:
3) 6 12 55 42 94 18 44 67 Nc = 5, Ne = 1.
Postępujemy tak dalej i kolejno dostajemy:
4) 6 12 18 42 94 55 44 67 Nc = 4, Ne = 0.
5) 6 12 18 42 94 55 44 67 Nc = 3, Ne = 1.
6) 6 12 18 42 44 55 94 67 Nc = 2, Ne = 0.
7) 6 12 18 42 44 55 94 67 Nc = 1, Ne = 1.
8) 6 12 18 42 44 55 67 94 Nc = 0, Ne = 0.
Niech Nc (number of comparisons) oznacza liczbę porównań kluczy i niech Ne (number
of exchanges) oznacza liczbę zamian rekordów. Nietrudno zauważyć, że w podanym algoryt-
mie liczba porównań kluczy nie zależy od początkowego ustawienia rekordów i wynosi
1 1
Nc = (n2 -n) = n(n -1)
, (1)
2 2
natomiast liczba zamian rekordów spełnia oszacowanie
Ne d" n -1 , (2)
przy czym w przykładzie Nc = 28 i Ne = 5 d" 7 .
Złożoność czasową algorytmów często oceniamy stosując notację dużego O (big O)
(Aho, Hopcroft, Ullman, 2003; Banachowski, Diks, Rytter, 2006). W przypadku algorytmów
sortowania wewnętrznego miarą ich efektywności czasowej mogą być liczba porównań klu-
czy i liczba przestawień elementów. Mówimy, że algorytm sortowania przez wybór ma zło-
żoność czasową kwadratową ze względu na operację porównywania kluczy, co wyrażamy
Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  proste metody sortowania tablic
16 kwietnia 2009
pisząc O(n2) - wzór (1), natomiast ze względu na operację zamiany rekordów algorytm ten
ma złożoność czasową liniową, co zapisujemy symbolem O(n) - wzór (2).
Zadanie obliczeniowe 1. Napisać, uruchomić i przetestować program w Adzie
implementujący algorytm sortowania przez wybór. Algorytm powinna realizować procedura z
odpowiednio zaprojektowanym interfejsem (parametrami formalnymi). Procedura ta powinna
wyznaczać liczbę porównań kluczy i liczbę zamian elementów oraz prezentować stan sorto-
wanej tablicy po wykonaniu każdych dwóch etapów algorytmu. Wymianę elementów zreali-
zować przy pomocy procedury Wymien, którą należy zadeklarować w odpowiednim obsza-
rze deklaracji. Wykonać też obliczenia dla przypadku posortowanej tablicy i tablicy posorto-
wanej wg porządku malejącego.
Program: Test_Selection_Sort
3. Sortowanie przez wstawianie
Algorytm sortowania przez wstawianie (insertion sort) jest równie prosty jak sortowanie
przez wybór (Sedgewick, 1983; Wirth, 2001) i jest stosowany przez ludzi układających karty
do gry w brydża.
W danym kroku bierzemy pod uwagę jeden element, który wstawiamy w odpowiednie
miejsce wśród elementów które poprzednio ustawiliśmy. Miejsce na wstawiany element
otrzymujemy przesuwając elementy o większych kluczach w prawo.
Przykład. (Wirth, 2001). Niech A: Tablica (1..8) będzie tablicą z następującymi
kluczami elementów:
1) 44 55 12 42 94 18 6 67.
W pierwszym kroku bierzemy pod uwagę drugi element, traktując pierwszy jako tę część
tablicy, która została wcześniej uformowana. Korzystając z lokalnej zmiennej pomocniczej
Temp : Element; tworzymy kopię elementu A(2) i sprawdzamy, czy
A(1).Key > Temp.Key.
Ponieważ w rozważanym przypadku relacja ta jest fałszywa dostajemy układ kluczy jak po-
przednio.
2) 44 55 12 42 94 18 6 67.
Teraz bierzemy pod uwagę element Temp := A(3). Ponieważ
Temp.Klucz < A(2).Klucz,
przesuwamy A(2) na miejsce A(3)i sprawdzamy, czy
Temp.Klucz < A(1).Klucz.
Ponieważ relacja ta jest prawdziwa i osiągnęliśmy początek tablicy przesuwamy A(1) w
miejsce A(2), a w wolne miejsce wstawiamy Temp = A(3). Wynikiem tych operacji jest
następujący układ kluczy:
3) 12 44 55 42 94 18 6 67.
Zauważmy, że proces porównywania kluczy i ewentualnego przesuwania elementów o więk-
szych kluczach wykonywany jest na przemian, a kończymy proces z dwóch powodów:
1. Znaleziono element z kluczem mniejszym od Temp.Klucz,
2. Osiągnięto początek poprzednio ułożonej części tablicy.
Postępując dalej według opisanego schematu kolejno otrzymujemy:
4) 12 42 44 55 94 18 6 67
5) 12 42 44 55 94 18 6 67
6) 12 18 42 44 55 94 6 67
7) 6 12 18 42 44 55 94 67
8) 6 12 18 42 44 55 67 94
Antoni M. Zajączkowski: : Algorytmy i podstawy programowania  proste metody sortowania tablic
16 kwietnia 2009
Zadanie obliczeniowe 2. Napisać, uruchomić i przetestować program w Adzie implementu-
jący algorytm sortowania przez wstawianie. Algorytm powinna realizować procedura z od-
powiednio zaprojektowanym interfejsem (parametrami formalnymi). Procedura ta powinna
wyznaczać liczbę przesunięć (zamian) elementów oraz prezentować stan sortowanej tablicy
po wykonaniu każdego etapu algorytmu. Wykonać też obliczenia dla przypadku posortowanej
tablicy i tablicy posortowanej wg porządku malejącego.
Program: Test_Insertion_Sort
Dodatek. Przypomnienie wybranych wiadomości z podstaw matematyki.
DEFINICJA. Niech S oznacza zbiór niepusty. Relacją częściowego porządku, albo
częściowym porządkiem (partial order relation, partial order) w S nazywamy relację
dwuargumentową (binarną), którą oznaczamy d" i która posiada następujące własności:
R1. x d" x dla każdego x " S - zwrotność (reflexivity),
R2. Jeżeli x d" y i y d" x , to x = y - antysymetria (antisymmetry),
R3. Jeżeli x d" y i y d" z , to x d" z - przechodniość (transitivity).
DEFINICJA. Niepusty zbiór S , w którym określono relację częściowego porządku nazy-
wamy zbiorem częściowo uporządkowanym (partially ordered set).
DEFINICJA. Dwa elementy x y " S nazywamy porównywalnymi (comparable), jeżeli
x d" y , albo y d" x .
Z definicji relacji częściowego porządku nie wynika, że każde dwa elementy zbioru S są
porównywalne. Jeżeli zbiór częściowo uporządkowany posiada własność
R4. Każde dwa elementy zbioru S są porównywalne,
to częściowy porządek nazywamy relacją porządku liniowego, albo relacją porządku peł-
nego (linear order relation, total order relation), a zbiór nazywamy zbiorem liniowo upo-
rządkowanym, albo zbiorem w pełni uporządkowanym (linearly ordered set, totally
ordered set).
Stosowana jest też nazwa łańcuch (chain).
LITERATURA
Aho, A.V, J.E. Hopcroft, J.D. Ullman. (2003). Algorytmy i struktury danych. Helion, Gliwice,
Polska (tłum. z ang.).
Banachowski, L., K. Diks, W. Rytter. (2006). Algorytmy i struktury danych. WNT, Warszawa
(wyd. 5).
Birkhoff, G. i T.C. Bartee. (1983). Współczesna algebra stosowana. PWN, Warszawa (tłum. z
ang.).
Sedgewick, R. (1983). Algorithms. Addison-Wesley, Reading, Mass.
Wirth, N. (2001). Algorytmy + struktury danych = programy. WNT, Warszawa (tłum. z ang.).