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