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).