Sortowanie

Porządkowanie zbioru.

q = [a₁, a₂ , ... , a_n]

permutacja a_i1 ≤ a_{i 2} ≤ ... ≤ a_in

Modyfikacje:

• sortowanie rekordów danych według klucza

key(a_i1) ≤ key(a_i2) ≤ ... ≤ key(a_in)

• jak poprzednio, ale klucz z dowiązaniem [k_i, p_i]

• sortowanie wewnętrzne lub zewnętrzne

• warunek stabilności

dla jednakowych wartościach klucza elementy posortowane położone względem siebie w tej kolejności, w jakiej występowały na liście wyjściowej

W opisie algorytmów -

porządkowane ciągi liczb całkowitych a₁...a_n

dodatkowo a₀ = - ∞ a_n+1 = + ∞

Operacja dominująca - porównanie elementów ciągu.{ --------- SelectionSort -------------------------- }

procedure SelectionSort(n: integer; var a: array1int);

var i, j,min,ri : integer;

{ pomocnicze zmienne - i,j,min,ri : integer

sortujemy tablicę a[1..n]

}

begin

for i:=1 to n-1 do

{ etap obliczen: a[1] ≤ a[2] ≤ ... ≤ a[i-1] ≤ a[i..n] }

begin

min := i;

for j := i+1 to n do

if a[j] < a[min] then min:=j;

{nierownosc ostra!}

{a[min] <−−> a[i];} { <−−> zamiana miejscami}

ri := a[i]; a[i] := a[min]; a[min] := ri;

end; {i}

end; {SelectionSort}

{ ------- koniec selection_sort -------- }

Złożoność czasowa:

Pesymistyczna:

W(n) = (n-1) + (n-2) + ... + 1 = n(n-1) /2

zawsze tyle samo, stąd

złożoność oczekiwana A(n) = W(n) = n(n-1) /2

wrażliwość (pesymistyczna, oczekiwana) Δ(n) = 0, δ(n) = 0)

Nie wymaga dodatkowej pamięci - sortuje w miejscu.

S(n) = 0(1)

Algorytm selection sort nie jest stabilny

{ ----------------- InsertionSort ---------------------- }

procedure InsertionSort(n: integer; var a: array1int);

{ pomocnicze zmienne - i,j,v : integer

sortujemy tablice a[1..n]

dla uproszczenia algorytmu wprowadzamy a[0] = - niesk

}

var i,j,v : integer;

begin

a[0]:= −niesk;

for i:= 2 to n do

{na tym etapie jest a[0] ≤ a[1] ≤ ... ≤ a[i-1] }

begin

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

while a[j-1] > v do { nierownosc ostra! }

begin a[j]:= a[j-1]; j:= j-1; end;

{ wszystkie elementy a[j] > a[i] poprzedząjce a[i]

zostaly przesuniete o jedno miejsce w prawo;

w powstalą lukę zostaje wprowadzony element v=a[i]}

a[j]:=v; { element v byl na i-tej pozycji, jest na j-tej}

end; {i}

end; {InsertionSort}

{ -------- koniec InsertionSort ------- }

scalanie dwóch ciągów uporządkowanych

a[1..na], b[1..nb] - uporządkowane

a[i-1]≤ a[i]; i=2,...,na b[j-1]≤ b[j]; i=2,...,nb

połączyć w uporzadkowany c[1..nc] nc=na+nb;

c[i-1]≤ c[i]; i=2,...,nc

Algorytm

ka := 1; kb := 1; a[na+1] := niesk; b[nb+1] := niesk;

kc := 0; nc := na+nb;

while kc < nc do

begin

if a[ka] <= b[kb]

then begin v := a[ka]; ka := ka+1 end

else begin v := b[kb]; kb := kb+1 end

kc := kc+1; c[kc] := v;

end;

procedure merge_sort(a,p,r);

{sortuje elementy podtablicy a[p..r] - rekurencyjnie:

jeżeli p >= r to tablica jest posortowana,

w przeciwnym przyp. a[p..r] dzielimy na a[p..q] i a[q+1..r] }

var q : integer;

begin

if p < r then

begin

q := (p+r) div 2;

merge_sort(a,p,q);

merge_sort(a,q+1,r);

scalaj(a,p,q,r); {scala a[p..q] i a[q+1..r] w

uporządkowaną podtabl. a[p..r]}

end;

end; {merge_sort}

Uwaga:

przy scalaj nie można podstawić niesk w miejsce a[q+1] i a[r+1]

{ ------------------- partition ------------------ }

function partition(le,r: integer; var a: array1int) : integer;

{na wejsciu musi byc le < r }

var iter, k, j, v : integer;

begin

v := a[le]; i := le; j := r +1; iter := 0;

repeat

iter := iter +1;

repeat inc(i) until a[i] ≥ v;

repeat dec(j) until a[j] ≤ v; {nier. nieostre!}

if i < j then

begin k := a[i]; a[i] := a[j]; a[j]:= k end;

until j<=i;

a[le] := a[j]; a[j] := v; partition:=j;

end; {partition}

{ --------- QuickSort ----------------------- }

procedure quicksort(le,r : integer; var a: array1int);

{ do posortowania a[le..r], le<r }

var j : integer;

begin

j:=partition(le,r,a);

{ w wyniku: i < j --> a[i] ≤ a[j], k>j --> a[k] ≤ a[j]}

if j -1 > le then quicksort (le, j-1, a);

if r > j+1 then quicksort (j+1, r, a)

end; {quicksort}



2

sortowanie

2

sortowanie

---