RÓśNE SORTOWNIA – część pierwsza

PRZYGOTOWAŁA: Beata Laszkiewicz

Strona 1 z 4

Sortowanie przez wybór.
Sortowanie to porządkowanie elementów według określonego klucza.

Algorytm sortowania przez wybór jest bardzo prosty. Zauważmy, że jeśli mamy ustawić elementy
w kolejności od najmniejszego do największego, to można wybrać w nim najpierw element najmniej-
szy, umieścić go na początku, za nim umieścić drugi element najmniejszy w ciągu pozostałym, itd.
Wiadomo, jak szukać najmniejszego elementu w ciągu nieuporządkowanym, należy więc podać jedy-
nie jak ustawiać elementy jeden za drugim. Najoszczędniej jest to zrobić w tym samym miejscu, czyli
wymienić element znaleziony z tym, który zajmuje jego miejsce.

Przykład:
Weźmy ciąg: 9, 7, 1, 10, 4, 2, 3
Na zielono zaznaczono kolejne fragmenty ciągu już uporządkowanego.

9 7 1 10 4 2 3

1

7 9 10 4 2 3

1 2

9 10 4 7 3

1 2 3

10 4 7 9

1 2 3 4

10 7 9

1 2 3 4 7

10 9

1 2 3 4 7 9 10

Algorytm:
Dane: Zbiór n liczb nieposortowanych
Wynik: Zbiór n liczb posortowanych

dla każdego elementu ze zbioru {dla i=1,2,...n}:

znajdź minimum w zbiorze od i – tego to ostatniego elementu zbioru

wymień znalezione minimum z i-tym elementem zbioru

Przy algorytmach sortowania należy zwrócić uwagę na złożoność wykonywania algorytmu, czyli ile
wykonujemy porównań, dodawań, mnożeń itd. W algorytmach sortowania będzie nas interesowała
liczba porównań. Na początku wystarczy policzyć porównania. Następnie można wyprowadzić wzór
w zależności od ilości liczb w ciągu. Do tego można posłużyć się dowodem geometrycznym, jak na
rysunku:




n-1





n

Złożoność

:

O(n

2

)

Dokładnie n(n-1)/2

RÓśNE SORTOWNIA – część pierwsza

PRZYGOTOWAŁA: Beata Laszkiewicz

Strona 2 z 4

Sortowanie przez wstawianie:


Algorytm sortowania przez wstawianie jest również prosty. Zakładamy, że pierwszy element zbioru
jest już uporządkowany. Następnie kolejne elementy zbioru próbujemy wstawić do zbioru już upo-
rządkowanego.

Przykład:
Weźmy ciąg: 9, 7, 1, 10, 4, 2, 3

9 7 1 10 4 2 3

7 9

1

10 4 2 3

1 7 9

10 4 2 3

1 7 9

10

4 2 3

1 4 7 9

10

2 3

1 2 4 7 9

10

3

1 2 3 4 7 9 10

Algorytm:
Dane: Zbiór n liczb nieposortowanych
Wynik: Zbiór n liczb posortowanych

dla każdego elementu ze zbioru z wyjątkiem pierwszego {dla i=2,3,...n}:

znajdź miejsce dla i-tego elementu zbioru w zbiorze uporządkowanym

przesuń elementy zbioru tak, by zrobić miejsce dla tego, który chcemy wstawić

wstaw i-ty element w znalezione miejsce

Złożoność

:

O(n

2

)

RÓśNE SORTOWNIA – część pierwsza

PRZYGOTOWAŁA: Beata Laszkiewicz

Strona 3 z 4

Sortowanie przez scalanie:

Najpierw należy zając się problemem scalania dwóch uporządkowanych ciągów w jeden ciąg upo-
rządkowany:

Opis:
Scalanie dwóch uporządkowanych ciągów może być wykonane w bardzo prosty sposób: patrzymy na
początki danych ciągów i do tworzonego ciągu przenosimy mniejszy z elementów czołowych lub któ-
rykolwiek z nich, gdy są równe.

Przykład:






Algorytm:
Dane: Dwa uporządkowane ciągi

y

x,

Wyniki: Uporządkowany ciąg

z

, będący scaleniem ciągów

y

x

,

dopóki oba ciągi

y

x

,

nie są puste wykonuj:

przenieś mniejszy z najmniejszych elementów z ciągów

x

i

y

do ciągu

z

do końca ciągu

z

dopisz elementy pozostałe w jednym z ciągów

y

x

,

A teraz jak wygląda sortowanie przez scalanie:
Opis:
Porządkowany ciąg jest dzielony w każdym kroku na dwa, niemal równej długości podciągi, które
rekurencyjnie są porządkowane tą samą metodą. Warunkiem zakończenia rekurencji jest sytuacja, gdy
ciąg ma jeden element – wtedy nie można go podzielić na podciągi, ciąg taki jest już uporządkowany.
Zatem powrót z wywołań rekurencyjnych rozpoczyna się z ciągami złożonymi z pojedynczych ele-
mentów, które są scalane w ciągi o długości 2, następnie 3 lub 4 elementy itd.

Algorytm:
Dane: Ciąg liczb

p

l

l

x

x

x

,

,

,

1

K

+

, nieuporządkowany

Wyniki: Uporządkowany ciąg tych liczb od najmniejszej do największej

jeśli pozostał jeden element – ciąg jest uporządkowany

w przeciwnym razie

- jeśli

p

l

<

to

2

)

(

div

p

l

s

+

←

- zastosuj algorytm dla

)

,

,

(

x

s

l

- zastosuj algorytm dla

)

,

,

(

x

p

l

s

+

- zastosuj algorytm scalania do ciągów

s

l

x

x

,

,K

oraz

p

s

x

x

,

,

1

K

+

i wynik ponownie umieść

w ciągu

p

l

l

x

x

x

,

,

,

1

K

+

Złożoność algorytmu:
Zakładamy, że liczba

n

będzie potęgo dwójki.

Otrzymujemy wtedy:

1 3 5 7 10 12

1 2 6 9 11 15 17 20

1 3 5 7 10 12
1 2 6 9 11 15
17 20

RÓśNE SORTOWNIA – część pierwsza

PRZYGOTOWAŁA: Beata Laszkiewicz

Strona 4 z 4











>

−

+

=

=

=

2

n

),

1

(

)

2

/

(

2

2

n

,

1

1

n

,

0

)

(

n

n

r

n

r

Zależność rozwiązujemy i otrzymujemy:

1

log

)

(

2

+

−

=

n

n

n

n

r

Przykład:

2 1 2 9 5

2 1 2

9 5 0

2

9

2

0

2

1

9

5

1,2

5,9

1,2,2

0,5,9

0,1,2,2,5,9