Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 1
Proste algorytmy sortowania
Naturalne sformułowanie problemu sortowania:
Dane wejściowe:
Lista obiektów L= ( a0, . . . , an-1 ) pewnego ustalonego typu, w którym jest
zdefiniowany liniowy porządek "≤".
Dane wyjściowe:
Lista L' = ( b0, . . . , bn-1 ) będąca permutacją listy L taką, Ŝe bi ≤ bi+1,
dla i = 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.
W tym wykładzie zostaną przedstawione trzy proste algorytmy sortowania:
sortowanie bąbelkowe (przez zamianę), przez wybór i przez wstawianie. 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.
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 2
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.
Niektóre algorytmy sortowania zachowują poprzednie uporządkowanie danych
o równych kluczach.
Wszystkie algorytmy sortowania, które omówimy w tym wykładzie składają się
z dwóch kroków, które wykonujemy tak długo, aŜ dane nie zostaną posortowane:
(1) Porównaj dwa elementy
(2) Zamień miejscami dwa elementy, albo skopiuj jeden w miejsce drugiego.
Sortowanie bąbelkowe
Idea:
Dana jest lista N elementów: a 0 , a 1 , ... , a n-1
Zaczynając od początku listy porównujemy elementy na pozycjach 0 i 1.
JeŜeli stojący na pozycji 0 jest większy niŜ element na pozycji 1, zamieniamy je
miejscami, w przeciwnym przypadku nic nie robimy (nie zamieniamy elementów).
Następnie porównujemy elementy z pozycji 1 i 2. I znów, gdy ten pierwszy jest
większy, zamieniamy je miejscami. Kontynuujemy porównanie i ewentualne zamiany,
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.
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 3
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
II faza: 3, 4, 1, 2
3, 1, 4, 2
3, 1, 4, 2
3, 1, 2, 4 koniec II fazy
III faza: 3, 1, 2
1, 3, 2
1, 2, 3 koniec III fazy
IV faza: 1, 2
1, 2 koniec IV fazy
BubbleSort() {
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ę miejscami elementów na
pozycjach ‘p’ i ‘q’ i ma postać:
swap( p, q ) {
temp = a[p];
a[p] = a[q];
a[q] = temp;
}
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 4
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
T(n) = 1/2 * n2 + O(1)
T(n) = Θ(n2)
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
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).
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 5
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.
PoniŜej przedstawiono program bubbleSort.java ilustrujący sortowanie bąbelkowe.
// bubbleSort.java
// demonstruje sortowanie bąbelkowe
class ArrayBub
{
private long[] a; // referencja do tablicy
private int nElems; // licznik elementów
//--------------------------------------------------------------
public ArrayBub(int max) { // konstruktor
a = new long[max]; // tworzymy tablicę
nElems = 0; // na razie brak elementów
}
//--------------------------------------------------------------
public void insert(long value) { // wstawienie elementu do tablicy
a[nElems] = value; // wstawiamy element
nElems++; // zwiększamy licznik elementów
}
//--------------------------------------------------------------
public void display(){ // wypisuje zawartość tablicy
for(int j=0; j<nElems; j++) // dla kaŜdego elementu...
System.out.print(a[j] + ", "); // ...wypisujemy jego wartość
System.out.println("");
}
//--------------------------------------------------------------
public void bubbleSort() {
for(int k=nElems-1; k>1; k--) // pętla zewnętrzna (malejąca)
for(int j=0; j<k; j++) // pętla wewnętrzna (rosnąca)
if( a[j] > a[j+1] ) // zła kolejność?
swap(j, j+1); // no to zamiana
} // koniec bubbleSort()
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 6
//--------------------------------------------------------------
private void swap(int one, int two) {
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
//--------------------------------------------------------------
} // koniec klasy ArrayBub
class BubbleSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // rozmiar tablicy
ArrayBub arr; // referencja do tablicy
arr = new ArrayBub(maxSize); // tworzymy tablicę
arr.insert(77); // wstawiamy 10 elementów
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // wypisujemy je
arr.bubbleSort(); // sortujemy bąbelkowo
arr.display(); // i znów wypisujemy
} // koniec main()
} // koniec klasy BubbleSortApp
NS 27.03.09
Metoda prostego wyboru (selection sort)
Idea:
Dla i=0, ..., N-2 powtarzaj kroki,
(1) znajdź 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 znajduje element najmniejszy i zamienia go z pierwszym
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 7
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 min większe …
min = j ; // ... mamy nowe minimum
swap (k, min); // zamiana
} // koniec pętli wewnętrznej
} // koniec SelectionSort ()
Analiza złoŜoności identyczna jak dla metody bąbelkowej:
Liczba operacji porównań = (n-1) + (n-2) + . . . + 1 = n*(n-1) / 2
T(n) = 1/2 * n2 – 1/2 * n
T(n) = 1/2 * n2 + O(1)
T(n) = Θ(n2)
Czyli: zarówno w pesymistycznym, jak i średnim przypadku, liczba porównań wynosi
ok. 1/2 n2.
Zaleta:
Wykonuje tylko n-1 zamian – metoda zalecana w przypadku niedługich tablic z
długimi rekordami
Wada: Nie jest stabilne.
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’
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 8
1, 2, 3, 5, 7’’, 7’
czyli w wyniku sortowania kolejność siódemek zostanie zmieniona.
PoniŜej przedstawiono program SelectSort.java ilustrujący działanie sortowania przez
wybór.
// SelectSort.java
// demonstruje algorytm sortowania przez wybór
class ArraySel
{
private long[] a; // referencja do tablicy
private int nElems; // liczba elementów w tablicy
//--------------------------------------------------------------
public ArraySel(int max) // konstruktor
{
a = new long[max]; // tworzymy tablicę
nElems = 0; // na razie brak elementów
}
//--------------------------------------------------------------
public void insert(long value) // wstawienie element do tablicy
{
a[nElems] = value; // wstawiamy element
nElems++; // zwiększenie licznika elementów
}
//--------------------------------------------------------------
public void display() // wypisanie zawartości tablicy
{
for(int j=0; j<nElems; j++) // dla kaŜdego elementu...
System.out.print(a[j] + " "); // ...wypisujemy jego wartość
System.out.println("");
}
//--------------------------------------------------------------
public void selectionSort()
{
int k, j, min;
for(k=0; k<nElems-1; k++) // pętla zewnętrzna
{
min = k; // wartość minimum
for(j=k+1; j<nElems; j++) // pętla wewnętrzna
if(a[j] < a[min] ) // jeŜeli min większe...
min = j; // ...mamy nowe minimum
swap(k, min); // zamiana
} // koniec pętli zewnętrznej
} // koniec selectionSort()
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 9
//--------------------------------------------------------------
private void swap(int one, int two)
{
long temp = a[one];
a[one] = a[two];
a[two] = temp;
}
//--------------------------------------------------------------
} // koniec klasy ArraySel
class SelectSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // rozmiar tablicy
ArraySel arr; // referencja do tablicy
arr = new ArraySel(maxSize); // tworzymy tablicę
arr.insert(77); // wstawiamy 10 elementów
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // wypisujemy je
arr.selectionSort(); // sortujemy przez wybór
arr.display(); // i znów wypisujemy
} // koniec main()
} // koniec klasy SelectSortApp
Metoda prostego wstawiania (insertion sort)
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 2 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.
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 10
Idea:
Wykonując kroki dla i = 1, ... , n – 1 , w i-tym kroku wstaw element A[i] na
właściwe miejsce w częściowo posortowanym fragmencie A[0 .. i-1], zawierającym
elementy początkowo połoŜone w A[0 .. i-1], przesuwając elementy większe od A[i]
w prawo o 1 pozycję.
Uzyskujemy w ten sposób posortowany fragment od A[0] do A[i].
Przykład.
Tablica wejściowa: 3, 2, 6, 4, 1, 7
2, 3, 6, 4, 1, 7
2, 3, 6, 4, 1, 7
2, 3, 4, 6, 1, 7
1, 2, 3, 4, 6, 7
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
tmp = A[k] ; // kopiujemy wyróŜniony element
while ( j >= 0 && tmp < A[j] ) {// dopóki elementy są większe
// niŜ tmp
A[j+1] = A[j]; // przesuń elementy w prawo
j-- ; // przesuń się w lewo
}
// j==-1 lub tmp >= A[j]
A[j+1] = tmp ; // wstaw wyróŜniony element
}
ZłoŜoność pesymistyczna (ciąg posortowany malejąco na wejściu) identyczna jak da
poprzednich.
Średnia: dwukrotnie lepsza, czyli w przypadku pesymistycznym ok. 1/2 n2 porównań
w przypadku średnim ok. 1/4 n2 porównań.
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 11
Zalety:
1. Stabilność
2. Średnio dwukrotnie szybszy niŜ inne proste metody
W sumie jest N*(N-1)/2 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)/4.
3. Optymalny 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 Θ(n2)
2. wartownik, dwie wersje
(a) A[0] = - nieskończoność
(b) na początku w A[0] ustaw najmniejszy element tablicy, będzie spełniał
rolę wartownika. W pętli while wystarczy warunek tmp < A[j], pętla
zewnętrzna for moŜe zacząć od k=2.
PoniŜej przedstawiono algorytm w wersji 2b
k = findIndMin(); // k takie Ŝe A[k] dowolny najmniejszy element
swap(0,k); // zamień (A[0], A[k])
for (j = 2; j < n; j++) // n=Length(A)
{ tmp = A[j]
// wstaw A[j] do posortowanej A[0..j-1]
i = j-1
while (tmp < A[i])
{
A[i+1] = A[i] // przesuń ku końcu tablicy
i = i-1
} // tmp >= A[i]
A[i+1] = tmp
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 12
}
PoniŜej przedstawiono program InsertSort.java, który ilustruje algorytm sortowania
przez proste wstawianie.
// insertSort.java
// demonstruje sortowanie przez wstawianie
//--------------------------------------------------------------
class ArrayIns
{
private long[] a; // referencja do tablicy
private int nElems; // licznik elementów tablicy
//--------------------------------------------------------------
public ArrayIns(int max) // konstruktor
{
a = new long[max]; // tworzymy tablicę
nElems = 0; // na razie brak elementów
}
//--------------------------------------------------------------
public void insert(long value) // wstawienie elementu do tablicy
{
a[nElems] = value; // wstawienie elementu
nElems++; // zwiększenie licznika
}
//--------------------------------------------------------------
public void display() // wypisuje elementy tablicy
{
for(int j=0; j<nElems; j++) // dla kaŜdego elementu...
System.out.print(a[j] + " "); // ...wypisujemy jego wartość
System.out.println("");
}
//--------------------------------------------------------------
public void insertionSort()
{
int j, k;
for(k=1; k < nElems; k++) // k to pierwszy nieposortowany element
{
long tmp = a[k]; // kopiujemy wyróŜniony element
j = k-1; // zaczynamy od k-1
while(j>=0 && a[j] > tmp) // dopóki elementy są większe niŜ temp
{
a[j+1] = a[j]; // przesuwamy elementy w prawo
Algorytmy i struktury danych – wykład 3 Sortowania proste Strona: 13
j--; // przesuwamy się w lewo
}
a[j+1] = tmp; // wstawiamy wyróŜniony element
} // koniec pętli for
} // koniec insertionSort()
//--------------------------------------------------------------
} // koniec klasy ArrayIns
class InsertSortApp
{
public static void main(String[] args)
{
int maxSize = 100; // rozmiar tablicy
ArrayIns arr; // referencja do tablicy
arr = new ArrayIns(maxSize); // tworzymy tablicę
arr.insert(77); // wstawiamy 10 elementów
arr.insert(99);
arr.insert(44);
arr.insert(55);
arr.insert(22);
arr.insert(88);
arr.insert(11);
arr.insert(00);
arr.insert(66);
arr.insert(33);
arr.display(); // wypisujemy elementy
arr.insertionSort(); // sortujemy je
arr.display(); // i znów wypisujemy
} // koniec main()
} // koniec klasy InsertSortApp