----------
X-Sun-Data-Type: text
X-Sun-Data-Description: text
X-Sun-Data-Name: text
X-Sun-Encoding-Info: uuencode
X-Sun-Content-Lines: 69
begin 600 text
M2&5R92!I<R!T:&4@;F5X="!O;F4Z(&=H8R=S(&]N;'D@8V]M;65N="!I<R!@
M=6YI;7!L96UE;G1E9"!C:&5C:R<N(%1H90ID971A:6QS(&%R92!G:79E;B!B
M96QO=R!A;F0@22=V92!A='1A8VAE9"!T:&4@;V9F96YD:6YG(&9I;&4@*&IU
M<W0@:6X*8V%S92!3=F5N(&QI:V5S('1O('-P96YD(&$@9F5W($-052!C>6-L
M97,I+@H*0VAE97)S+"!286QF"@H*:F]D(#DW/B!G:&,@+78@+6,@+4\@+5<@
M+69G;&%S9V]W+65X=',@+7)E8V]M<"!1=6EC:U-O<G1);E!L86-E+FQH<R M
M;R!1=6EC:U-O<G1);E!L86-E+F\*5&AE($=L;W)I;W5S($=L87-G;W<@2&%S
M:V5L;"!#;VUP:6QA=&EO;B!3>7-T96TL('9E<G-I;VX@-"XP,"P@<&%T8VAL
M979E;" P"@IL:71E<F%T92!P<F4M<')O8V5S<V]R.@H)+VAO;64O24E)+V$O
M<F%L9B]&4"]G:&,O;&EB+W5N;&ET("!1=6EC:U-O<G1);E!L86-E+FQH<R M
M(" ^/B O=&UP+V=H8S(V,3(V+FQP< H*<F5A;" @(" @(" @,"XP"G5S97(@
M(" @(" @(# N, IS>7,@(" @(" @(" P+C *"D5F9F5C=&EV92!C;VUM86YD
M(&QI;F4Z("UV("UC("U/("U7("UF9VQA<V=O=RUE>'1S("UR96-O;7 @+6\@
M475I8VM3;W)T26Y0;&%C92YO"@I);F5F9F5C=&EV92!#('!R92UP<F]C97-S
M;W(Z"@EE8VAO("=[+2,@3$E.12 Q(")1=6EC:U-O<G1);E!L86-E+FQH<R(@
M+7TG(#X@+W1M<"]G:&,R-C$R-BYC<' @)B8@8V%T("]T;7 O9VAC,C8Q,C8N
M;'!P(#X^("]T;7 O9VAC,C8Q,C8N8W!P"@IR96%L(" @(" @(" P+C *=7-E
M<B @(" @(" @,"XP"G-Y<R @(" @(" @(# N, IG:&,Z8V]M<&EL93I/=71P
M=70@9FEL92!1=6EC:U-O<G1);E!L86-E+F\@9&]E<VXG="!E>&ES= IG:&,Z
M8V]M<&EL93I);G1E<F9A8V4@9FEL92!1=6EC:U-O<G1);E!L86-E+FAI(&1O
M97-N)W0@97AI<W0*9VAC.G)E8V]M<&EL93I);G!U="!F:6QE(%%U:6-K4V]R
M=$EN4&QA8V4N;&AS(&YE=V5R('1H86X@475I8VM3;W)T26Y0;&%C92YO"@I(
M87-K96QL(&-O;7!I;&5R.@H)+VAO;64O24E)+V$O<F%L9B]&4"]G:&,O;&EB
M+VAS8R L+4X@+"U7("PO=&UP+V=H8S(V,3(V+F-P<" @+69W87)N+6]V97)L
M87!P:6YG+7!A='1E<FYS("UF=V%R;BUM:7-S:6YG+6UE=&AO9',@+69W87)N
M+61U<&QI8V%T92UE>'!O<G1S("UF=V%R;BUI;F-O;7!L971E+7!A='1E<FYS
M("UF=V%R;BUU;G5S960M8FEN9',@+69W87)N+75N=7-E9"UI;7!O<G1S("UF
M9VQA<V=O=RUE>'1S("UF9&\M971A+7)E9'5C=&EO;B M9G-I;7!L:69Y(%L@
M("UF:V5E<"US<&5C+7!R86=M82UI9',@+69E<W-E;G1I86PM=6YF;VQD:6YG
M<RUO;FQY("UF<VEM<&PM=68M=7-E+71H<F5S:&]L9# @+69C;&]N92UB:6YD
M<R M9FUA>"US:6UP;&EF:65R+6ET97)A=&EO;G,Q("UF<&5D86YT:6,M8F]T
M=&]M<R!=("UF<W!E8VEA;&ES92UO=F5R;&]A9&5D(" M9G-P96-I86QI<V4@
M+69S:6UP;&EF>2!;(" M9F9L;V%T+6QE=',M97AP;W-I;F<M=VAN9B M9F9L
M;V%T+7!R:6UO<',M;VL@+69C87-E+6]F+6-A<V4@+69D;RUC87-E+65L:6T@
M+69C87-E+6UE<F=E("UF9&\M;&%M8F1A+65T82UE>'!A;G-I;VX@+69R975S
M92UC;VX@+69P961A;G1I8RUB;W1T;VUS(" M9FUA>"US:6UP;&EF:65R+6ET
M97)A=&EO;G,T(" M9F-L;VYE+6)I;F1S(%T@+69F=6QL+6QA>FEN97-S("UF
M9FQO870M:6YW87)D<R M9G-I;7!L:69Y(%L@("UF9FQO870M;&5T<RUE>'!O
M<VEN9RUW:&YF("UF9FQO870M<')I;6]P<RUO:R M9F-A<V4M;V8M8V%S92 M
M9F1O+6-A<V4M96QI;2 M9F-A<V4M;65R9V4@+69D;RUE=&$M<F5D=6-T:6]N
M("UF9&\M;&%M8F1A+65T82UE>'!A;G-I;VX@+69R975S92UC;VX@("UF<&5D
M86YT:6,M8F]T=&]M<R @+69M87@M<VEM<&QI9FEE<BUI=&5R871I;VYS-" @
M72 M9G-T<FEC=&YE<W,@+69S:6UP;&EF>2!;(" M9F9L;V%T+6QE=',M97AP
M;W-I;F<M=VAN9B M9F9L;V%T+7!R:6UO<',M;VL@+69C87-E+6]F+6-A<V4@
M+69D;RUC87-E+65L:6T@+69C87-E+6UE<F=E("UF9&\M;&%M8F1A+65T82UE
M>'!A;G-I;VX@+69R975S92UC;VX@+69L970M=&\M8V%S92 M9G!E9&%N=&EC
M+6)O='1O;7,@("UF;6%X+7-I;7!L:69I97(M:71E<F%T:6]N<S0@(%T@+69F
M;&]A="UI;G=A<F1S("UF<VEM<&QI9GD@6R @+69F;&]A="UL971S+65X<&]S
M:6YG+7=H;F8@+69F;&]A="UP<FEM;W!S+6]K("UF8V%S92UO9BUC87-E("UF
M9&\M8V%S92UE;&EM("UF8V%S92UM97)G92 M9F1O+6QA;6)D82UE=&$M97AP
M86YS:6]N("UF<F5U<V4M8V]N("UF;&5T+71O+6-A<V4@+69I9VYO<F4M:6YL
M:6YE+7!R86=M82 @+69P961A;G1I8RUB;W1T;VUS(" M9FUA>"US:6UP;&EF
M:65R+6ET97)A=&EO;G,T("!=("UF;&%M8F1A+6QI9G0@(" M9FQE="UN;RUE
M<V-A<&4@+69W87)N+6]V97)L87!P:6YG+7!A='1E<FYS("UF=V%R;BUM:7-S
M:6YG+6UE=&AO9',@+69W87)N+61U<&QI8V%T92UE>'!O<G1S("UF:&DM=F5R
M<VEO;CTT,# @+6AI;6%P/2XE+FAI.B]H;VUE+TE)22]A+W)A;&8O1E O9VAC
M+VQI8B]I;7!O<G1S+V5X=',E+FAI.B]H;VUE+TE)22]A+W)A;&8O1E O9VAC
M+VQI8B]I;7!O<G1S+V5X=',E+FAI.B]H;VUE+TE)22]A+W)A;&8O1E O9VAC
M+VQI8B]I;7!O<G1S+W-T9"4N:&D@(" M=B M:&EF:6QE/2]T;7 O9VAC,C8Q
M,C8N:&D@+5,]+W1M<"]G:&,R-C$R-BYS("U&/2 M1D@]("M25%,@+4@V,# P
M,# P("U+,3 P,# P, I';&%S9V]W($AA<VME;&P@0V]M<&EL97(L('9E<G-I
M;VX@-"XP,"P@9F]R($AA<VME;&P@,2XT"@IU;FEM<&QE;65N=&5D(&-H96-K
M"G)E86P@(" @(" @,3$N,0IU<V5R(" @(" @(#$P+C4*<WES(" @(" @(" @
M,"XR"F1E;&5T:6YG+BXN("]T;7 O9VAC,C8Q,C8N;'!P("]T;7 O9VAC,C8Q
M,C8N8W!P("]T;7 O9VAC,C8Q,C8N:&D@+W1M<"]G:&,R-C$R-BYS(" *"G)M
3("UF("]T;7 O9VAC,C8Q,C8J"C8N
end
----------
X-Sun-Data-Type: default
X-Sun-Data-Name: QuickSortInPlace.lhs
X-Sun-Charset: us-ascii
X-Sun-Content-Lines: 86
%-------------------------------= --------------------------------------------
\chapter{In place quick sort}
%-------------------------------= --------------------------------------------
%align
> module QuickSortInPlace (module QuickSortInPlace)
> where
> import Array
> import ST
> import LibBase
%align 33
%-------------------------------= --------------------------------------------
\section{Median of three quick sort}
%-------------------------------= --------------------------------------------
> swap a i j = do { v <- readSTArray a i
> ; w <- readSTArray a j
> ; writeSTArray a i w
> ; writeSTArray a j v }
> qsortInPlace :: Rel a -> STArray s Int a -> (Int, Int) -> ST s ()
> qsortInPlace (<=) a (l, r)
> | l >= r = return ()
> | otherwise = do { m <- median3 l ((l + r) `div` 2) r
> ; swap a l m
> ; pivot <- readSTArray a l
> ; j <- partition pivot (l - 1) (r + 1)
> ; qsortInPlace (<=) a (l, j)
> ; qsortInPlace (<=) a (j + 1, r) }
> where
Median von 3-Elementen.
> median3 i j k = do { u <- readSTArray a i
> ; v <- readSTArray a j
> ; w <- readSTArray a k
> ; return (
> if u <= v
> then if v <= w then j
> else if u <= w then k else i
> else if v <= w then
> if u <= w then i else k
> else j ) }
Partitionierung. Vorsicht: siehe Bemerkungen bei Corman.
> partition pivot i j = do { i' <- left (i + 1)
> ; j' <- right (j - 1)
> ; if i' < j' then
> do { swap a i' j'
> ; partition pivot i' j' }
> else
> return j' }
> where left i = do { v <- readSTArray a i
> ; if pivot <= v then return i
> else left (i + 1) }
> right j = do { v <- readSTArray a j
> ; if v <= pivot then return j
> else right (j - 1) }
Kapselung.
> qsortArrayBy :: Rel a -> Array Int a -> Array Int a
> qsortArrayBy (<=) a = runST (
> do { b <- newSTArray (bounds a) undefined
> ; sequence [ writeSTArray b i (a ! i) | i <- indices a ]
> ; qsortInPlace (<=) b (bounds a)
> ; freezeSTArray b } )
Vorsicht mit leeren Feldern!
> qsort :: (Ord a) => [a] -> [a]
> qsort = qsortBy (<=)
>
> qsortBy :: Rel a -> [a] -> [a]
> qsortBy (<=) = elems . qsortArrayBy (<=) . fromList
> fromList as = listArray (0, length as - 1) as
%-------------------------------------------------------------------------------
\subsection{Quicksort by Bentley and McIlroy}
%-------------------------------------------------------------------------------
