IIUJ Metody programowania Strona: 1
Wykład 3.
Proste algorytmy sortowania
Problem sortowania można sformułować następująco:
Dana jest lista obiektów L= ( a 0, . . . , a n-1 ) pewnego ustalonego typu,
w którym jest zdefiniowany liniowy porządek "Ł�".
Sortowanie polega na permutowaniu tych obiektów aż do chwili otrzymania listy
L' = ( b 0, . . . , b n-1 ) takiej, że b k Ł� b k+1, dla k = 0, . . . , n-2.
W ogólnym przypadku sortowanie danych w pewnym zbiorze jest krokiem
wstępnym przed wyszukiwaniem zadanej wartości. Jak pokazaliśmy w poprzednim
wykładzie, można wówczas zastosować wyszukiwanie binarne, które można
zastosować tylko dla posortowanych danych. Jest ono dużo szybsze niż wyszukiwanie
liniowe.
Często obiekty listy są strukturami (rekordami) wówczas o kolejności decyduje
wartość wyróżnionego pola struktury: klucza.
Pod względem sposobu przechowywania danych wyróżniamy następujące warianty
problemu sortowania:
q� � Sortowanie wewnętrzne (sortowanie tablic)
Lista reprezentowana za pomocą tablicy: A[0], . . . , A[n-1]
W tym przypadku tablica jest pamiętana w pamięci wewnętrznej o dostępie
bezpośrednim oraz czas dostępu do elementu A[i] jest stały, niezależny od
rozmiaru danych n
q� � Sortowanie zewnętrzne (sortowanie plików)
Lista jest plikiem w pamięci zewnętrznej.
Wykorzystuje się tylko stałą (możliwe, że bardzo małą) ilość pamięci wewnętrznej.
W tym przypadku dostęp do kolejnych elementów jest sekwencyjny, tzn. dostęp
do i-tego elementu wymaga przeglądnięcia poprzedzających go i-1 elementów.
IIUJ Metody programowania Strona: 2
W tym wykładzie zostaną przedstawione trzy proste algorytmy:
o sortowania przez zamianę (BubbleSort),
o sortowania przez wybór (SelectionSort),
o sortowania przez wstawianie (InsertionSort).
Algorytmy te są łatwe do zrozumienia i choć są relatywnie mało efektywne,
bywają w pewnych warunkach bardziej wydajne niż algorytmy złożone.
Przykładowo dla małych zestawów danych lub danych  prawie
posortowanych sortowanie przez wstawianie jest często bardziej efektywne niż
uważany za najlepszy algorytm quicksort.
Często danymi poddawanymi sortowaniu są struktury (rekordy), wówczas o
kolejności decyduje wartość wyróżnionego pola struktury: klucza.
Sortowanie stabilne
Metoda sortowania jest stabilna, jeśli zachowuje względną kolejność
elementów o jednakowych kluczach.
Na przykład możemy mieć dane pracowników posortowane
alfabetycznie względem nazwiska. Następnie chcemy posortować dane
według imion, ale tak by osoby o tych samych imionach zachowywały
kolejność alfabetyczną według nazwisk.
Inny przykład: sortowanie par liczb względem pierwszej liczby w parze.
We:
(3, 1) (2, 1) (3, 4) (1, 3) (3, 2) (2, 4) (1, 1)
wszystkie pary są odróżnialne
prawidłowe sortowanie względem pierwszej liczby w parze, ale niestabilne
może dać np.
(1, 1) (1, 3) (2, 1) (2, 4) (3, 2) (3, 4) (3, 1)
sortowanie stabilne względem pierwszej liczby w parze daje:
(1, 3) (1, 1) (2, 1) (2, 4) (3, 1) (3, 4) (3, 2)
Niektóre z podanych dalej algorytmów sortowania zachowują poprzednie
uporządkowanie danych o równych kluczach.
IIUJ Metody programowania Strona: 3
Wszystkie algorytmy sortowania, które omówimy w tym wykładzie składają się
z dwóch kroków, które wykonujemy dopóki, dopóty dane nie zostaną posortowane:
(1) Porównaj dwa obiekty
(2) Zamień miejscami dwa obiekty, albo skopiuj jeden w miejsce drugiego.
Sortowanie przez prostą zamianę (Bubble_Sort)
Idea: Dana jest lista n elementów: a[0] , a[1] , ... , a[n-1]
Zaczynając od początku listy porównujemy kolejne pary elementów. Jeżeli pierwszy
element pary jest większy niż element drugi, zamieniamy je miejscami, w przeciwnym
przypadku nic nie robimy (nie zamieniamy elementów). Kontynuujemy porównanie i
ewentualne zamiany następnych par elementów, dopóki nie osiągniemy końca listy.
Cały ten proces będziemy nazywać fazą, w jej wyniku na koniec listy, czyli na
pozycję n-1 zostanie przesunięty element największy na liście.
W dalszym ciągu będziemy wykonywać od początku listy drugą fazę, w której
porównujemy i ewentualnie zamieniamy sąsiednie elementy, ale tym razem
zakończymy ten proces na przedostatnim elemencie, ponieważ wiemy, że na
ostatniej pozycji stoi element największy. Po zakończeniu tej fazy na przedostatniej
pozycji znajdzie się element mniejszy od ostatniego, ale większy od elementów
poprzednich.
W ten sposób na pozycjach n-2 i n-1 znajdą się już elementy posortowane.
To postępowanie kontynuujemy, aż wszystkie elementy będą posortowane,
przy czym każda kolejna faza kończy się na pozycji o 1 wcześniejszej niż poprzednia.
Przykład.
Tablica wejściowa: 7, 3, 4, 1, 2
I faza: 7, 3, 4, 1, 2
3, 7, 4, 1, 2
3, 4, 7, 1, 2
3, 4, 1, 7, 2
3, 4, 1, 2, 7 koniec I fazy
IIUJ Metody programowania Strona: 4
II faza: 3, 4, 1, 2, 7
3, 1, 4, 2, 7
3, 1, 4, 2, 7
3, 1, 2, 4, 7 koniec II fazy
III faza:3, 1, 2, 4, 7
1, 3, 2, 4, 7
1, 2, 3 , 4, 7 koniec III fazy
IV faza:1, 2, 3 , 4, 7
1, 2, 3 , 4, 7 koniec IV fazy
BubbleSort() { // sortowanie przez zamianę (bąbelkowe)
for ( k = n-1 ; k >=1; k--) // pętla zewnętrzna (malejąca)
for ( j = 0 ; j < k; j++) // pętla wewnętrzna (rosnąca)
if( a[j] > a[j+1] ) // zła kolejność
swap (j, j+1) ; // zamiana elementów
}
Przy czym operacja swap(p, q), wykonuje zamianę (przestawienie) miejscami
elementów na pozycjach p i q i ma postać:
swap( p, q ) {
temp = a[p]; a[p] = a[q]; a[q] = temp;
}
Złożoność sortowania bąbelkowego:
Operacjami dominującymi są porównania wykonywane w pętli wewnętrznej.
Jest ich:
(n-1) + (n-2) + . . . + 1 = (1+n-1)*(n-1) / 2 = n*(n-1) / 2
Zatem pesymistyczna złożoność czasowa wynosi
T(n) = 1/2 * n2  1/2 * n = 1/2 * n2 + O(1)
T(n) = Q�(n2)
IIUJ Metody programowania Strona: 5
Złożoność średnia: identyczna jak pesymistyczna, czyli liczba porównań
pesymistycznie i średnio ok. 1/2 n2.
Zamian jest mniej niż porównań, gdyż elementy są zamieniane miejscami tylko
wtedy, gdy to konieczne. Dla losowego wybranego zbioru elementów zamiana jest
potrzebna średnio w połowie badanych przypadków, więc będzie około ź n2.
Ale w najgorszym przypadku, gdy dane są ułożone w odwrotnym przypadku,
zamiana jest konieczna po każdym porównaniu.
Metoda sortowania bąbelkowego jest stabilna i jest to chyba jedyna obok
prostoty jej zaleta.
Możliwe modyfikacje usprawniające:
�� � zapamiętanie ostatnio wykonanej zamiany, w kolejnej iteracji pętli zewnętrznej
ustawiać koniec pętli wewnętrznej na zapamiętane miejsce.
�� � zapamiętanie, czy w pętli wewnętrznej potrzebna była zamiana, jeśli nie, to tablica
jest uporządkowana i można zakończyć (nie wykonuje się następnych faz).
�� � sortowanie mieszane: kolejne fazy wykonuje się rozpoczynając porównania
elementów na przemian, raz od początku, drugi raz od końca tablicy. Pozwala to
na przyspieszenie sortowania w przypadkach tablic, np. 9, 1, 2, 3, 4, 5, 0
Niezmienniki
W wielu algorytmach istnieją pewne warunki, które są spełnione przez cały
czas działania algorytmu. Te warunki nazywane są niezmiennikami (ang. invariant).
Poznanie niezmienników może być pomocne w zrozumieniu zasady działania
algorytmu, może też przydać się przy testowaniu i wyszukiwaniu błędów. Na przykład
po wykonaniu każdej instrukcji możemy sprawdzać prawdziwość niezmiennika i
sygnalizować błąd, jeżeli warunek nie jest spełniony.
W algorytmie BubbleSort niezmiennik jest następujący:
 elementy o indeksach większych niż zmienna k są posortowane .
Pozostaje on prawdziwy przez cały czas działania algorytmu.
IIUJ Metody programowania Strona: 6
Metoda prostego wyboru (Selection Sort)
Idea:
Dla i=0, ..., n-2 powtarzaj kroki,
(1) znajdz
najmniejszy element spośród a[i], . . . , a[n-1]
(2) zamień go z elementem a[i];
Przykład: Tablica wejściowa: 3, 2, 4, 9, 1, 7
3, 2, 4, 9, 1, 7 znajduje element najmniejszy i zamienia go z pierwszym
1, 2, 4, 9, 3, 7 znajduje element najmniejszy i zamienia go z drugim
1, 2, 4, 9, 3, 7 znajduje element najmniejszy i zamienia go z trzecim
1, 2, 3, 9, 4, 7 znajduje element najmniejszy i zamienia go z czwartym
1, 2, 3, 4, 9, 7 znajduje element najmniejszy i zamienia go z piątym
1, 2, 3, 4, 7, 9
SelectionSort() { // n=Length(a)
for (k = 0; k < n-1; k++ ) { // pętla zewnętrzna
min = k; // indeks wartości minimalnej
for (j = k+1; j < n; j++) // pętla wewnętrzna
if (a[j] < a[ min] ) // jeżeli a[min] większe &
min = j ; // ... mamy nowe minimum
swap (k, min); // zamiana elementów
} // koniec pętli wewnętrznej
} // koniec SelectionSort()
IIUJ Metody programowania Strona: 7
Analiza złożoności identyczna jak dla metody bąbelkowej:
Liczba operacji porównań elementów= (n-1) + (n-2) + . . . + 1 = n*(n-1) / 2
T(n) = � * n2  � * n = � * n2 + O(1)
T(n) = Q�(n2)
Czyli: zarówno w pesymistycznym, jak i średnim przypadku, liczba porównań wynosi
ok. 1/2 n2.
Zaleta: Wykonuje tylko n-1 przestawień  metoda zalecana w przypadku niedługich
tablic z długimi rekordami
Wada: Metoda nie jest stabilna.
Na przykład dla ciągu: 7 , 3, 2, 7  , 5, 1 sortowanie wykona następujące
przekształcenia:
7 , 3, 2, 7  , 5, 1
1, 3, 2, 7  , 5, 7
1, 2, 3, 7  , 5, 7
1, 2, 3, 5, 7  , 7
czyli w wyniku sortowania kolejność siódemek zostanie zmieniona.
Kosztem zwiększenia współczynnika proporcjonalności złożoności, można ten
algorytm uczynić stabilnym co proponuję zrobić jako ćwiczenie.
Metoda przez proste wstawianie (InsertionSort)
W większości przypadków sortowanie przez wstawianie (ang. insertion sort)
jest najlepszym z trzech podstawowych algorytmów sortowania. Jego złożoność
czasowa to nadal O(n2), ale w normalnych sytuacjach jest około dwa razy szybsze niż
sortowanie bąbelkowe i trochę szybsze niż sortowanie przez wybór.
Sortowanie przez wstawianie jest często używane jako końcowa faza bardziej
skomplikowanych algorytmów sortowania, jak na przykład quicksort.
Idea:
Wykonując kroki dla k = 1, ... , n 1 , w k-tym kroku wstaw element a[k] na
właściwe miejsce w częściowo posortowanym fragmencie a[0] ... a[k-1],
przesuwając elementy większe od a[k] w prawo o 1 pozycję.
Uzyskujemy w ten sposób posortowany fragment od a[0] do a[k].
IIUJ Metody programowania Strona: 8
Przykład.
Tablica wejściowa: 3, 2, 6, 4, 1, 7
krok1: zaczynamy od elemetu 2 i wstawiamy go na początek
tmp
3 1
3, 2, 6, 4, 1, 7
2
2, 3, 6, 4, 1, 7
krok2: element 6 jest na właściwej pozycji
2, 3, 6, 4, 1, 7
krok3: element 4 przesuwa się przed 6
2, 3, 4, 6, 1, 7
krok4: element 1 przesuwa się na początek
tmp
3 1
2, 3, 4, 6, 1, 7
2 2 2 2 jak długo elementy stojące przed 1 są większe od 1
1, 2, 3, 4, 6, 7
krok5: element 7 jest na właściwej pozycji
1, 2, 3, 4, 6, 7
InsertionSort () { // n=Length(a)
for ( k =1; k < n ; k++) { // pętla zewnętrzna, k to pierwszy nieposortowany
j = k  1 ; // zaczynamy od elementu k-1
v = a[k] ; // kopiujemy wyróżniony element do zmiennej v
while ( j >= 0 && v < a[j] ) // dopóki v jest mniejszy niż a[j]
{ // i nie osiągnięty został początek tablicy
a[j+1] = a[j]; // przesuń element w prawo
j-- ; // sprawdz
poprzedni element
} // niezmiennik: (j==-1) lub (v >= a[j])
a[j+1] = v ; // wstaw wyróżniony element za a[j]
}
IIUJ Metody programowania Strona: 9
Analiza metody prostego wstawiania.
W k-tym kroku pętli:
q� � Liczba Po k porównań elementów wynosi co najmniej 1,
co najwyżej k-1 oraz średnio k/2.
q� � Liczba Pr k przesunięć (podstawień obiektów) wynosi Po k +1.
Wynika stąd, że liczby porównań i przesunięć są następujące:
q� � Po min = n-1 Pr min = n (tablica uporządkowana)
q� � Po max= � (n2-n) Pr max= � (n2+n)  1 (tablica uporządkowana odwrotnie)
Tak więc złożoność pesymistyczna (ciąg posortowany malejąco na wejściu) jest
identyczna jak dla poprzednich metod, czyli w przypadku pesymistycznym ok. 1/2 n2
porównań.
Średnio: dwukrotnie lepsza, ok. ź n2 porównań. W sumie jest � n*(n-1)
porównań, ponieważ w każdym przejściu, zanim znajdziemy miejsce do wstawienia
elementu wykonuje się średnio tylko połowa z maksymalnej liczby porównań,
możemy podzielić otrzymaną wartość przez 2, co daje ź n*(n-1).
Zalety metody:
1. Stabilność
2. Średnio dwukrotnie szybsza niż inne proste metody.
3. Optymalna dla ciągów prawie posortowanych
Możliwe usprawnienia:
1. Wyszukiwanie miejsca do wstawienia metodą połówkową  liczba porównań
maleje do n log n, liczba przesunięć dalej Q�(n2)
Niestety, przesuwanie obiektów i związanych z nimi informacji jest przeważnie o
wiele bardziej czasochłonne niż porównywanie kluczy.
2. Na początku w a[0] ustaw najmniejszy element tablicy, będzie spełniał rolę
wartownika. W pętli while wystarczy warunek v < a[j], pętla zewnętrzna for
może zacząć od k=2. (wykład 1)
IIUJ Metody programowania Strona: 10
Porównanie prostych metod sortowania
1. Powyższe sortowania pomimo prostoty w praktyce mogą być stosowane tylko
dla niewielkich tablic a (n=Length(a)<20).
2. Sortowanie bąbelkowe jest najmniej efektywne.
3. Sortowanie przez wybór minimalizuje liczbę przestawień,
ale liczba porównań jest taka sama jak w sortowaniu bąbelkowym.
4. Sortowanie przez wstawianie jest najbardziej efektywne z tych
metod (średnio dwukrotnie), jest najlepsza w przypadkach tablic
 prawie posortowanych.
Pod względem wykorzystania pamięci wszystkie trzy metody wykonują
sortowanie  w miejscu , co oznacza, że poza tablicą wejściową, wszystkie
metody używają jednej, dodatkowej zmiennej, aby tymczasowo
przechować zamienianą wartość.
Na koniec przedstawimy w Javie metodę sortowania przez proste
wstawianie dla tablic obiektów, gdzie kluczem względem, którego
realizowany jest proces sortowania jest łańcuch znakowy, np. nazwisko w
klasie Osoba.
class Osoba
{
private String nazwisko; // nazwisko
private String imie; // imię
private int wiek; // wiek
//---------------------------------------------------------
public Osoba(String nazw, String im, int a)
{ // konstruktor
nazwisko = nazw;
imie = im;
wiek = a;
}
//----------------------------------------------------------
public void displayOsoba()
{
System.out.print(" Nazwisko: " + nazwisko);
System.out.print(", Imie: " + imie);
System.out.println(", Wiek: " + wiek);
}
//----------------------------------------------------------
public String getNazw() // pobierz nazwisko
IIUJ Metody programowania Strona: 11
{
return nazwisko; // do wyszukiwania
}
} // koniec klasy Osoba
//----------------------------------------------------------
class DataArray
{
private Osoba[] a; // referencja do tablicy
private int n; // liczba elementów tablicy
public DataArray(int max) { // konstruktor
a = new Osoba[max]; // tworzymy tablicę
n = 0; // na razie brak elementów
}
public void insertionSort(){
int j, k;
for(k=1; k Osoba v = a[k]; // k to pierwszy nieposortowany
j = k-1; // zaczynamy od k-1
while(j>=0 && // póki v.getNazw < a[j].getNazw
a[j].getNazw().compareTo(v.getNazw()) > 0)
{
a[j+1] = a[j]; // przesuwamy element w prawo
j--; // przesuwamy się w lewo
}
a[j+1] = v; // wstawiamy v na pozycję właściwą
} // koniec pętli for
} // koniec insertionSort()
& & }
W powyższej metodzie porównanie nazwisk dwóch osób wykonuje wyrażenie:
a[j].getNazw( ).compareTo (v.getNazw( ) ) > 0.
Metoda compareTo() zwraca wartość całkowitą, której znak odpowiada
relacji leksykograficznej między obiektem String, na którym została wywołana, a
obiektem, który został przekazany jako argument.
Poniższa tabelka ilustruje wyniki jej działania:
s1.compareTo(s2)
zwraca wartość
s1 mniejsze s2
< 0
s1 równe s2
0
s1 większe s2
> 0