1

Wykład 3

Sortowanie grzebieniowe (combsort)

Sortowanie przez podział (quicksort)

Sortowanie przez scalanie (mergesort)

Sortowanie licznikowe (countsort)

Sortowanie kubełkowe (bucketsort)

Sortowanie pozycyjne (radixsort)

2

Sortowania szybkie I

Sortowanie grzebieniowe Combsort:

- pochodzi z roku 1991,

- oparta na metodzie bąbelkowej,

- włączono tutaj empirię (współczynnik 1.3 wyznaczono

doświadczalnie),

- złożoność O(n*log(n)), statystyka gorsza niż Quicksort

(1.5 - 2 razy), ale algorytm prosty (bez rekurencji).

3

Sortowania szybkie I cd.

Warianty sortowania Comsort:

- podstawowy - za rozpiętość przyjmij długość tablicy,

podziel rozpiętość przez 1.3, odrzuć część ułamkową,
będzie to pierwsza rozpiętość badanych par obiektów,
badaj wszystkie pary o tej rozpiętości, jeżeli naruszają
monotoniczność, to przestaw; wykonuj w pętli
(rozpiętość podziel znów przez 1.3); kontynuując do
rozpiętości 1 przejdziesz na metodę bąbelkową;
kontynuuj do uzyskania monotoniczności.

- Combsort 11 - rozpiętość 9 i 10 zastępujemy 11.

4

Sortowania szybkie I cd.

procedure Combsort(var a:tablica; n:integer);

var top, gap, i, j : integer;

x : element;

swapped : boolean;

begin

gap := n;

repeat

gap := max(trunc(gap/1.3),1);

top := n - gap;

swapped := false;

for i := 1 to top do begin

j := i + gap;

if a[i] > a[j] then begin

a[i] :=: a[j];

swapped := true;

end;

end;

until (gap = 1) and not swapped;

end;

5

Sortowania szybkie II

Sortowanie przez podział – Quicksort

- wybieramy element dzielący, względem którego dzielimy
tablicę na elementy mniejsze i większe, wymieniając
elementy położone daleko od siebie, operację powtarzamy
dla obu części tablicy, aż do podziału na części o długości 1.
- wersja rekurencyjna i nierekurencyjna,
- warianty: naiwny, losowy, z medianą z 3,
- kombinacja z metodą prostą,
- Quickersort,

6

Sortowania szybkie II cd.

Sortowanie szybkie cd.

- w zależności od wyboru elementu dzielącego różne

działanie dla skrajnych przypadków: mediana -
najmniejsza liczba porównań; mediana z próbki - nie
wpływa na wydajność; losowy wybór - średnia
efektywność mniejsza od optymalnej; lewy, prawy - zły
dla posortowanych ⇒ środkowy,

- wady i zalety: dla dużych n, można łatwo łączyć z

innymi, może się ukwadratowić - O(n

2

)! (zły wybór

ograniczenia), niestabilna, najszybsza metoda oparta
o porównywanie kluczy.

2

7

Sortowania szybkie II cd.

procedure sortowanieszybkie;

procedure sortuj(l, p : integer);

var i,j : integer; x : integer;

begin

i := l; j := p;

x := a[(l+p) div 2];

repeat

while a[i] < x do i := i+1;

while a[j] > x do j := j-1;

if i <= j then begin

a[j] :=: a[i];

i := i+1;

j := j-1;

end;

until i > j;

if l < j then sortuj(l, j);

if i < p then sortuj(i, p);

end;

begin

sortuj(1, n);

end;

8

Wyszukiwanie mediany na

bazie sortowania szybkiego

Algorytm poszukiwania mediany:

- ogólnie znajdowanie k-tego co do wielkości elementu

z n elementowego zbioru,

- mediana: w ciągu posortowanym jest to element

środkowy; dla mediany k = n / 2,

- algorytm Hoare'a: działa w miejscu, jest szybki dla

danych losowych, pesymistyczna złożoność O(n

2

).

9

Sortowania szybkie III

· Sortowanie przez scalanie - Mergesort

- jest to metoda ekstensywna o zapotrzebowaniu na

dodatkową pamięć równą pojemności tablicy sortowanej;
wyjątkowo dogania Quicksort, statystycznie z nim
przegrywa, skomplikowany, dobra idea dla sortowania

zewnętrznego,

-

algorytm scalania

: dane dwa piki (tablice)

monotoniczne, należy je scalić w jeden monotoniczny:
bierz obiekty z czoła i mniejszy przenieś na plik
końcowy, konkatenuj, aż któryś z plików wejściowych
się skończy, resztę dopisz na koniec wyjściowego pliku,

10

Sortowania szybkie III cd.

Sortowanie Mergesort cd.

- wersja podstawowa (iteracyjna): podziel tablicę na

odcinki 1-elementowe, scalaj 1 z 2, 3 z 4 itd. Przepisując
do drugiej tablicy; potem dwuelementowe odcinki scalaj
w 4-elementowe, przepisując z powrotem do 1-szej
tablicy itd. aż do odcinka posortowanego o długości
tablicy,

- wersja rekurencyjna: podziel na 2 części i zastosuj

metodę Mergesort, wyniki scal; gorsza od podstawowej,

- wersja naturalna: zaczyna się od serii naturalnych; kłopot

z wyznaczeniem granic serii; jest atrakcyjna, gdy tablica
jest częściowo posortowana.

11

Sortowanie licznikowe

type

element = 0..K;

tablica = array [1..MAX] of element;

procedure CountingSort(var A,B:tablica);

var

i, j : integer;

C : array[0..K] of integer;

begin

for i:=0 to K do C[i]:=0;

for j:=1 to MAX do C[A[j]]:=C[A[j]]+1;

for i:=1 to K do C[i]:=C[i]+C[i-1];

for j:=MAX downto 1 do begin

B[C[A[j]]]:=A[j];

C[A[j]]:=C[A[j]]-1;

end;

end;

12

Sortowanie kubełkowe

type

tablica = array [1..MAX] of element;

{ element przyjmuje warto

ś

ci [0..1) }

BucketSort(A)

for i:=1 to MAX do

{ wstaw A[i] do kolejki B[trunc(MAX*A[i])];

for i:=0 to MAX-1 do

{ posortuj kolejk

ę

B[i] }

{ dokonaj konkatenacji kolejek B[0]...B[MAX-1] }