declare Partition QuickSort

% Puts all elems<Pivot in L1 and others in L2

proc {Partition Pivot L ?L1 ?L2}

case L of nil then

L1 = nil

L2 = nil

[] X|Y then Y1 in

if X < Pivot then

L1 = X|Y1

{Partition Pivot Y Y1 L2}

else

L2 = X|Y1

{Partition Pivot Y L1 Y1}

end

end

end

local

fun {QuickSortD L}

case L of nil then E in E#E

[] X|nil then E in (X|E)#E

[] X|Y then L1 L2 S1 S2 E1 E2 E3 in

{Partition X Y L1 L2}

%Sort L1 and L2 and then return L1+X+L2

S1#(X|E1) = {QuickSortD L1}

S2#E2 = {QuickSortD L2}

E1 = S2

S1#E2

end

end

in

fun {QuickSort L}

S#nil = {QuickSortD L}

in

S

end

end

% Test Partition

local D1 D2 E in

{Partition 5 [5 2 7 3 4] D1 D2}

{Browse D1}

{Browse D2}

end

% Test QuickSort

{Browse {QuickSort nil}}

{Browse {QuickSort [1]}}

{Browse {QuickSort [2 1]}}

{Browse {QuickSort [5 2 7]}}

{Browse {QuickSort [5 2 7 3 4]}}

%=====================================

% Partition that takes difference list and

% returns difference lists

% not used in our program though

proc {Partition N D ?D1 ?D2}

case D of nil then E1 E2 in

D1 = E1#E1

D2 = E2#E2

[] X|Y then Y1 Y2 in

if X < N then

D1 = (X|Y1)#Y2

{Partition N Y Y1#Y2 D2}

else

D2 = (X|Y1)#Y2

{Partition N Y D1 Y1#Y2}

end

end

end

## Thursday, January 29, 2009

### Ch3, Ex15

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment