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