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ę