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

].