1
Algorytmy i Struktury Danych
wykład 3
Algorytmy sortowania cz.1
1
Algorytmy i Struktury Danych
wykład 3
Algorytmy sortowania cz.1
2/31
Definicja sortowania
proces układania, porządkowania
elementów w określonej kolejności,
według określonego kryterium (klucza)
3/31
Definicja sortowania (2)
elementy sortowane:
e
1
, e
2
, e
3
,…,e
i
,…, e
n
operacja sortowania → wyznaczanie permutacji
na obiektach sortowanych do momentu
osiągnięcia ich uporządkowania spełniającego
dla określonej funkcji porządkującej f warunek:
f(e
(1)
)
≤
f(e
(2)
)
≤
f(e
(3)
)
≤
…
≤
f(e
(i)
)
≤
…
≤
f(e
(n)
)
4/31
Sortowanie - zastosowanie
jest jednym z ważniejszych i często
spotykanych operacji w przetwarzani danych
sortowanie może być stosowane w celu
łatwiejszego wyszukania lub wybrania
pewnych elementów sortowanych danych
5/31
Ogólny podział metod sortowania
sortowanie wewnętrzne
→ sortowanie tablic,
zwykle przechowywanych w pamięci
operacyjnej komputera, wszystkie elementy
sortowane są widoczne łatwo dostępne
sortowanie zewnętrzne
→ sortowanie plików,
zwykle przechowywanych w pamięci
zewnętrznej komputera, widoczne są tylko
elementy leżące na wierzchu stosu
6/31
Określanie efektywności
algorytmów sortowania
liczba elementarnych operacji, będąca
funkcją liczby sortowanych elementów:
liczba porównań
liczba przesunięć
przykłady klas algorytmów sortowania
O(N
2
) – proste algorytmy, nie nadają się do
sortowania dużych tablic
O(NlogN) – zaawansowane, wykorzystywane
do sortowania dużych tablic
7/31
Porównanie liczby operacji
algorytmów klas N∙logN oraz N
2
0
5000
10000
15000
20000
25000
30000
35000
40000
45000
0
2000
4000
6000
8000
10000
12000
0
20000000
40000000
60000000
80000000
100000000
120000000
NlogN
N2
8/31
Sortowanie „przez wstawianie”
ustawienie indeksu na elemencie o numerze j
przypisanie wartości elementu e(j) do
zmiennej tymczasowej
porównanie wartości tymczasowej e(j) z e(j-1)
jeżeli element e(j-1) > e(j) to:
element e(j-1) staje się elementem e(j)
indeks j zmniejsza się o 1
ponowne sprawdzenie wartości tymczasowej i
elementu e(j-1)
umiejscowienie sprawdzanego elementu
9/31
Sortowanie „przez wstawianie”
2
5
7
4
8
1
9
elementy posortowane
elementy nieposortowane
sortowany element
ostateczna pozycja
sortowanego
elementu
10/31
Sortowanie „przez wstawianie”
void sort_wstaw(int t[],int r)
{
int j,wtemp;
for(int i=0;i<r;i++)
{
j=i; wtemp=t[j];
while(t[j-1]>wtemp && j>0)
{
t[j]=t[j-1];
j--;
}
t[j]=wtemp;
}
}
← rozpoczęcie pętli
← wartość tymczasowa
← porównanie
← zamiana
← ostateczne umiejscowienie
sprawdzanego elementu
11/31
Sortowanie „przez wstawianie” -
przykład
12/31
Cechy sortowania „przez wstawianie”
prosty zapis w postaci algorytmu
algorytm o dużej złożoności obliczeniowej, klasy
O(N
2
)
liczba porównań i przesunięć może być różna
dla różnych przypadków uporządkowania tablicy
przed sortowaniem
nie nadaje się do sortowania dużych tablic
13/31
Sortowanie bąbelkowe
stanowi analogię tablicy odwróconej o 90
o
do
naczynia z wodą i pęcherzykami powietrza w
wodzie
pęcherzyki powietrza ulatują do góry
im lżejszy pęcherzyk powietrza tym szybciej
ulatuje do góry
14/31
Sortowanie bąbelkowe - przebieg
pierwszym sprawdzanym elementem jest ostatni
element tablicy
w 1. pętli element o najmniejszej wartości (najlżejszy)
przemieszcza się na 1. pozycję
w 2. pętli element najlżejszy z zakresu pomijającego 1.
element przemieszcza się na 2. pozycję tabeli
pojedyncza operacja to porównanie dwóch sąsiednich
elementów
każda pętla operuje na tablicy o 1 element mniejszej →
pomijane posortowane elementy
15/31
Sortowanie bąbelkowe - przykład
10
9
8
7
6
5
4
3
2
1
p9
10
10
10
10
10
10
10
6
6
e10
9
9
9
9
9
9
9
10
3
e9
8
8
8
8
8
8
6
9
10
e8
7
7
7
6
6
6
8
3
9
e7
6
6
6
7
5
5
4
8
1
e6
5
5
5
5
7
4
5
4
8
e5
4
4
4
4
4
7
3
5
4
e4
3
3
3
3
3
3
7
2
5
e3
2
2
2
2
2
2
2
7
2
e2
1
1
1
1
1
1
1
1
7
e1
p8
p7
p6
p5
p4
p3
p2
p1
p0
16/31
Sortowanie bąbelkowe - algorytm
void sort_babelkowe(int t[],int r)
{
int wtemp;
for(int i=0;i<r;i++)
{
for(int j=r-1;j>=i;j--)
if(t[j]<t[j-1])
{
wtemp=t[j-1];
t[j-1]=t[j]; t[j]=wtemp;
}
}
}
ogranicznik sprawdzanych
elementów do nieposortowanych
indeks sprawdzanej pary
nieposortowanego zakresu listy
porównanie pary elementów listy
je
żeli element o większym
indeksie jest mniejszy od
poprzednika to nast
ępuje zamiana
miejsc w li
ście
17/31
Sortowanie bąbelkowe - analiza
często zdarzają się „puste” przebiegi pętli
wrażliwość na ułożenie danych w tablicy
prosty zapis algorytmu
dość duża złożoność obliczeniowa O(N
2
)
18/31
Sortowanie przez wstrząsanie
oparte na sortowaniu bąbelkowym
klasa algorytmu O(N
2
)
zapamiętywany indeks ostatniej zmiany
(w celu uniknięcia pustych przebiegów pętli)
przełączanie kierunku przeglądania tablicy
wymagana mniejsza liczba operacji
porównania/przestawiania elementów
19/31
Sortowanie przez wstrząsanie
void sort_wstrzasanie(int t[],int r)
{
int k,wtemp,left,right;
left=1; right=n-1; k=n-1;
do
{
for(int i=r-1;i>=left;i--)
if(t[i]<t[i-1])
{
wtemp=t[i-1]; t[i-1]=t[i];
t[i]=wtemp; k=i;
}
left=k+1;
for(int i=left;i<=right;i++)
if(t[i]<t[i-1])
{
wtemp=t[i-1];
t[i-1]=t[i];
t[i]=wtemp; k=i;
}
right=k-1;
} while(left<=right);
return;
}
kierunek przesuwania
kierunek przesuwania
20/31
Sortowanie przez wstrząsanie -
przykład
21/31
Sortowanie przez wybieranie
metoda:
wyszukiwany jest element o najmniejszej wartości i
wymieniany z 1. elementem tablicy
operacja powyższa powtarzana jest dla następnych n-1
nieposortowanych obiektów
w danym kroku pod uwagę brane są wszystkie
elementy tablicy wejściowej, aby wyszukać
najmniejszy i wstawić go w odpowiednie miejsce
tablicy wynikowej → odwrotnie niż w metodzie
„przez wstawianie”, gdzie porównuje się jeden
element tablicy źródłowej ze wszystkimi
elementami tablicy wynikowej
22/31
Sortowanie przez wybieranie - przykład
void sort_wybieranie(int t[],int r)
{
int k,wtemp;
for(int i=0;i<r;i++)
{
k=i; wtemp=t[i];
for(int j=i+1;j<n;j++)
if(t[j]<wtemp)
{
k=j; wtemp=t[j];
}
t[k]=t[i]; t[i]=wtemp; wyswietl(t,n);
}
}
rozpocz
ęcie przeszukiwania dla
1. elementu nieposortowanej
cz
ęści tablicy źródłowej
zmienna pomocnicza
wyszukiwanie najmniejszego
elementu tablicy
źródłowej
w
śród pozostałych elementów
zamiana elementów tablicy
indeks najmniejszego elementu
23/31
Sortowanie przez wybieranie - przykład
24/31
Sortowanie przez wybieranie - analiza
liczba porównań Po=0.5(n
2
-n) nie zależy od
początkowego ustawienia elementów tablicy
liczba przesunięć minimalna: Pr
min
=3(n-1)
liczba przesunięć maksymalna:
Pr
max
=trunc(n
2
/4)+3(n-1)
liczba przesunięć średnia: Pr
sr
≈
n(ln(n)+
γ
) gdzie
γ ≈0,577 → stała Eulera
zwykle nieco szybszy od prostego wstawiania
25/31
Quicksort – szybkie sortowanie
jest algorytmem klasy O(NlogN)
jest algorytmem typu rekurencyjnego
przebieg procesu sortowania:
wybór punktu podziału (pivot)
przerzucenie elementów o wartościach
większych od pivota na prawo od niego oraz
elementów o wartościach mniejszych na lewo
od niego
wywołanie rekurencyjne sortowania dla obu
części tabeli
26/31
Quicksort – kod
void sort_szybkie(int t[],int r, int p, int k)
{
int i,j,wtemp,pivot;
i=p; j=k; pivot=t[p];
while(i<j)
{
while(t[i]<pivot) i++;
while(t[j]>pivot) j--;
if(i<=j)
{
wtemp=t[i]; t[i]=t[j]; t[j]=wtemp;
i++; j--;
}
}
if(i<k) sort_szybkie(tab, n, i, k);
if(p<j) sort_szybkie(tab, n, p, j);
}
definicja punktu podzia
łu
wyszukanie pary elementów
ustawionych niepoprawnie
wobec pivota
zamiana pary elementów
ustawionych niepoprawnie
wobec pivota
wywo
łanie rekurencyjne
sortowania cz
ęści tablicy
prawej i lewej
27/31
Quicksort – przykład
7
2
5
4
8
1
9
10
3
6
7
2
5
4
1
3
6
8
9
10
2
1
5
4
3
6
5
4
3
6
punkt podzia
łu
28/31
Quicksort – przykład
29/31
Quicksort – podsumowanie
szybkość wykonania algorytmu jest
uzależniona od wyboru punktu podziału
(pivota)
wybór punktu podziału może być:
losowy
pierwszy element tablicy
środkowy element tablicy
30/31
Quicksort – podsumowanie
jeżeli jako punkt podziału wybrany
zostanie punkt środkowy (mediana) to
liczba porównań = n∙logn
liczba wymian = n/6∙logn
w skrajnie niekorzystnym przypadku
algorytm staje się algorytmem klasy O(N
2
)
quicksort preferuje tablice
nieuporządkowane i złożone
31
Dziękuję za uwagę