1
Sortowanie
Sorting
Sortowanie
ASD
LJ
S
Sformułowanie problemu sortowania:
Dane wejściowe: skończony ciąg n elementów (a
1
, a
2
, ., a
n
), na którym
określona jest relacja porządkująca ≤.
Dane wyjściowe: permutacja π=(π(1), π(2), , π(n)) zbioru liczb <1, n>
ustawiająca ciąg elementów (a
1
, a
2
, ., a
n
) w porządku spełniającym
zależność:
a
π(1)
≤ a
π(2)
≤, ,≤ a
π(n)
Proces uzyskania ciągu (a
π(1)
, a
π(2)
, , a
π(n)
) z ciągu (a
1
, a
2
, ., a
n
) nazywamy
sortowaniem.
2
Klasyfikacja algorytmów sortowania
ASD
LJ
S
Według rodzaju struktury danych:
•
sortowanie tablicy,
•
sortowanie listy, łańcucha, rekordu,
•
sortowanie pliku.
Według wykorzystania pamięci:
•
metody intensywne (
in situ
),
•
metody ekstensywne (dodatkowa pamięć - metody szybsze),
•
wewnętrzne (
internal sorting
),
•
zewnętrzne (
external sorting
).
Według efektywności:
•
metody proste O(n
2
),
•
metody szybkie O(n log n)).
Według stabilności:
•
stabilne,
•
niestabilne.
Klasyfikacja algorytmów sortowania
ASD
LJ
S
Algorytmy elementarne:
•
przez wybieranie (
selection sort
),
•
przez wstawianie (
insertion sort
),
•
bąbelkowe (
bubble sort, modified bubble sort
).
Algorytmy zaawansowane:
•
sortowanie szybkie (
quick sort
)
•
przez łączenie (
merge sort
)
•
kopcowe (
heap sort
)
•
Shella (
shell sort
),
•
kubełkowe (
bucket sort
),
•
przez zliczanie (
count sort
),
•
pozycyjne (
radix sort
),
•
turniejowe (
tournament sort
).
3
Sortowanie przez wybieranie
Cechy algorytmu:
Selection sort
Algorytm niestabilny
Działa w miejscu (
in situ
)
Złożoność obliczeniowa O(n
2
)
Zachowanie naturalne.
ASD
LJ
S
Sortowanie przez wybieranie
I.
Sformułowanie problemu.
Dane wejściowe: ciąg n liczb {a
1
, a
2
, ..., a
n
}, na których określona jest relacja
uporządkowania ≤.
Ciąg jest reprezentowany poprzez tablicę A indeksowaną od 1 do n.
Dane wyjściowe: permutacja {a
π(1)
, a
π(2)
, ...,a
π(n)
}, a
π(1)
≤ a
π(2)
≤...≤ a
π(n)
.
Permutacja jest reprezentowana poprzez tablicą A uporządkowanych niemalejąco
elementów
A[π(i)], i=1,2,...,n.
II.
Koncepcja sortowania (werbalny opis algorytmu).
1.
W tablicy sortowanej A[1..n] stanowiącej dane wejściowe wybieramy element o
najmniejszej wartości, a dokładniej jego indeks min, następnie zamieniamy miejscami
element A [min] z elementem A[1].
2. Z następnych n-1 elementów A[2], A[3], . , A[n] wybieramy ponownie najmniejszy
element i zamieniamy z elementem A[2], itd.
3. Procedura sortowania kończy się po rozpatrzeniu dwóch ostatnich elementów.
ASD
LJ
S
4
Sortowanie przez wybieranie
Pseudokod
SELECT_SORT (A,n)
// A-tablica indeksowana od 1 do n
{
FOR i=1,2, ...,n-1{
min:=i;
FOR j:=i+1, ...,n
IF(A[j]<A[min]) min:=j;
swap(A[i],A[min]);
}
}// A-tablica posortowana
ASD
LJ
S
T(n) = (n-1)+ (n-2) + ... + 1 =
2
)
1
( −
n
n
= O(n
2
)
swap(x,y)
{
temp = x;
x = y;
y = temp;
}
5
10
5
2
8
15
20
6
1
2
10
5
5
8
15
20
6
2
2
5
10
5
8
15
20
6
3
2
5
5
10
8
15
20
6
4
2
5
5
6
8
15
20
10
5
2
5
5
6
8
15
20
10
6
2
5
5
6
8
10
20
15
7
2
5
5
6
8
10
15
20
8
część posortowana
bieżąca wartość nminimalna
Sortowanie przez wybieranie
Modyfikacja algorytmu – wykluczenie zamiany elementu z samym sobą,
wymaga wprowadzenia dodatkowej instrukcji prównania.
ASD
LJ
S
Pseudokod
SELECT_SORT (A,n)
//A-tablica indeksowana od 1 do n
{
FOR i=1,2,...,n-1{
min=i;
FOR j=i+1, ...,n
IF (A[j] < A[min]) min=j;
IF (min≠i)
swap(A[i],A[min]);
}
}// A-tablica posortowana
5
Sortowanie przez wstawianie
Cechy algorytmu:
Insertion sort
Algorytm stabilny
Działa w miejscu (in situ)
Złożoność pesymistyczna O(n
2
)
Złożoność optymistyczna O(n)
Zachowanie naturalne
Poprawa efektywności przez wstawianie połówkowe.
ASD
LJ
S
Sortowanie przez wstawianie
Koncepcja sortowania (werbalny opis algorytmu):
1.
Element z każdej pozycji w części nieposortowanej tablicy A należy wstawić do
części posortowanej, tak aby nie naruszyć dokonanego już posortowania.
2.
Dokładniej, element A[i], i=2,3,...,n jest wstawiany na ”właściwe” miejsce j, (1 ≤ j
< n) a wszystkie elementy większe niż A[i] są przesuwane o jedną pozycję w
prawo.
3.
Na początku zakładamy, że element A[1] stanowi jednoelementową,
posortowaną część tablicy.
ASD
LJ
S
6
Sortowanie przez wstawianie
Pseudokod
INSERT_SORT(A,n)
//A-tablica indeksowana od 1 do n
{
FOR (i=2,3,….,n) {
t=A[i];
j=i–1;
WHILE(j≥1 and A[j]>t){
A[j+1]=A[j];
j=j–1;
}
A[j+1]=t;
}
} // A-tablica posortowana
ASD
LJ
S
5
10
5
2
8
15
20
6
1
5
10
5
2
8
15
20
6
2
5
10
5
2
8
15
20
6
3
5
5
10
2
8
15
20
6
4
2
5
5
10
8
15
20
6
5
2
5
5
8
10
15
20
6
6
2
5
5
8
10
15
20
6
7
2
5
5
8
10
15
20
6
8
2
5
5
6
8
10
15
20
9
T(n) = 1+2+
... +
(n-1) =
2
)
1
( −
n
n
= O(n
2
)
Złożoność pesymistyczna:
T(n) = (n-1) = O(n)
Złożoność optymistyczna:
część posortowana
wartość wstawiana
Sortowanie przez wstawianie
INSERT_SORT1(A,n)
//A-tablica indeksowana od 0 do n
{
A[0]=-∞;
FOR (i=2,3,….,n) {
j=i;
WHILE(A[j]<A[j-1]){
swap (A[j],A[j-1])
j=j–1;
}
}
} // A-tablica posortowana
ASD
LJ
S
Sortowanie z wartownikiem (
sentinel
).
Nie w każdej konkretnej implementacji istnieje specjalna, minimalna wartość (-∞),
nie zawsze więc możliwe jest użycie dodatkowego elementu
A[0],
wówczas w
dalszym ciągu konieczne jest sprawdzanie, czy nie następuje próba wysunięcia
A[ i] przed pierwszą pozycję tablicy.
7
Sortowanie bąbelkowe
Cechy algorytmu:
Boubble sort, exchange sort
Algorytm stabilny
Działa w miejscu (
in situ
)
Złożoność O(n
2
)
Porównujemy jedynie sąsiednie elementy tak długo, aż posortujemy.
ASD
LJ
S
Sortowanie bąbelkowe – modyfikacje:
Zamiana kierunku przejść (sortowanie mieszane) asymetria lekkiego i
ciężkiego końca.
Zapamiętanie, czy dokonano zamiany.
Sortowanie bąbelkowe
Algorytm (lekki początek)
BUBBLE_SORT (A,n)
//A-tablica indeksowana od 1 do n
{
FOR (i=1,2,…. n-1)
FOR (j=n,n-1,…. i+1){
IF (A[j]<A[j-1])
swap(A[j],A[j-1]);
}
} // A-tablica posortowana
ASD
LJ
S
część posortowana
2
5
5
10
6
8
15
20
3
2
5
5
6
10
8
15
20
4
2
5
5
6
8
10
15
20
5
2
5
5
6
8
10
15
20
6
2
5
5
6
8
10
15
20
8
5
10
5
2
8
15
20
6
1
2
5
5
6
8
10
15
20
7
2
5
10
5
6
8
15
20
2
T(n) = (n-1)+ (n-2) + ... + 1 =
2
)
1
( −
n
n
= O(n
2
)
8
Sortowanie bąbelkowe
BUBBLE_SORT1(A,n)
//A-tablica indeksowana od 1 do n
{
i=n-1;
flag=true;
WHILE(i>1 and flag){
flag=false;
FOR(j=1,2,…. i)
IF (A[j+1]< A[j]){
swap(A[j],A[j+1]);
flag=true;
}
i=i-1;
}
}// A-tablica posortowana
ASD
LJ
S
Modyfikacja algorytmu (
modified sort
) – zapamiętanie zmian przestawień.
Sortowanie bąbelkowe
Algorytm (ciężki koniec)
BUBBLE_SORT (A,n)
//A-tablica indeksowana od 1 do n
{
FOR (i=n-1,n-2,...,1)
FOR (j=1,2,…,i){
IF (A[j+1] < A[j])
swap(A[j],A[j-1]);
}
} // A-tablica posortowana
ASD
LJ
S
część posortowana
5
10
5
2
8
15
20
6
1
5
5
2
8
10
15
6
20
2
5
2
5
8
10
6
15
20
3
2
5
5
8
6
10
15
20
4
2
5
5
6
8
10
15
20
5
2
5
5
6
8
10
15
20
7
2
5
5
6
8
10
15
20
8
9
Sortowanie Shella
Shell_Sort
D. Shell
Sortowanie Shella
Cechy algorytmu Shella :
Algorytm jest rozszerzeniem algorytmu Insertion sort,
Idea algorytmu oparta jest na grupowaniu i sortowaniu elementów
oddalonych od siebie o wartość odstępu (
gap
),
Wartości odstępów zmieniają się (końcowa wartość wynosi 1),
Sortowanie w miejscu (
in situ
)
Metoda niestabilna
Zachowanie naturalne
Złożoność O(n
1.25
) ÷ O(n
1.5
)
Brak formalnej analizy złożonościowej.
Shell sort zmodyfikowany algorytm Insertion sort.
ASD
LJ
S
10
Sortowanie Shella
Ciąg :
a
1
, a
2
, , a
n
jest h posortowanym jeżeli wszystkie podciągi:
a
1
, a
h+1
, , a
rh+1
a
2
, a
h+2
, , a
rh+2
.
a
h
, a
2h
, , a
rh
(co h elementów) są posortowane.
ASD
LJ
S
Sortowanie Shella
ASD
LJ
S
Sortowanie odbywa się podtablicami danej tablicy (zwanymi h-tablicami), przy
czym każdą podtablicę sortujemy wg Insertion sort.
h-tablicą nazywamy taka podtablicę tablicy A[1..n] w której indeksy odlegle są o h.
A[1], A[1+h], A[1+2h], A[1+3h], - pierwsza h-tablica
A[2], A[2+h], A[2+2h], A[2+3h], - druga h-tablica
A[3], A[2+h], A[2+2h], A[2+3h], - trzecia h-tablica
A[h], A[h+h], A[h+2h], A[h+3h], - h-ta h-tablica itd.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
11
Fazy algorytmu Shella
Faza sortowania "co h=4".
44
55
12
42
94
18
6
67
Sortowanie „co 4”
44
18
6
42
94
55
12
67
Tablica po sortowaniu „co 4”
42
-
-
-
67
44
-
-
-
94
55
-
-
-
18
12
-
-
-
6
ASD
LJ
S
Fazy algorytmu Shella
Sortowanie "co h=2".
44
18
6
42
94
55
12
67
Sortowanie „co 2”
44
-
6
-
94
-
12
18
-
42
-
55
-
67
6
18
12
42
44
55
94
67
Tablica po sortowaniu „co 2”
ASD
LJ
S
6
18
12
42
44
55
94
67
6
12
18
42
44
55
67
94
Tablica po posortowaniu „co 1”
Sortowanie "co h=1".
12
Sortowanie Shella
Fazy algorytmu Shella – „metoda malejących przyrostów”.
Granulację podziału tablicy na podciągi sortowanych elementów wyznaczają
przyrosty oznaczone przez:
h
t
, h
t-1
, , h
1
dla których spełnione jest:
h
1
= 1,
h
i+1
> h
i
Malejąca wartość przyrostu sortowania zmniejsza liczbę podtablic oraz zwiększa
ich rozmiar.
ASD
LJ
S
Sortowanie Shella
Warunki wyboru przyrostów:
h
1
= 1
h
i+1
= 3h
i
+ 1
Największa wartość h
t
taka, że h
t+2
≥ n.
Dla n = 10 000 otrzymany ciąg przyrostów: 1, 4, 13, 40, 121, 364, 1093 .
h
1
= 1
h
i+1
= 2h
i
+ 1
Ciąg przyrostów: 1, 3, 7, 15, 31 .
ASD
LJ
S
h
i
= 2
i
- 1 dla i = t, t - 1, ... , 1; t = lg n .
Ciąg przyrostów: ( , 31, 15, 7, 3, 1).
13
Sortowanie Shella
1.
Wybrać malejący ciąg przyrostów: h
t
, h
t-1
... , h
1
= 1
2.
Wykonać sortowanie co h
i
(i = t, t - 1, ... , 1)
3.
h
t
= 2
t
-1, t = lg n .
Shell_sort(A,n)
//A-tablica indeksowana od 1 do n
{
h=2
lgn
-1;
WHILE (h>=1){
FOR j=h+1,h+2,…,n {
p=A[j];
i=j-h;
WHILE (i>0 ∩ A[i]>p){
A[i+h]=A[i];
i=i-h;
}
A[i+h]=p;
}
h=h div 2;
}
}
ASD
LJ
S
Złożoność algorytmu
Złożoność algorytmu jednak w istotny sposób zależy od doboru ciągu przyrostów.
Testy oceny własności algorytmu Shella wykonano szereg testów (
J. Peterson
), wg
których można przybliżyć średnią złożoność (liczbę przestawień) dla praktycznych
wartości 100≤ n ≤60000:
h
t
= 2
t
+ 1;
. 9, 5, 3, 1 →
1,09 n
1.27
h
t
= 2
t
– 1; 15, 7, 3, 1 →
1,22n
1.26
h
t
= (3
t
- 1)/2; ..40, 13, 4, 1 →
1,66n
1.25
Doświadczalne wyniki O(n
1.25
) ÷ O(n
1.5
)
ASD
LJ
S
Złożoność można zmniejszyć stosując ciąg h
t
postaci 2
p ∗
3
q
, gdzie p, q to liczby
całkowite nieujemne, a h
t
przyjmuje wszystkie wartości tej postaci mniejsze od n
( 24, 18, 16, 12, 9, 8, 6, 4, 3, 2, 1). W takim przypadku złożoność obliczeniowa
algorytmu Shella wynosi O(n(lgn)
2
).
W niektórych przypadkach można jednak oszacować złożoność:
Jeżeli h
i
= 2
i
- 1 dla i = t, t - 1, ... , 1; t = lg n , to T(n) = O(n
3/2
) [
D. Knuth
].