Porównanie metod sortowania
Sortowanie Liczba porównań
Liczba przesunięć (Pr) dla danych przed sortowaniem
(dane up. losowo)
uporządkowanych:
P
losowo uporządkowanych odwrotnie
uporządkowanych
bubble sort 0
1 3 3
(n2 - n)=const (n2 - n) (n2 - n)
(prosta zamiana)
2 4 2
insertion sort
1
n2 n2
(n2 - n)
(wstawianie)
2(n -1)2
2
4 2
selection sort
1
n2
(wybieranie)
(n2 - n)=const
n ln n
3n
2
4
1
quick sort n2 n2
n logn
logn
6
(szybkie)
Shell sort
n1.5 n1.5
n1.5
n1.5
(Shella)
scalanie
n logn n logn
n logn n logn
Zasada  dziel i zwyciężaj
Polega na dekompozycji problemu na skończoną ilość podproblemów tego samego typu a
następnie połączeniu rozwiązań częściowych częściowych w uzyskanie rozwiązania
globalnego.
Przykłady:
1. Sortowanie szybkie
Zbiór dzieli się na dwie części, dla których występują wywołania rekurencyjne.
Początek: przetwarzanie największego zbioru;
Koniec: przetwarzanie najmniejszych podzbiorów i uzyskanie uporządkowania
2. Sortowanie przez scalanie
Zbiór dzieli się na dwie części, dla których występują wywołania rekurencyjne.
Początek: przetwarzanie największego zbioru;
Koniec: w procesie scalania coraz większych zbiorów uzyskanie uporządkowania
3. Wyszukiwanie binarne
Tablica uporządkowana składająca się z n danych, spośród których poszukujemy elementu x
Algorytm:
1. Jeśli tablica jednoelementowa zakończyć przeszukiwanie
2. Jeśli tablica nie jest jednoelementowa: Podzielić tablicę na dwie połowy element
podziału to p=(lewy+prawy)/2
3. Jeżeli xrekurencyjnie funkcję.
Jeżeli x>tab[p] szukany element x znajduje się w prawej części tablicy. Wywołać
rekurencyjnie funkcję.
t:
p+1
lewy p prawy
t:
p+1
lewy p prawy
int bin(char *t, int x, int lewy, int prawy)
{
if (lewy>prawy) return -1;
else
{ int p=(lewy+prawy)/2;
if (t[p]==x) return p;
else
if (x return bin(t, x, lewy, p-1);
else
return bin(t, x, p+1, prawy);
}
}
Np.:
t[1] t[2] t[3] t[4] t[5] t[6]
Anna Bartek Cezary Damian Krzysztof Tymoteusz
Szukane: Krzysztof;
1. sprawdzenie warunkulewy=prawy (nie jest spełnione=NSP, spełnione=SP)
2. określenie p=t[3] (element podziału) i sprawdzenie warunku x3. wywołanie rekurencyjne dla prawej podtablicy (szukaj(tab, x, 4, prawy))
t[4] t[5] t[6]
Damian Krzysztof Tymoteusz
3a. sprawdzenie warunkulewy=prawy (NSP)
3b. określenie p=5 (element podziału) i sprawdzenie warunku x3c. wywołanie rekurencyjne dla lewej podtablicy (szukaj(tab, x, lewy, 5))
t[4] t[5]
Damian Krzysztof
3ca. sprawdzenie warunkulewy=prawy (NSP)
3cb. określenie p=4 (element podziału) i sprawdzenie warunku x3cc. wywołanie rekurencyjne dla prawej podtablicy (bin(t, x, 5, prawy))
5
t[5]
Krzysztof
3cca. sprawdzenie warunku lewy=prawy (SP) funkcja  bin zwraca TRUE
Złożoność obliczeniowa:
t1=1
tn=t n/2 +1 n>0, n będące potęgą 2 (założenie)
t1=1
t2=2
t4=3
t8=4
tn=log2n+1
1. n=1
t1=log21+1=1 O(logn)
2. t2k=log2(2k)+1 dla k3. t2n=t(2n/2)+1=tn+1=log2n+1+1= log2n+ log22+1=log2(2n)+1
4. Wieże Hanoi
Dane są 3 słupki A, B, C
Początkowo na słupku A n krążków o średnicach wzrastających ku górze, słupki B,C puste
Problem:
Należy przenieść n krążków z A na C według następujących zasad:
1. w każdym kroku można przenieść jeden krążek z jednego słupka na inny
2. krążek nie może znalez
ć się na krążku o mniejszej średnicy
3. słupek B może być używany jako magazyn pomocniczy
Np. n=3
A B C
(liczba krążków)
3 0 0 nr 3 najniżej, nr 2 środkowy, nr 1 najwyżej
2 0 1 po krok 1: nr 1 z A na C
1 1 1 po krok 2: nr 2 z A na B
1 2 0 po krok 3: nr 1 z C na B
0 2 1 po krok 4: nr 3 z A na C
1 1 1 po krok 5: nr 1 z B na A
1 0 2 po krok 6: nr 2 z B na C
0 0 3 po krok 7: nr 1 z A na C
Algorytm:
1. Przenieść n-1 krążków z A na B pozostawiając na słupku A krążek o największej
średnicy
2. Przenieść krążek n o największej średnicy na słupek C
3. Przenieść n-1 krążków z B na C
Algorytm:
1. Przenieść n-1 krążków z A na B pozostawiając na słupku A krążek o największej
średnicy
2. Przenieść krążek n o największej średnicy na słupek C
3. Przenieść n-1 krążków z B na C
Odpowiednie krążki:
A nr 0
B nr 1
C nr 2
void hanoi(int n,int a,int b)
{
"<< b < else
{
hanoi(n-1,a,3-a-b);
cout <<
hanoi(n-1,3-a-b,b);
}
}
wywołanie: hanoi(3, 0, 1) dla n=3
n, A, C
Złożoność obliczeniowa:
t1=1 tn
tn=2t n-1 +1 n>=2 n=1 1 krok
n=2 3 kroki
n=3 7 kroków&
tn=2n-1
1. n=1
t1=1
2. tk=2tk-1+1=2k-1 dla k3. tn=2tn-1+1=2(2n-1-1)+1=2n-1+1-2+1 = 2n-1 O(2n)