1

Wykład 4 

Sortowanie 

2

Sortowanie - zadanie

Definicja (dla liczb):

   wejście: ciąg n liczb A = (a

1

, a

2

, …, a

n

)

   wyjście: permutacja (a

1

,…, a’

n

) taka, że a’

1 

≤ … ≤ a’

n   

Po co sortować?

– Podstawowy problem dla algorytmiki
– Wiele algorytmów wykorzystuje sortowanie jako procedurę 

pomocniczą

– Pozwala pokazać wiele technik
– Dobrze zbadane (czas)

3

Sortowanie – taksonomia

 Wewnętrzne i zewnętrzne

– Zależnie od miejsca przechowywania zbioru: (RAM czy dysk)

 Sortowanie tablic i sortowanie list łączonych

– zależnie od struktury danych (pliku);
– różny sposób dostępu (bezpośredni dla tablicy, sekwencyjny dla listy).

 „W miejscu” lub nie

– Nie wymaga dodatkowej pamięci

 Stabilne i niestabilne

– Kolejność elementów o tych samych wartościach klucza nie zmienia 

się. Inaczej kolejne sortowanie dla złożonych obiektów nie psuje 
efektów poprzedniego sortowania.

 Bezpośrednie i pośrednie

– zależnie od tego przemieszczamy całe obiekty, czy tylko wskaźniki 

(indeksy) do nich

4

Zestawienie czasów działania

 Przez wybór:

O(N

2

) zawsze

 Bąbelkowe:

O(N

2

) najgorszy przypadek; O(N) 

najlepszy przyp.

 Wstawianie:

O(N

2

) średnio; O(N) najlepszy przypadek

 Shellsort: O(N

4/3

)

 Heapsort: O(NlogN) zawsze
 Mergesort: O(NlogN) zawsze
 Quicksort: O(NlogN) średnio; O(N

2

) najgorszy przypadek

 Zliczanie: O(N) zawsze
 Radix sort: O(N) zawsze

 zewnętrzne: 

O(b logb)) dla pliku o b „stronach”.

5

Sortowanie przez wybór – pomysł

 Znajdujemy najmniejszy element ciągu i zamieniamy go 

z pierwszym elementem. Powtarzamy to dla podciągu 
bez pierwszego elementu, itd.

Znajdź minimum i zamień 
z pierwszym elementem

X

X

6

Sortowanie przez wybór – pseudokod

     Selection_Sort(int A) 
1   for i ← 1 to length[A]
2   do min ← i; 
3

 for j ← i+1 to length[A] 

4      do if A[j] < A[min] then min ← j; 
5      Exchange A[min] ↔ A[i]

7

ciąg: EASYQUESTION  - rozmiar 12 znaków

       

#porównań       #zamian

EASYQUESTION

     

A

ESYQUESTION

11 

1

AE

SYQUESTION

10 

1

AEE

YQUSSTION

  9 

1

AEEI

QUSSTYON 

  8 

1

AEEIN

USSTYOQ 

  7 

1

AEEINO

SSTYUQ 

  6       

1

AEEINOQ

STYUS 

  5     

1

AEEINOQS

TYUS 

  4     

1

AEEINOQSS

YUT 

  3     

1

AEEINOQSST

UY 

  2   

1

AEEINOQSSTU

Y 

  1   

1

Razem

             66                 11

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
1
0
1
1

Sortowanie przez wybór – przykład 

iteracj
a

8

Sortowanie przez wybór – czas działania

 Zależność od danych wejściowych:

– Ilość przebiegów: nie (zawsze N-1)
– Ilość porównań: nie
– Ilość zamian: nie 

 O(N

2

) zawsze (bez znaczenia jaki jest układ elementów w 

danych – ważna tylko ilość)

9

Sortowanie bąbelkowe (przez zamianę)

 Przechodzimy przez ciąg od jego końca, porównując sąsiadujące 

elementy i ewentualnie zamieniając je miejscami. Powtarzamy te 
procedurę aż do uporządkowania całego ciągu.

– Po pierwszym przejściu element minimalny znajduje się na początku –  a[0], 

po drugim na drugim miejscu znajduje się drugi co do wielkości – a[1], po itd.

Porównanie do 
wypływających bąbelków – 
stąd nazwa

.

10

Sortowanie bąbelkowe – pseudokod 

    BUBBLE_SORT(A)
1  for i ← 1 to length[A]
2  do for j ← length[A] downto i + 1
3       do if A[j] < A[j - 1]
4             then exchange A[j] ↔ A[j - 

1]

11

Ciąg: EASYQUESTION, (12 znaków)

       

porównań

zamian

EASYQUESTION                     

(najgorszy przyp)

A

EESYQUISTNO

11     (11) 8     (11)

AE

EISYQUNSTO

10     (10) 6     (10)

AEE

INSYQUOST

  9       (9) 6       (9)

AEEI

NOSYQUST

  8       (8) 4       (8)

AEEIN

OQSYSUT 

  7       (7) 3       (7)

AEEINO

QSSYTU

  6       (6) 2       (6)

AEEINOQ

SSTYU

  5       (5) 1       (5)

AEEINOQS

STUY

  4       (4) 1       (4)

AEEINOQS

STUY

  3       (3) 

0

       (3)

           (2)          (2) 

(1)

         (1)

                              razem          63      (66)

31   (66)

iteracja

  1
  2
  3
  4
  5
  6
  7
  8
  9

Sortowanie bąbelkowe – przykład

12

Sortowanie bąbelkowe – czas wykonania

 Zależność od danych wejściowych:

– Ilość potrzebnych przejść: tak

– Ilość porównań w jednym przejściu: nie

– Ilość zamian: tak

 Najgorszy przypadek: O(N

2

)

– Dane odwrotnie posortowane, np.: JIHGFEDCBA.

– N-1 przejść

– (N-1)N/2 porównań i  (N-1)N/2 zamian

 Najlepszy przypadek: O(N)

– Jeśli elementy są już posortowane, np.: ABCDEFGHIJ.

– Tylko jedno przejście. Stąd mamy N-1 porównań i 0 zamian.

13

Sortowanie przez wstawianie – pomysł 

 Dla każdego elementu ciągu (od lewej do prawej), 

wstawiamy go we właściwe miejsce ciągu elementów 
poprzedzających go (już posortowanych).

14

Sortowanie przez wstawianie – pseudokod 

INSERTION_SORT(A)
1   for j ← 2 to length[A]
2   do key ← A[j]
3         i ← j-1
4        while i>0 and A[i]>key
5        do A[i+1] ← A[i]
6            i ← i-1
7           A[i+1] ← key

15

Ciąg: EASYQUESTION, (12 znaków)

       

porównań

zamian

                                                     (najgorszy przyp.)

E

ASYQUESTION

A

E

SYQUESTION

1     (1)

1     (1)

AE

S

YQUESTION

1     (2)

0     (2)

AES

Y

QUESTION

1     (3)

0     (3)

AE

Q

SY

UESTION

3     (4)

2     (4)

AEQS

U

Y

ESTION

2     (5)

1     (5)

AE

E

QSUY

STION

5     (6)

4     (6)

AEEQS

S

UY

TION

3     (7)

2     (7)

AEEQSS

T

UY

ION

3     (8)

2     (8)

AEE

I

QSSTUY

ON

7     (9)

6     (9)

AEEI

O

QSSTUY

N

7   (10)

6   (10)

AEEI

N

OQSSTUY

8   (11)

7   (11)

                   razem

          41   (66)          31   (66)

iteracja

    1
    2
    3
    4
    5
    6
    7
    8
    9
  10
  11

Sortowanie przez wstawianie – przykład

 

16

Sortowanie przez wstawianie – czas 
działania

 Zależność od danych wejściowych:

– Ilość iteracji: nie (zawsze N-1)
– Ilość porównań: tak
– Ilość zamian: tak

 Najgorszy przypadek: O(N

2

)

– Elementy odwrotnie posortowane np.: JIHGFEDCBA.
– (N-1)N/2 porównań i (N-1)N/2 zamian.

 Najlepszy przypadek: O(N)

– Elementy już posortowane np.: ABCDEFGHIJ.
– Jedno porównanie i 0 zamian w każdej iteracji. Razem, N-1 

porównań i brak zamian.

17

Shellsort – pomysł 

 Modyfikacja (rozszerzona wersja) sortowania przez 

wstawianie

 Dążymy do zmniejszenia ilości zamian – albo ciągi 

krótkie, albo lepsze („bliższe” posortowania).

 Shellsort wykonuje sortowanie podciągów:

– Wybieramy ciąg liczb (zwany ciągiem przyrostów) h

t

, …

 

, 

h

2

, h

1 

;

– h

1

=1; h

t 

 > … > h

2

 >h

1

 ;

– Sortujemy ciągi elementów odległych o h

t

, h

t-1

, h

t-2

,…,h

1

.

18

Shellsort – kod w C

void shellsort (int[ ] a, int n) 

{ 

 int i, j, k, h, v; 

 int[ ] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592, 

1968, 861, 336, 112, 48, 21, 7, 3, 1} 

 for (k=0; k<16; k++) 

                                 {

                                   h=cols[k]; 

                                   for (i=h; i<n; i++) 

                                                            { 

                                                              v=a[i]; 

                                                              j=i; 

                                                              while (j>=h && a[j-h]>v) 

                                                                                                   { 

                                                                                                     a[j]=a[j-

h]; 

                                                                                                     j=j-h; 

                                                                                                   } 

                                                              a[j]=v; 

                                                            } 

                                } 

} 

19

Shellsort – przykład

ciąg: EASYQUESTION  (12 znaków)
ciąg przyrostów 4, 1.

porównań zamian

EASYQUESTION

E

ASY

Q

UES

T

ION

   2

     0

E

A

SY

Q

I

ES

T

U

ON

   3

     1

E

A

E

Y

Q

I

O

S

T

U

S

N

   3

     2

E

A

E

N

Q

I

O

S

T

U

S

Y

   3

     3

Razem w tej fazie

  11

     6

faza 1: przyrost = 4

20

Shellsort – przykład

porównań zamian

EAENQIOSTUSY

AE

ENQIOSTUSY 

   1

     1

AEE

NQIOSTUSY 

   1

     0

AEEN

QIOSTUSY 

   1

     0

AEENQ

IOSTUSY

   1

     0

AEEINQ

OSTUSY

   3

     2

AEEINOQ

STUSY

   2

     1

AEEINOQS

TUSY

   1

     0

AEEINOQST

USY

   1

     0

AEEINOQSTU

SY

   1

     0

AEEINOQSSTU

Y

   3

     2

AEEINOQSSTUY

   1

     0

Razem w tej fazie

  16

     6

faza 2: przyrost= 1

21

Shellsort – przykład

 Razem 27 porównań i 12 zamian.
 Dla sortowania przez wstawiania odpowiednio 41 i 

31 !!! 

– Polepszenie dostajemy przez wstępne posortowanie, 

krótkich podciągów

 Zwykle stosuje się ciągi przyrostów o więcej niż 2 

elementach.

22

Shellsort – czas działania

 Nie ma możliwości przeprowadzenie dokładnej analizy dla 

przypadki ogólnego (wyniki są oparte o badania 
empiryczne).

 Wybór ciągu przyrostów ma zasadniczy wpływ na czas 

sortowania.

– Dla ciągu podanego przez Shell’a: O(N

2

)

• I

max

 = Floor(N/2), I

k

 = Floor(I

k+1

/2). 

• np N=64:1, 2, 4, 8, 16, 32

– Dla ciągu podanego przez Knuth’a: O(N

3/2

)

• I

1

=1, I

k+1

 = 1+3*I

k

. 

• 1, 4, 13, 40, 121, 364, …

23

Mergesort – pomysł

 Dzielimy ciąg na podciągi, sortujemy te podciągi, a 

następnie łączymy zachowując porządek.

– Przykład algorytmu typu „dziel i zwyciężaj”.
– Potrzeba dodatkowego miejsca dla tych podciągów – nie 

jest to sortowanie „w miejscu”.

• Można realizować ten proces „w miejscu”, ale rośnie 

stopień komplikacji.

24

Mergesort – przykład

ciąg: EASYQUESTION  (12 znaków)

EASYQUESTION

EASYQU

ESTION

EAS

YQU

EST

ION

E

AS

Y

QU

E ST I ON

A S

Q U

S T

O N

podział

25

Mergesort – przykład

AEEINOQSSTUY

AEQSUY

EINOST

AES

QUY

EST

INO

E

AS

Y

QU

E

ST

I

NO

A S

Q U

S T

O N

łaczenie

A  E  S

Q  U  Y

C1

C2

C3

26

Mergesort - pseudokod

MERGE-SORT(A, p, r)

1  if p < r

2 

then q ← ⌊(p + r)/2⌋

3 

MERGE-SORT(A, p, q)

4 

MERGE-SORT(A, q + 1, r)

5 

MERGE(A, p, q, r)

27

Mergesort - pseudokod

MERGE(A, p, q, r)
1   n1 ← q - p + 1
2   n2 ← r - q
3   create arrays L[1 ..n1 + 1] and R[1 ..n2 + 

1]

4  for i ← 1 to n1
5  do L[i] ← A[p + i - 1]
6   for j ← 1 to n2
7  do R[j] ← A[q + j]
8  L[n1 + 1] ← ∞
9   R[n2 + 1] ← ∞
10  i ← 1
11  j ← 1
12  for k ← p to r
13  do if L[i] ≤ R[j]
14 

then A[k] ← L[i]

15 

i ← i + 1

16      else A[k] ← R[j]
17              j ← j + 1

28

Sortowanie w czasie 

liniowym 

29

Przegląd

 Czy możliwe jest sortowanie w czasie lepszym niż dla 

metod porównujących elementy (poprzednio – najlepsze 
algorytmy dawały czas O(NlogN))?

 Algorytmy o liniowym czasie działania:

– Przez zliczanie (Counting-Sort)
– Radix-Sort
– Kubełkowe (Bucket-sort)

 Potrzeba dodatkowych założeń!

30

Sortowanie o czasie liniowym

 Możliwe przy dodatkowych informacjach (założeniach) o 

danych wejściowych. 

 Przykłady takich założeń: 

– Dane są liczbami całkowitymi z przedziału [0..k] i k = O(n).
– Dane są liczbami wymiernymi z przedziału [0,1) o rozkładzie 

jednostajnym na tym przedziale

 Trzy algorytmy:

– Counting-Sort
– Radix-Sort
– Bucket-Sort

31

Zliczanie (Counting sort)

   

wejście: n liczb całkowitych z przedziału [0..k], dla k = O(n).

   pomysł: dla każdego elementu wejścia x określamy jego 

pozycje (rank): ilość elementów mniejszych od x.

   jeśli znamy  pozycję elementu – umieszczamy go na r+1 

miejscu ciągu

  

 przykład: jeśli wiemy, że w ciągu jest 6 elementów mniejszych 

od 17, to 17 znajdzie się na 7 miejscu w ciągu wynikowym.

  

 powtórzenia: jeśli mamy kilka równych elementów 

umieszczamy je kolejno poczynając od indeksu pozycja

32

Zliczanie (Counting sort)

1

3

2

4 5

Jeśli nie ma powtórzeń i n = k, 
Rank[A[i]] = A[i] i B[Rank[A[i]] 
 A[i]

Dla każdego A[i], liczymy 

elementy ≤  od niego. Daje to 

rank (pozycję) elementu

4

1

2

5

A =

B =

Rank =

4

3

5

2

1

3

33

Zliczanie (Counting sort)

5

1

2

3

A =

3

2

4

Rank =

Jeśli nie ma powtórzeń i n < 
k

, 

Niektóre komórki tablicy 
rank pozostają 
niewykorzystane, ale 
algorytm działa.

B =

5

2

1

1

3

34

Zliczanie (Counting sort)

4

1

2

2

A =

1

4

3

5

Rank =

Jeśli n > k i mamy 
powtórzenia, 

umieszczamy na wyjściu 
powtarzające się elementy 
w takiej kolejności, w jakiej 
występowały w oryginalnym 
ciągu (stabilność)

B =

3

3 4

2

1

2

2

35

Zliczanie (Counting sort)

Counting-Sort(A, B, k)
1.

for i  0 to k 

2.

   do C[i]  0

3.

for j  1 to length[A] 

4.

   do C[A[j]]  C[A[j]] +1   

5.

 /* C zawiera ilości elementów równych i

6.

for i  1 to k

7.

   do C[i]  C[i] + C[i –1]

8.

 /* C zawiera ilości elementów ≤  i

9.

for j  length[A] downto 1 

10.

   do B[C[A[j]]]  A[j]

11.

        C[A[j]]  C[A[j]] – 1

A[1..n] – tablica wejściowa
B [1..n] – tablica wyjściowa
C [0..k] – pomocnicza tablica (do zliczania) 

36

Sortowanie przez zliczanie – przykład  (1)

n = 8
k = 6

B[C[A[j]]]  A[j]

C[A[j]]  C[A[j]] – 1

po p. 11

C[A[j]]  C[A[j]] +1

po p.4

C =

 0      1      2       3     4      5

 

2

2

0

3 0 1

2

3

5

0 2 3 0 3

A =

 1      2       3     4      5      6      7      8

 

2

4

2

7 7 8

C =

 0      1      2       3     4      5

 

C[i]  C[i] + C[i –1]

po p. 7

2

4

2

7 8

C =

 0      1      2       3     4      5

 

7

 1      2       3     4      5      6      7      8

 

B =

3

6

37

Sortowanie przez zliczanie – przykład  (2)

0

3

B =

2

4

2

6 7 8

C =

 0      1      2       3     4      5

 

 1      2       3     4      5      6      7      8

 

2

3

5

0 2 3 0 3

A =

 1      2       3     4      5      6      7      8

 

2

4

2

6 7 8

C =

 0      1      2       3     4      5

 

1

38

Sortowanie przez zliczanie – przykład  (3)

0

3

B =

1

4

2

6 7 8

C =

 0      1      2       3     4      5

 

 1      2       3     4      5      6      7      8

 

2

3

5

0 2 3 0 3

A =

 1      2       3     4      5      6      7      8

 

2

4

2

6 7 8

C =

 0      1      2       3     4      5

 

3

5

39

Counting sort – czas działania

 Pętla for w p.1-2 zajmuje czas Θ(k)
 Pętla for w p.3-4 zajmuje czas Θ(n)
 Pętla for w p.6-7 zajmuje czas Θ(k)
 Pętla for w p.9-11 zajmuje czas Θ(n)
 Stąd dostajemy łączny czas Θ(n+k)
 Ponieważ k = O(n), T(n) = Θ(n)       algorytm jest 

optymalny!!

 Konieczne jest założenie k = O(n). Jeśli k >> n to 

potrzeba to potrzeba dużej ilości pamięci. 

 Nie jest to sortowanie „w miejscu”. 

40

Radix sort – sortowanie pozycyjne

wejście: n liczb całkowitych, d-cyfrowych, łańcuchów o d-

pozycjach

pomysł: zajmować się tylko jedną z cyfr (sortować 

względem kolejnych pozycji – cyfr/znaków). Zaczynamy 
od najmniej znaczącej cyfry/znaku, potem kolejne pozycje 
(cyfry/znaki), aż do najbardziej znaczącej. Musimy 
stosować metodą stabilną. Ponieważ zbiór możliwych 
wartości jest mały (cyfry – 0-9, znaki ‘a’-’z’) możemy 
zastosować metodę zliczania, o czasie O(n)

Po zakończeniu ciąg będzie posortowany!!

41

Radix sort – przykład 

7 2 

0

 3 2 

9
 4 3 

6
 8 3 

9
 3 5 

5
 4 5 

7
 6 5 

7

3 2 

9

 4 5 

7
 6 5 

7
 8 3 

9
 4 3 

6
 7 2 

0
 3 5 

5

7 2 

0

3 5 

5
4 3 

6
4 5 

7
6 5 

7
3 2 

9
8 3 

9

3 2 

9

 3 5 

5 
 4 3 

6
 4 5 

7
 6 5 

7
 7 2 

0
 8 3 

9

42

Radix-Sort – pseudokod 

Radix-Sort(A, d)
1. for i  1 to d 
2.    do  zastosuj stabilną metodę sortowania do cyfry d dla 

tablicy A

uwagi: 
•

złożoność: T(n) = Θ(d(n+k))  Θ(n) dla stałego d i k = O(1)

•

wartości cyfr/znaków są z zakresu [0..k –1] dla k = O(1)

•

Metoda stosowana dla poszczególnych pozycji musi być 
stabilna!

43

Sortowanie kubełkowe – Bucket sort

wejście: n liczb rzeczywistych z przedziału [0..1) ważne jest, 

aby były równomiernie rozłożone  (każda wartość równie 
prawdopodobna)

pomysł: dzielimy przedział [0..1) na n podprzedziałów 

(„kubełków”):0, 1/n, 2/n. … (n–1)/n. Elementy do 
odpowiednich kubełków, a

i

: 1/i ≤ a

i 

≤ 1/(i+1). Ponieważ 

rozkład jest równomierny to w żadnym z przedziałów nie 
powinno znaleźć się zbyt wiele wartości. Jeśli wkładamy je 
do kubełków zachowując porządek (np. przez wstawianie – 
Insertion-Sort), dostaniemy posortowany ciąg.   

44

Bucket sort – przykład

.78

.17

.39

.26

.72

.94

. 21

.12

.23

.68

7

6

8

9

5

4

3

2

1

0

.17

.12

.26

.23

.21

.39

.68

.78

.72

.94

.68

.72

.78

.94

.39

.26

.23

.21

.17

.12

45

Bucket-Sort

Bucket-Sort(A)
1.

 n  length(A)

2.

 for i  0 to n 

3.

   do wstaw A[i] do listy B[floor(nA[i])]

4.

for i  0 to n –1 

5.

   do Insertion-Sort(B[i])

6.

 Połącz listy B[0], B[1], … B[n –1]

A[i] tablica wejściowa
B[0], B[1], … B[n –1]  lista „kubełków”

46

Bucket-Sort – złożoność czasowa

 Wszystkie instrukcje z wyjątkiem 5 (Insertion-Sort) wymagają 

czasu O(n), w przypadku pesymistycznym.

 W przypadku pesymistycznym, O(n) liczb trafi do jednego 

„kubełka” czyli ich sortowanie zajmie czas O(n

2

). 

 Jednak w średnim przypadku stała ilość elementów wpada do 

jednego przedziału – stąd czas średni  wyniesie O(n).