Sortowanie
Sorting
Sortowanie
Sformułowanie problemu sortowania:
Dane wejściowe: skończony ciąg n elementów (a1, a2, ., an), na którym
określona jest relacja porządkująca d".
Dane wyjściowe: permutacja Ą=(Ą(1), Ą(2), , Ą(n)) zbioru liczb <1, n>
ustawiająca ciąg elementów (a1, a2, ., an) w porządku spełniającym
zależność:
aĄ(1) d" aĄ(2) d", ,d" aĄ(n)
Proces uzyskania ciągu (aĄ(1) , aĄ(2) , , aĄ(n) ) z ciągu (a1, a2, ., an) nazywamy
sortowaniem.
ASD LJ S
1
Klasyfikacja algorytmów sortowania
Według rodzaju struktury danych:
" sortowanie tablicy,
" sortowanie listy, łańcucha, rekordu,
" sortowanie pliku.
Według stabilności:
" stabilne,
" niestabilne.
Według efektywności:
" metody proste O(n2),
" metody szybkie O(n log n)).
Według wykorzystania pamięci:
" metody intensywne (in situ),
" metody ekstensywne (dodatkowa pamięć - metody szybsze),
" wewnętrzne (internal sorting),
" zewnętrzne (external sorting).
ASD LJ S
Klasyfikacja algorytmów sortowania
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).
ASD LJ S
2
Sortowanie przez wybieranie
Cechy algorytmu:
Selection sort
Algorytm niestabilny
Działa w miejscu (in situ)
Złożoność obliczeniowa O(n2)
Zachowanie naturalne.
ASD LJ S
Sortowanie przez wybieranie
I. Sformułowanie problemu.
Dane wejściowe: ciąg n liczb {a1, a2, ..., an}, na których określona jest relacja
uporzÄ…dkowania d".
CiÄ…g jest reprezentowany poprzez tablicÄ™ A indeksowanÄ… od 1 do n.
Dane wyjściowe: permutacja {aĄ(1), aĄ(2), ...,aĄ(n)}, aĄ(1)d" aĄ(2) d"...d" 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
3
Sortowanie przez wybieranie
Pseudokod 1 5 10 5 2 8 15 20 6
2 2 10 5 5 8 15 20 6
SELECT_SORT (A,n)
// A-tablica indeksowana od 1 do n
{ 3 2 5 10 5 8 15 20 6
FOR i=1,2, ...,n-1{
4 2 5 5 10 8 15 20 6
min:=i;
FOR j:=i+1, ...,n
5 2 5 5 6 8 15 20 10
IF(A[j]6 2 5 5 6 8 15 20 10
swap(A[i],A[min]);
}
7 2 5 5 6 8 10 20 15
}// A-tablica posortowana
8 2 5 5 6 8 10 15 20
część posortowana
swap(x,y)
{
temp = x; bieżąca wartość nminimalna
x = y;
y = temp;
n(n -1)
} T(n) = (n-1)+ (n-2) + ... + 1 =
= O(n2)
2
ASD LJ S
Sortowanie przez wybieranie
Modyfikacja algorytmu  wykluczenie zamiany elementu z samym sobÄ…,
wymaga wprowadzenia dodatkowej instrukcji prównania.
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
ASD LJ S
4
Sortowanie przez wstawianie
Cechy algorytmu:
Insertion sort
Algorytm stabilny
Działa w miejscu (in situ)
Złożoność pesymistyczna O(n2)
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 d" 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
5
Sortowanie przez wstawianie
1 5 10 5 2 8 15 20 6
Pseudokod
2 5 10 5 2 8 15 20 6
INSERT_SORT(A,n)
//A-tablica indeksowana od 1 do n
3 5 10 5 2 8 15 20 6
{
4 5 5 10 2 8 15 20 6
FOR (i=2,3,& .,n) {
t=A[i];
5 2 5 5 10 8 15 20 6
j=i 1;
WHILE(je"1 and A[j]>t){ 6 2 5 5 8 10 15 20 6
A[j+1]=A[j];
7 2 5 5 8 10 15 20 6
j=j 1;
}
8 2 5 5 8 10 15 20 6
A[j+1]=t;
9 2 6 8 10 15 20
5 5
}
} // A-tablica posortowana
część posortowana
wartość wstawiana
n(n -1)
= O(n2)
Złożoność pesymistyczna: T(n) = 1+2+ ... + (n-1) =
2
Złożoność optymistyczna: T(n) = (n-1) = O(n)
ASD LJ S
Sortowanie przez wstawianie
Sortowanie z wartownikiem (sentinel).
INSERT_SORT1(A,n)
//A-tablica indeksowana od 0 do n
{
A[0]=-";
FOR (i=2,3,& .,n) {
j=i;
WHILE(A[j]swap (A[j],A[j-1])
j=j 1;
}
}
} // A-tablica posortowana
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.
ASD LJ S
6
Sortowanie bÄ…belkowe
Cechy algorytmu:
Boubble sort, exchange sort
Algorytm stabilny
Działa w miejscu (in situ)
Złożoność O(n2)
Porównujemy jedynie sąsiednie elementy tak długo, aż posortujemy.
Sortowanie bÄ…belkowe  modyfikacje:
Zamiana kierunku przejść (sortowanie mieszane) asymetria lekkiego i
ciężkiego końca.
Zapamiętanie, czy dokonano zamiany.
ASD LJ S
Sortowanie bÄ…belkowe
1 3 4 5 6 7 8
2
Algorytm (lekki poczÄ…tek)
5 2 2 2 2
2 2 2
10 5 5 5 5
5 5 5
BUBBLE_SORT (A,n)
5 5 5 5 5 5 5
10
//A-tablica indeksowana od 1 do n
2 10 6 6 6 6 6
5
{
FOR (i=1,2,& . n-1)
8 8 8 8 8
6 6 10
FOR (j=n,n-1,& . i+1){
15 10 10 10 10
8 8 8
IF (A[j]20 15 15 15 15
15 15 15
swap(A[j],A[j-1]);
} 6 20 20 20 20
20 20 20
} // A-tablica posortowana
część posortowana
n(n -1)
T(n) = (n-1)+ (n-2) + ... + 1 =
= O(n2)
2
ASD LJ S
7
Sortowanie bÄ…belkowe
1 2 3 4 5 7 8
Algorytm (ciężki koniec)
5 5 5 2 2 2 2
10 5 2 5 5 5 5
BUBBLE_SORT (A,n)
5 2 5 5 5 5 5
//A-tablica indeksowana od 1 do n
2 8 8 8 6 6 6
{
FOR (i=n-1,n-2,...,1) 8 10 10 6 8 8 8
FOR (j=1,2,& ,i){
15 15 6 10 10 10 10
IF (A[j+1] < A[j])
20 6 15 15 15 15 15
swap(A[j],A[j-1]);
6 20 20 20 20 20 20
}
} // A-tablica posortowana
część posortowana
ASD LJ S
Sortowanie bÄ…belkowe
Modyfikacja algorytmu (modified sort)  zapamiętanie zmian przestawień.
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
8
Sortowanie Shella
Shell_Sort
D. Shell
Sortowanie Shella
Shell sort zmodyfikowany algorytm Insertion sort.
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(n1.25) ÷ O(n1.5)
Brak formalnej analizy złożonościowej.
ASD LJ S
9
Sortowanie Shella
CiÄ…g :
a1, a2, , an
jest h posortowanym jeżeli wszystkie podciągi:
a1, ah+1, , arh+1
a2, ah+2, , arh+2
.
ah, a2h, , arh
(co h elementów) są posortowane.
ASD LJ S
Sortowanie Shella
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.
ASD LJ S
10
Fazy algorytmu Shella
Faza sortowania "co h=4".
44 - - - 94
55 - - - 18
12 - - - 6
44 55 12 42 94 18 6 67
42 - - - 67
Sortowanie  co 4
44 18 6 42 94 55 12 67
Tablica po sortowaniu  co 4
ASD LJ S
Fazy algorytmu Shella
Sortowanie "co h=2".
44 - 6 - 94 - 12
44 18 6 42 94 55 12 67
18 - 42 - 55 - 67
Sortowanie  co 2
6 18 12 42 44 55 94 67
Tablica po sortowaniu  co 2
Sortowanie "co h=1".
6 12 18 42 44 55 67 94
6 18 12 42 44 55 94 67
Tablica po posortowaniu  co 1
ASD LJ S
11
Sortowanie Shella
Fazy algorytmu Shella   metoda malejących przyrostów .
Granulację podziału tablicy na podciągi sortowanych elementów wyznaczają
przyrosty oznaczone przez:
ht, ht-1, , h1
dla których spełnione jest:
h1= 1,
hi+1 > hi
Malejąca wartość przyrostu sortowania zmniejsza liczbę podtablic oraz zwiększa
ich rozmiar.
ASD LJ S
Sortowanie Shella
Warunki wyboru przyrostów:
h1 = 1
hi+1 = 3hi+ 1
Największa wartość ht taka, że ht+2 e" n.
Dla n = 10 000 otrzymany ciąg przyrostów: 1, 4, 13, 40, 121, 364, 1093 .
h1 = 1
hi+1 = 2hi+ 1
Ciąg przyrostów: 1, 3, 7, 15, 31 .
hi = 2i - 1 dla i = t, t - 1, ... , 1; t = ðÅ‚lg n ûÅ‚.
Ciąg przyrostów: ( , 31, 15, 7, 3, 1).
ASD LJ S
12
Sortowanie Shella
1. Wybrać malejący ciąg przyrostów: ht, ht-1... , h1= 1
2. Wykonać sortowanie co hi (i = t, t - 1, ... , 1)
3. ht = 2t-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 100d" n d"60000:
ht = 2t + 1; . 9, 5, 3, 1 1,09 n1.27
ht = 2t  1; 15, 7, 3, 1 1,22n1.26
ht = (3t - 1)/2; ..40, 13, 4, 1 1,66n1.25
DoÅ›wiadczalne wyniki O(n1.25) ÷ O(n1.5)
W niektórych przypadkach można jednak oszacować złożoność:
Jeżeli hi = 2i - 1 dla i = t, t - 1, ... , 1; t = ðÅ‚lg n ûÅ‚, to T(n) = O(n3/2) [D. Knuth].
Złożoność można zmniejszyć stosując ciąg ht postaci 2p " 3q, gdzie p, q to liczby
całkowite nieujemne, a ht 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).
ASD LJ S
13