Sortowanie przez scalanie angielskie mergesort



Pobieranie 16.9 Kb.
Data04.05.2016
Rozmiar16.9 Kb.



Sortowanie przez scalanie (angielskie mergesort),

Przykład:

MERGE – SORT (A, p, n)

If p < n then

q := ( p + n ) div 2

MERGE – SORT (A, p, q )

MERGE – SORT (A, q + 1, r )

MERGE (A, p, q, r) MERGE (A, p, q, r)

i:=p


j:=q+1

k:=p


while i <= q and j<=r do

if A[i] > A[j] then

begin

B[k]:=A[j]



j:=j+1

k:=k+1


cdn…

QUICKSORT ( A, p, r )

if p < r

then


q := PARTITION ( A, p, r )

QUICKSORT ( A, p, q )

QUICKSORT ( A, q + 1, r )

PARTITION ( A, p, r )

x := A [ p ]

i := p – 1

j := r + 1

while true do

repeat j := j – 1

until A [ j ] <= x

repeat i := i + 1

until A [ i ] => x

if i < j

then zamień A [ i ] <-> A [ j ]

else

return



Sortowanie przez kopcowanie (angielskie heapsort),

BUILD - HEAP [ A ]

HEAP - SIZE [ A ] := length [ A ]

for i = length [ A ] div 2 downto 1 do

HEAPIFY [ A, i ]

HEAP – SORT ( A )

BUILD – HEAP ( A )

For i := length [ A ] downto 2 do

Zamień A [ i ] < - > A [ 1 ]

HEAP – SIZE ( A ) := HEAP – SIZE ( [ A ] – 1 )

HEAPIFY ( A, 1 )



Merge cd

end


else

B[d]:=A[i]

i:=i+1

k:=k+1


if i>q then

begin


for j=j to r do

B[k] :=A[j]

k:=k+1

end


else

for i=i to q do

B[k]:=A[i]

k:=k+1





Poprzednik


tree predecessor (x)

if left (x) <>nil then

return tree maximum (left(x))

else


begin

y:=parent(x)

while x=left(y)

do

begin



x:=y

y:=parent (y)

end

return y



end



Sortowanie bąbelkowe (angielskie bubble sort), Przykład:

z = true


while z = true do

z = false

for i =1 to n do

if A [ i ] = A [ i + 1 ] then

r := A [ i + 1 ]

A [ i + 1 ]: = A [ i ]

A [ i ] := r

z := true




Sortowanie przez wstawianie (angielskie insertsort

Przykład:

A [ 1 . . n ]

INSERT – SORT

i := 1


i := 1

for j = 2 to lenght [ A] do

key := A [ j ]

i := j – 1

while i > 0 and A [ i ] > key do

A [ i + 1 ] := A [ i ]

i := i – 1

A [ i + 1 ] := key





Dodawanie liczb binarnych


Reszta = 0

for i = 1 to n do

C [ i ] := ( A [ i ] + B [ i ] + Reszta ) mod 2

Reszta := ( A [ i ] + B [ i ] + Reszta ) div 2

C [ i ] := Reszta


Następnik

tree succesor (x);

if right (x) <>nil then

return tree minimum (right(x))

else

begin


y:=parent(x)

while x=right(y) do

begin

x:=y


y:=parent(y)

end;


return y

end;







: baza -> f-7




©absta.pl 2019
wyślij wiadomość

    Strona główna