1

Algorytmy i Struktury

Danych

Wykład 3

2

Sortowanie – definicja i

cele

Sortowanie - uporządkowanie zbioru danych względem

pewnych cech charakterystycznych każdego elementu
tego zbioru (np. wartości każdego elementu, np.
sortowanie liczb rosnąco, słów alfabetycznie itp.)

Cele:
 uporządkowanie danych,
 umożliwienie stosowania wydajniejszych algorytmów

(np. wyszukiwania)

 prezentacja danych w sposób czytelniejszy dla

człowieka.

3

Sortowanie danych

Jest wiele metod sortowania danych.
Dobór odpowiedniej metody zależy od wielu

czynników. Są to m.in.

 rodzaj danych,
 ilość danych,
 wspólne cechy charakterystyczne danych.

Wszystkie metody sortowania będą

przedstawione na przykładzie sortowania

tablicy liczb.

4

Sortowanie przez

wstawianie (ang.

insertion sort)

1.

Zakładamy, że pierwszy element tablicy

jest posortowany.

2.

Bierzemy kolejny,przenosimy do zmiennej

pomocniczej (tmp) i porównujemy elementy

już posortowane z tmp. Jeśli te elementy są

większe od tego w tmp, to przesuwamy je o

jedną pozycję w prawo.

3.

Na końcu (po zakończeniu przesuwania)

wstawiamy element z tmp do pozostałej

komórki tablicy.

5

Sortowanie przez

wstawianie przykład

6

Zaleta

Sortuje on tylko tablice wtedy, gdy

jest to potrzebne. Jeśli nasza

tablica będzie już posortowana

(może to być część tablicy), to

działanie algorytmu polega jedynie

na pobraniu wartości do zmiennej

tmp i odstawieniu jej na miejsce. Nie

wykonujemy żadnych przesunięć.

7

Wady

1. Może się zdarzyć, że liczby, które znajdowały

się już na odpowiednich pozycjach są i tak
przesuwane. W powyższym przykładzie ma to
miejsce dla liczby 7, która w tablicy wejściowej
zajmowała 2 pozycję i pomimo przesunięć, w
ostateczności powróciła na 2 pozycję.

2. Podczas wstawiania liczby do tablicy należy

przesunąć wszystkie większe (mniejsze)
elementy w prawo. W najgorszym przypadku
trzeba przesunąć wszystkie elementy w tablicy.

8

Algorytm ten wykonuje się w n-1 krokach (gdzie

n to ilość elementów do posortowania), a w

każdym kroku wykonujemy jeszcze pewną

ilość przesunięć (porównań i wstawień) –

zależną od położenia sortowanej liczby.

Możliwe są dwa skrajne przypadki:

1.

tablica całkowicie posortowana

2.

tablica posortowana w odwrotnej kolejności

Oraz przypadek pośredni, gdy elementy

tablicy są rozmieszczone przypadkowo.

9

tablica całkowicie

posortowana

W tym przypadku ilość kroków będzie

równa n-1, a ilość „przesunięć” w
każdym kroku 1 (liczba będzie
porównana i wstawiona w to samo
miejsce).

Zatem złożoność w tym przypadku

wyniesie O(n).

10

tablica posortowana w

odwrotnej kolejności

 ilość kroków wyniesie także n-1,

natomiast w każdym k-tym kroku
będzie wykonane k przesunięć
(maksymalna liczba). Zatem ilość
przesunięć w n-1 krokach wyniesie:

czyli złożoność pesymistyczna
tego algorytmu to O(n

2

)

(kwadratowa).

11

Wpływ struktury danych na

efektywność wykonania

algorytmu

 Implementacja oraz efektywność

poszczególnych kroków (podczas
takiego i innych sortowań) zależy od
struktury danych, której używamy.
Np.wstawianie lub usuwanie jest
prostsze jeżeli używamy listy
(szczególnie dwukierunkowej), a nie
statycznej tablicy.

12

Sortowanie przez wybór -

przykład

13

Sortowanie przez wybór

(ang. selection sort)

1. Zaczynamy od pustej części posortowanej, czyli cała

tablica tworzy część nieposortowaną.

2. Przeszukujemy nieposortowaną podtablicę w celu

znalezienia minimum,

3. Jeśli te minimum jest mniejsze od pierwszego

elementu tablicy nieposortowanej to zamieniamy je

miejscami (możliwe, że są one identyczne lub

minimum jest na tej właśnie pozycji, wtedy nic nie

robimy).

4. Przemianowujemy jeden element z części

nieposortowanej do posortowanej.

5. Wracamy do punktu 2.

14

15

Złożoność

(operacja istotna:

porównania)

 Czynność tą wykonujemy n-1 razy, gdzie

n to ilość liczb w tablicy (ostatni element

sam trafia na swoje miejsce)

 Musimy więc wykonać n-1 kroków (n to

ilość elementów w tablicy), a w każdym

kroku wykonujemy przeszukanie

podtablicy o (n-1)-k elementach (k to

numer kroku). Zatem suma porównań

jakie trzeba wykonać będzie wynosić:

16

Złożoność (operacja

istotna: zamiana

elementów miejscami)

Pesymistycznie: musimy w każdym

kroku dokonać zamiany miejscami,
czyli n-1 kroków (n to ilość elementów
w tablicy)

Czyli f(n) = n-1, czyli złożoność O(n)

Optymistycznie: nie musimy wykonać

ani jednej zamiany, bo wszystkie
elementy są „na swoich miejscach”

17

Sortowanie bąbelkowe

 Bierzemy ostatni element tablicy i

porównujemy z poprzednim. Jeśli jest
mniejszy to zamieniamy pozycjami i
porównujemy ten mniejszy znów z
sąsiednim

18

Sortowanie bąbelkowe

(ang.bubble exchange

sort)

 Można to porównać do bąbelków, które

są lżejsze i idą w gorę. Ostatni element

tablicy wrzucamy do bąbelka.

 Jeśli poprzedni jest mniejszy (lżejszy) to

bąbelek zostawia większy element i

zabiera ten mniejszy (lżejszy). Porównuje

go z kolejnym sąsiadem i znów to samo...

Robimy tak długo,aż bąbelek nie dotrze

do części posortowanej tablicy.

19

Sortowanie bąbelkowe -

złożoność

Wykonamy dokładnie n-1 kroków, a w

każdym kroku wykonamy (n-1)-k
porównań, czyli:

20

Sortowanie bąbelkowe

ulepszone

 Algorytm ten można nieco ulepszyć. Może się zdarzyć

tak, że elementy tablicy są częściowo posortowane,

jak np. 1 3 5 8 4 2

 Jeśli bąbelek przejdzie z dołu do góry i żadne komórki

nie zostaną zamienione miejscami to oznacza to, że

tablica jest już posortowana i można zakończyć.

 Przy implementacji realizuje się to przy pomocy

dodatkowej zmiennej logicznej, która na początku

każdego cyklu bąbelka będzie ustawiana na false, a

jakakolwiek zamiana miejscami elementów powoduje

jej ustawienie na true. W ten sposób będziemy mogli

kontrolować, czy były dokonywane jakieś zamiany.

21

Sortowanie bąbelkowe

ulepszone - złożoność

 W przypadku optymistycznym, gdy

tablica będzie posortowana zostanie
wykonane n-1 porównań (jeden bąbelek) i
żaden element nie zostanie zamieniony.

 W przypadku pesymistycznym, gdy

elementy są posortowane odwrotnie niż
powinny wykonamy n-1 kroków, a w
każdym kroku wykonamy (n-1)-k
porównań, czyli:

22

Sortowanie przez

zliczanie (ang.

counting sort)

 Jeżeli wiemy, że liczby do

posortowania są ze skończonego
zbioru liczb całkowitych, to możemy
skorzystać z tej wiedzy i zmniejszyć
złożoność algorytmu sortowania.

23

Przykład: tablica zawiera

liczby z przedziału <0;

3>

 Aby posortować te liczby tworzymy dodatkową

tablicę o dokładnie takiej liczbie komórek jak ilość
liczb mieszcząca się w przedziale k 0,3>. Dla

naszego przykładu będzie to tablica 4 elementowa
(w C/C++).

 Teraz należy przejść tablicę wejściową

(nieposortowaną) i zliczyć ilość wystąpień
poszczególnych liczb w tej tablicy, a wynik zliczania
wstawiać do tablicy pomocniczej pod odpowiednim
indeksem.

24

 Następnie wypisujemy z tablicy zliczeń

odpowiednią ilość każdego elementu
w kolejności rosnącej i gotowe!

25

Sortowanie przez

zliczanie - złożoność

 Złożoność takiego algorytmu sortowania

jest równa O(n) ze względu na operacje

zliczania (zwiększania o jeden elementu w

tablicy zliczającej) oraz tworzenia tablicy

posortowanej.

 Pozwala to sortować niezwykle szybko (w

porównaniu do innych algorytmów

sortowania), przy założeniu, że wiemy

jakie elementy się mogą pojawić.

Potrzebna jest też określona ilość

dodatkowej pamięci na tablicę zliczającą.

26

Sortowanie stabilne

 Sortowanie stabilne to taki rodzaj

sortowania, który zachowuje
kolejność elementów o tej samej
wartości w ciągu wejściowym i
wyjściowym. Innymi słowy ma
znaczenie, który z elementów o tej
samej wartości będzie pierwszy.

27

 Dla omówionego wcześniej sortowania przez

zliczanie zastosujemy sortowanie stabilne.
Do cyfr o tej samej wartości dopisano
indeksy, które mówią o kolejności
wystąpienia tych samych cyfr w tablicy
wejściowej.

28

Sortowanie pozycyjne

(ang. radix sort)

 Problem sortowania ciągów znaków lub liczb

wielocyfrowych można rozwiązać

wykorzystując sortowanie pozycyjne.

 Sortowanie to odbywa się w grupach od lewej

do prawej lub odwrotnie.

 Jeśli chcemy posortować ciąg znaków (np.

nazwiska) sortować będziemy od lewej do

prawej.

 Aby posortować liczby poruszmy się w

odwrotnym kierunku.

29

 Rozważamy dla przykładu liczby trzy

cyfrowych, które należy posortować
rosnąco.

 Wykorzystując stabilne sortowanie przez

zliczanie sortujemy względem liczb na
poszczególnych pozycjach. Wbrew
pozorom sortowanie rozpoczynamy od
pozycji najmniej znaczących (jedności)
i poruszamy się w „lewo”.

30

 W pierwszym kroku sortujemy liczby

sugerując się jedynie ostatnia cyfrą, w
drugim kroku przedostatnią, a w ostatnim
kroku bierzemy pod uwagę jedynie
pierwszą cyfrę.

 W ten sposób nasza tablica liczb zostanie

posortowana. Warto rownież zauważyć, że
jeśli któraś z liczb ma mniejszą ilość cyfr to
należy z przodu uzupełnić ją zerami.

31

32

 Złożoność takiego algorytmu

wynosi kn, gdzie k to ilość cyfr w
liczbie (stosujemy sortowanie przez
zliczanie, bo wiemy, że cyfry są
tylko i wyłącznie dziesiętne), co
daje w notacji złożoność O(n).

33

Sortowanie kubełkowe

(ang. bucket sort)

 Jest to metoda pozwalająca

posortować liczby całkowite. Do
tego celu wykorzystamy 10
kubełków ponumerowanych od 0 do
9. Do każdego będziemy wkładać
odpowiednio liczby.

34

 Na początku umieszczamy liczby w kubełkach

sugerując się cyfrą jedności. Przykładowo, jeśli

cyfra ta jest równa 0 to liczba taka trafi do

kubełka zerowego, gdy 1 to do kubełka

pierwszego, itd. Ważna jest jednak kolejność

liczb w kubełku. Muszą on bowiem być tam

umieszczane w kolejności wystąpienia w ciągu.

Dlatego podczas implementacji kubełka należy

skorzystać z kolejki (struktura dynamiczna!). W

ten sposób wejściowa względna kolejność liczb

zostanie zachowana.

35

 Następnie wyciągamy elementy z

kubełka i układamy w ciąg. Ważne jest

aby wyciągać je począwszy od kubełka

zerowego aż po kubełek dziewiąty.

 Uzyskany ciąg liczb znów rozrzucamy do

kubełków, ale już względem kolejnej

cyfry (dziesiątek).

 Operacje powtarzamy k razy (k to ilość

cyfr w najdłuższej liczbie).

36

Przykład - ciąg liczb: 436,

124, 068, 348, 741, 041, 002, 675,

943, 179. Krok 1 – cyfra jedności.

37

Krok 2: Cyfra dziesiątek

38

Krok 3: Cyfra setek

39

 Dla niewielkich zbiorów można wykorzystać

do zaimplementowania kolejki zrealizowane

na tablicy statycznej, gdyż przyspiesza ona

szybkość wykonywania.

 W tego typu implementacji nie jest

marnowany czas na operacje związane z

tworzeniem i destrukcją kolejek – raz

utworzone kolejki pozostają. Wykonywane

są tylko operacje związane z przenoszeniem

przenoszeniem danych między kolejkami.

40

 Ta wersja nie sprawdza się w przypadku

dużych ciągów elementów, gdyż
niezbędne jest k (ilość pozycji w
elemencie – np. cyfr) tablic o rozmiarze n
(ilość elementów) oraz tablica wejściowa z
danymi.

 Złożoność tego algorytmu jest rzędu O(n)

(podobnie jak sortowania przez zliczanie).