digitalmars.D - Multisort

dsimcha (380/380) Jul 06 2008 I've been working on implementing some statistics functions in D, and no...

bearophile (13/13) Jul 06 2008 I haven't tried your code (yet), but I suggest you to not use too much l...
superdan (16/25) Jul 06 2008 yarp i needed this 2. sounds good but it's unnecessary. sort does all th...

dsimcha <dsimcha yahoo.com> writes:

I've been working on implementing some statistics functions in D, and noticed
that it would be nice if a multisort function were in Phobos.  Such a function
would take N arrays in and sort them by the first one.  The common way to
handle something like this seems to be to make a struct with the fields, make
opCmp point to whatever field you want to sort by, and then use a regular
sorting algorithm.  This is slow and a pain.  I've implemented a few different
multisort functions, along with documentation and unit testing, and would like
to contribute them to Phobos.  I've attached the source file and the Ddoc
documentation.
begin 644 phobosSort.d
M+R\ 5W)I='1E;B!I;B!T:&4 1"!P<F]G<F%M;6EN9R!L86YG=6%G92X-" T*

M("H-"B`J("!4:&ES('-O9G1W87)E(&ES('!R;W9I9&5D("=A<RUI<R<L('=I
M=&AO=70 86YY(&5X<')E<W, ;W( :6UP;&EE9`T*("H ('=A<G)A;G1Y+B!)
M;B!N;R!E=F5N="!W:6QL('1H92!A=71H;W)S(&)E(&AE;&0 ;&EA8FQE(&9O
M<B!A;GD 9&%M86=E<PT*("H (&%R:7-I;F< 9G)O;2!T:&4 =7-E(&]F('1H

M;R!A;GEO;F4 =&\ =7-E('1H:7, <V]F='=A<F4 9F]R(&%N>2!P=7)P;W-E
M+`T*("H (&EN8VQU9&EN9R!C;VUM97)C:6%L(&%P<&QI8V%T:6]N<RP 86YD
M('1O(&%L=&5R(&ET(&%N9"!R961I<W1R:6)U=&4 :70-"B`J("!F<F5E;'DL

M("H (&\ (%1H92!O<FEG:6X ;V8 =&AI<R!S;V9T=V%R92!M=7-T(&YO="!B
M92!M:7-R97!R97-E;G1E9#L
M=&AA="!Y;W4 =W)O=&4 =&AE(&]R:6=I;F%L('-O9G1W87)E+B!)9B!Y;W4 
M=7-E('1H:7, <V]F='=A<F4-"B`J("` ("!I;B!A('!R;V1U8W0L(&%N(&%C
M:VYO=VQE9&=M96YT(&EN('1H92!P<F]D=6-T(&1O8W5M96YT871I;VX =V]U
M;&0 8F4-"B`J("` ("!A<'!R96-I871E9"!B=70 :7, ;F]T(')E<75I<F5D
M+ T*("H (&\ ($%L=&5R960 <V]U<F-E('9E<G-I;VYS(&UU<W0 8F4 <&QA

M;6ES<F5P<F5S96YT960 87, 8F5I;F< =&AE(&]R:6=I;F%L('-O9G1W87)E
M+ T*("H (&\ (%1H:7, ;F]T:6-E(&UA>2!N;W0 8F4 <F5M;W9E9"!O<B!A
M;'1E<F5D(&9R;VT 86YY('-O=7)C90T*("H ("` (&1I<W1R:6)U=&EO;BX-

M=F5R<VEO;BAU;FET=&5S="D >PT*("` (&EM<&]R="!S=&0N<W1D:6\L('-T
M9"YR86YD;VTL('-T9"YM871H.PT*("` ('9O:60 ;6%I;B`H*2![?0T*?0T*

M;VXN("!5<V5F=6P =VAE;B!F87-T(&UE;6]R>0T*("H 86QL;V-A=&EO;B!I
M<R!N96-E<W-A<GDL(&%N9"!T:&4 :6YI=&EA;"!V86QU97, 87)E(&1E9FEN

M;VED*%0I*'-I>F5?="!L96YG=& I('L-"B` ("!4*B!P='( /2!C87-T*%0J
M*2!S=&0N9V,N;6%L;&]C*&QE;F=T:"`J(%0N<VEZ96]F*3L-"B` ("!R971U

M;W( <W1A8FQE4V5L96-T:6]N4V]R="X-"G9O:60 <F]T871E4FEG:'0H5"DH


M(#T

M=&5M<#L-"GT-" T*+RHJ56YS=&%B;&4 <75I8VL ;75L=&ES;W)T+B` 4V]R


M('%S;W)T*%0N+BXI*%0 9&%T82D >R` +R]&87-T97( =&AA;B!S=&%B;&4 



M9W1H("\ ,CL-"B` ("!F;W)E86-H*&%R<F%Y.R!D871A*2!S=V%P*&%R<F%Y
M6VUI9&1L95TL(&%R<F%Y6R0M,5TI.R` +R]!=F]I9"!W;W)S="!C87-E(&EF
M(&%L<F5A9'D <V]R=&5D+ T*("` (%0 ;&5S<RP 9W)E871E<CL-"B` ("!S
M:7IE7W0 <W=A<$EN9&5X(#T ,#L-
M,%TN;&5N9W1H("T ,2D >PT*("` ("` ("!I9BAD871A6S!=6VE=(#P 9&%T

M*2!S=V%P*&%R<F%Y6VE=+"!A<G)A>5MS=V%P26YD97A=*3L-"B` ("` ("` 

M8V H:2P 87)R87D[(&1A=&$I('L-"B` ("` ("` <W=A<"AA<G)A>5LD+3%=
M+"!A<G)A>5MS=V%P26YD97A=*3L-"B` ("` ("` ;&5S<UMI72`](&%R<F%Y



M:V4 =&AI<R!F=6YC=&EO;B!L:6ME(")N;W)M86PB('%S;W)T(&EF(&1A=&$N
M;&5N9W1H(&ES(&]N92X-"GT-" T*+RHJ4W1A8FQE('9E<G-I;VX ;V8 <7-O
M<G0H*2!F=6YC=&EO;BX ($1O97, ;F]T('-O<G0 :6X <&QA8V4L(&%N9`T*
M("H :7, 86)O=70 ,34E('-L;W=E<B!T:&%N('5N<W1A8FQE('9E<G-I;VXL
M('-O('5S92!O;FQY('=H96X ;F5C97-S87)Y+ T*("H 06QS;RP <&5R9F]R
M;6%N8V4 :7, 3RA.7C(I(&]N('!R92US;W)T960 87)R87ES+"!B96-A=7-E

M;'0 ;W( :6UP;W-S:6)L92!I;B!A('-T86)L92!Q<V]R="X-"B`J('-T86)L
M95%S;W)T(&-R96%T97, =&5M<"!V87)I86)L97, 86YD(&9O<G=A<F1S(&%L


M;B!C87-E('1H92!U<V5R('=A;G1S('1O(')E8WEC;&4 <')E+6%L;&]C871E

M9&%T82D >PT*("` ('1Y<&5O9BAD871A*2!T96UP.PT*("` (&9O<F5A8V H
M:2P 87)R87D[('1E;7`I('L-"B` ("` ("` =&5M<%MI72`](&YE=U9O:60A
M*'1Y<&5O9BAD871A6VE=6S!=*2DH9&%T85MI72YL96YG=& I.PT*("` ('T-

M96%C:"AI+"!A<G)A>3L =&5M<"D >PT*("` ("` ("!D96QE=&4 =&5M<%MI

M;', ;VX ;&%R9V4 87)R87ES+ T*("` ('T-"B` ("!R971U<FX 9&%T85LP
M73L-"GT-" T*5%LP72!S=&%B;&51<V]R=$)A8VM%;F0H5"XN+BDH5"!D871A
M26XI('L ("\O07-S=6UE<R!F:7)S="!H86QF(&]F(&EN<'5T(&ES(&1A=&$L






M(&QE<W,L(&=R96%T97(L(&QE<W-496UP+"!G<F5A=&5R5&5M<#L-"B` ("!S
M:7IE7W0 :6YD97  /2`P.PT*("` (&9O<F5A8V H:3L ,"XN9&%T85LP72YL


M82D =&5M<%MT:5U;:6YD97A=(#T

M<F%Y.R!D871A*2!T96UP6W1I75MI;F1E>%T /2!A<G)A>5LD+3%=.PT*("` 
M('-I>F5?="!M:60 /2!I;F1E>#L-"B` ("!I;F1E>"LK.PT*("` (&9O<F5A

M=&%;,%U;:5T /B!D871A6S!=6R0M,5TI('L-"B` ("` ("` ("` (&9O<F5A
M8V H=&DL(&%R<F%Y.R!D871A*2!T96UP6W1I75MI;F1E>%T /2!A<G)A>5MI

M("` 9F]R96%C:"AI+"!A<G)A>3L =&5M<"D >PT*("` ("` ("!D871A6VE=
M6S`N+B1=(#T
M87)R87D[(&1A=&$I('L-"B` ("` ("` ;&5S<UMI72`](&%R<F%Y6S`N+FUI


M("` (&=R96%T97)496UP6VE=(#T =&5M<%MI75MM:60 *R`Q+BXD73L-"B` 

M"B` ("!S=&%B;&51<V]R=$)A8VM%;F0H9W)E871E<BP 9W)E871E<E1E;7`I

M<G0N("!486ME<R!I;B!.(&%R<F%Y<R!A;F0 <V]R=', =&AE;2!B>2!T:&4-
M"B`J(&9I<G-T(&%R<F%Y+B` 268 ;&%S="!A<F=U;65N="!I<R!A('5L;VYG

M('1H870 =V]U;&0 :&%V92!B965N(&YE8V5S<V%R>2!T;R!B=6)B;&4 <V]R
M=`T*("H =&AE(&1A=&$N("!4:&ES(&ES('5S969U;"!F;W( 8V%L8W5L871I
M;F< <W1A=&ES=&EC86P 9G5N8W1I;VYS(&QI:V4-"B`J($ME;F1A;&P 8V]R
M<F5L871I;VXN("!3;&]W97( =&AA;B!S=&%B;&51<V]R="!O;B!A=F5R86=E
M+"!U<V4 ;VYL>0T*("H :68 >6]U(&YE960 =&\ 8V]U;G0 =&AE('-W87!S
M(&9O<B!S;VUE('-T871I<W1I8V%L(&9U;F-T:6]N+`T*("H ;W( :68 >6]U
M(&YE960 3RA.(&QO9R!.*2!W;W)S="!C87-E('!E<F9O<FUA;F-E+B!,:6ME


M*B!E;F0 9G5N8W1I;VXN*B\-" T*5%LP72!M97)G95-O<G0H5"XN+BDH5"!D

M+3%=*2DI('L ("\O5&AI<R!S=&%T:6, :68 8FQO8VL 86-C;W5N=', 9F]R

M('!A<W-E9"X-"B` ("` ("` :6YV87)I86YT('5I;G0 9&P /2!D871A+FQE


M/2!D871A+FQE;F=T:#L-"B` ("` ("` =6QO;F< 9'5M;7D /2!V;VED.R` 
M+R]4:&ES(&ES(&$ 9'5M;7D =F%R:6%B;&4N("!)="!D;V5S;B=T(&YE960 

M/2`F9'5M;7D[("`O+TUA:V5S('1H:6YG<R!A(&QO="!E87-I97( :68 22!U
M<V4 82!D=6UM>2!S=V%P8V]U;G0 =F%R:6%B;&4 :6YS=&%E9"!O9B!W<FET

M='EP96]F*&1A=&%;,"XN9&Q=*2!T96UP.PT*("` (&9O<F5A8V H:2P 87)R
M87D[('1E;7`I('1E;7!;:5T /2!N97=6;VED(2AT>7!E;V8H9&%T85MI75LP
M72DI*&1A=&%;:5TN;&5N9W1H*3L-"B` ("!46S!=(&]U='!U="`](&UE<F=E

M("` 9F]R96%C:"AT:2P 87)R87D[('1E;7`I(&1E;&5T92!T96UP6W1I73L-

M;F0H5"XN+BDH5"!D871A26XI('L-"B` ("!A=71O(&1A=&$ /2!D871A26Y;
M,"XN9&%T84EN+FQE;F=T:"\R73L-"B` ("!A=71O('1E;7` /2!D871A26Y;
M9&%T84EN+FQE;F=T:"\R+BXD+3%=.PT*("` ('5L;VYG*B!S=V%P0V]U;G0 

M"B` ("` ("` <F5T=7)N('-T86)L95-E;&5C=&EO;E-O<G0H9&%T82P <W=A


M3&5F="P =&5M<%)I9VAT.PT*("` (&9O<F5A8V H=&DL(&%R<F%Y.R!D871A

M("` (')I9VAT6W1I72`](&%R<F%Y6VAA;&8N+B1=.PT*("` ("` ("!T96UP
M3&5F=%MT:5T /2!T96UP6W1I75LP+BYH86QF73L-"B` ("` ("` =&5M<%)I
M9VAT6W1I72`]('1E;7!;=&E=6VAA;&8N+B1=.PT*("` ('T-"B` ("!M97)G
M95-O<G1"86-K16YD*&QE9G0L('1E;7!,969T+"!S=V%P0V]U;G0I.PT*("` 
M(&UE<F=E4V]R=$)A8VM%;F0H<FEG:'0L('1E;7!2:6=H="P <W=A<$-O=6YT
M*3L-"B` ("!M97)G92AL969T+"!R:6=H="P =&5M<"P <W=A<$-O=6YT*3L-
M"B` ("!F;W)E86-H*'1I+"!A<G)A>3L =&5M<"D >PT*("` ("` ("!D871A
M6W1I75LP+BXD72`]('1E;7!;=&E=6S`N+B1=.PT*("` ('T-"B` ("!R971U
M<FX 9&%T85LP73L-"GT-" T*+R\O365R9V4 9G5N8W1I;VX 9F]R(&UE<F=E




M/2`P*3L ("\O069T97( =&%K:6YG(&]U="!S=V%P8V]U;G0L(&YU;6)E<B!O
M9B!A<F=U;65N=', <VAO=6QD(&)E(&1I=FES:6)L92!B>2!T:')E92X-"B` 
M("!A=71O(&QE9G0 /2!D871A6S`N+F1L+S-=.PT*("` (&%U=&\ <FEG:'0 

M6V1L*C(O,RXN9&Q=.PT*("` ('-T871I8R!A<W-E<G0H;&5F="YL96YG=&  
M/3T <FEG:'0N;&5N9W1H("8F(')I9VAT+FQE;F=T:"`]/2!R97-U;'0N;&5N
M9W1H*3L-"B` ("!S:7IE7W0 :2`](')E<W5L=%LP72YL96YG=&  +2`Q.PT*
M("` ("\O=W)I=&5F*&QE9G0L(")<="(L(')I9VAT+"`B7'0B+"`B(#X^("( 
M*3L-"B` ("!W:&EL92AL969T6S!=+FQE;F=T:"`F)B!R:6=H=%LP72YL96YG



M6W1I75LD+3%=.PT*("` ("` ("` ("` ("` (')I9VAT6W1I72YL96YG=&  
M/2!R:6=H=%MT:5TN;&5N9W1H("T ,3L-"B` ("` ("` ("` ('T-"B` ("` 
M("` ?2!E;'-E('L-"B` ("` ("` ("` ("IS=V%P0V]U;G0 *ST <FEG:'1;
M,%TN;&5N9W1H.PT*("` ("` ("` ("` 9F]R96%C:"AT:2P 87)R87D[(')E
M<W5L="D >PT*("` ("` ("` ("` ("` (')E<W5L=%MT:5U;:5T /2!L969T
M6W1I75LD+3%=.PT*("` ("` ("` ("` ("` (&QE9G1;=&E=+FQE;F=T:"`]

M('T-"B` ("` ("` :2TM.PT*("` ('T-"B` ("!I9BAR:6=H=%LP72YL96YG
M=& I('L-"B` ("` ("` 9F]R96%C:"AT:2P 87)R87D[(')E<W5L="D >PT*
M("` ("` ("` ("` <F5S=6QT6W1I75LP+BYR:6=H=%MT:5TN;&5N9W1H72`]

M(&9O<F5A8V H=&DL(&%R<F%Y.R!R97-U;'0I('L-"B` ("` ("` ("` (')E
M<W5L=%MT:5U;,"XN;&5F=%MT:5TN;&5N9W1H72`](&QE9G1;=&E=.PT*("` 

M+RHJ0G5B8FQE(&UU;'1I<V]R="!F=6YC=&EO;BX (%5S969U;"!O;FQY(&)E
M8V%U<V4 :70G<R!E87-Y('1O(&EM<&QE;65N=`T*("H 86YD('1E<W0 ;W1H
M97( <V]R=&EN9R!F=6YC=&EO;G, 86=A:6YS="X ($-O=6YT<R!S=V%P<R!I

M=6)B;&53;W)T*%0N+BXI*%0 9&%T82D >PT*("` ("\O268 ;&%S="!A<F=U
M;65N="!I<R!A('!O:6YT97( =&\ 86X :6YT96=E<B!T>7!E+"!I;F-R96UE


M(&$ <&]I;G1E<B!T;R!A;B!I;G1E9V5R+"!U;F1E9FEN960 8F5H879I;W(N

M(&EN=F%R:6%N="!U:6YT(&1L(#T 9&%T82YL96YG=&  +2`Q.PT*("` (&5L
M<V4 :6YV87)I86YT('5I;G0 9&P /2!D871A+FQE;F=T:#L-"B` ("!I9BAD

M<W=A<$5X96-U=&5D(#T =F]I9#L-

M("` (&9O<F5A8V H:CL ,2XN9&%T85LP72YL96YG=& I('L-"B` ("` ("` 
M("` (&EF*&1A=&%;,%U;:BTQ72`^(&1A=&%;,%U;:ETI('L-"B` ("` ("` 
M("` ("` ("!S=V%P17AE8W5T960 /2`Q.PT*("` ("` ("` ("` ("` ('-T
M871I8R!I9B A:7-!<G)A>2$H='EP96]F*&1A=&%;)"TQ72DI*2`H*BAD871A
M6R0M,5TI*2LK.PT*("` ("` ("` ("` ("` (&9O<F5A8V H87)R87D[(&1A
M=&%;,"XN9&Q=*2!S=V%P*&%R<F%Y6VHM,5TL(&%R<F%Y6VI=*3L-"B` ("` 
M("` ("` ('T-"B` ("` ("` ?0T*("` ("` ("!I9B A<W=A<$5X96-U=&5D



M;E-O<G0H5"XN+BDH5"!D871A*2![("`O+U5S960 9F]R('-M86QL('-U8F%R

M='5R;B!D871A6S!=.PT*("` (&9O<F5A8V H:3L ,"XN9&%T85LP72YL96YG
M=& M,2D >PT*("` ("` ("!S:7IE7W0 ;6EN4F]W(#T :3L-"B` ("` ("` 

M("!I9BAD871A6S!=6VI=(#P
M("` ("` ("` ;6EN4F]W(#T :CL-"B` ("` ("` ("` ('T-"B` ("` ("` 
M?0T*("` ("` ("!F;W)E86-H*&%R<F%Y.R!D871A*2!S=V%P*&%R<F%Y6VE=


M86QL('-U8F%R<F%Y<R!I;B!S=&%B;&51<V]R="!A;F0 ;65R9V53;W)T+ T*
M("H 268 ;&%S="!A<F=U;65N="!I<R!A('5L;VYG*BP :V5E<', =')A8VL 

M96-E<W-A<GD :68 =&AI<R!W97)E(&$ 8G5B8FQE('-O<G0N*B\-" T*5%LP
M72!S=&%B;&5396QE8W1I;VY3;W)T*%0N+BXI*%0 9&%T82D >R` +R]5<V5D
M(&9O<B!S;6%L;"!S=6)A<G)A>7, :6X <W1A8FQE47-O<G0L(&UE<F=E4V]R
M="X-"B` ("!S=&%T:6, :68H(6ES07)R87DA*'1Y<&5O9BAD871A6R0M,5TI

M96QS92!I;G9A<FEA;G0 =6EN="!D;"`](&1A=&$N;&5N9W1H.PT*("` (&EF
M*&1A=&%;,%TN;&5N9W1H(#P ,BD >W)E='5R;B!D871A6S!=.WT-"B` ("!F


M6S!=+FQE;F=T:"D >PT*("` ("` ("` ("` :68H9&%T85LP75MJ72`\(&1A
M=&%;,%U;;6EN4F]W72D >PT*("` ("` ("` ("` ("` (&UI;E)O=R`](&H[

M<G)A>3L 9&%T85LP+BYD;%TI(')O=&%T95)I9VAT*&%R<F%Y6VDN+FUI;E)O




M=6YI='1E<W0 >R` +R]087)T<R!O9B!T:&ES('1E<W0 =&AE('-O<G0 9G5N
M8W1I;VYS(&%G86EN<W0 96%C:"!O=&AE<B!B>2!C:&5C:VEN9R!F;W( 86=R
M965M96YT+B` 07-S=6UE<R!T:&5Y('=O;B=T($%,3"!B92!W<F]N9R!I;B!T





M;&%C94-O=6YT+"!S<T-O=6YT.PT*("` ("` ("!S:7IE7W0 ;&]W97)";W5N
M9"`]('5N:69O<FTH9V5N+"`P+"!Q<U1E<W0N;&5N9W1H*3L ("\O3F5E9"!T
M;R!T97-T(&$ 8G5N8V  ;V8 9&EF9F5R96YT('-I>F5S+"!E<W!E8VEA;&QY
M(&9O<B!M97)G92!S;W)T+ T*("` ("` ("!S:7IE7W0 =7!P97)";W5N9"`]
M('5N:69O<FTH9V5N+"`P+"!Q<U1E<W0N;&5N9W1H*3L-"B` ("` ("` :68H
M=7!P97)";W5N9"`\(&QO=V5R0F]U;F0I('-W87`H=7!P97)";W5N9"P ;&]W

M.PT*("` ("` ("!U:6YT6UT ;7-497-T(#T <7-497-T+F1U<"P (&)S5&5S
M="`]('%S5&5S="YD=7`L('-S5&5S="`]('%S5&5S="YD=7`L('-S<U1E<W0 
M/2!Q<U1E<W0N9'5P.PT*("` ("` ("!Q<U1E<W1;;&]W97)";W5N9"XN=7!P
M97)";W5N9%TN<7-O<G0H*3L-"B` ("` ("` ;7-497-T6VQO=V5R0F]U;F0N

M<U1E<W1;;&]W97)";W5N9"XN=7!P97)";W5N9%TN<W1A8FQE4V5L96-T:6]N


M;W=E<D)O=6YD+BYU<'!E<D)O=6YD72YB=6)B;&53;W)T*"9B<T-O=6YT*3L-
M"B` ("` ("` 87-S97)T*&ES4V]R=&5D*'%S5&5S=%ML;W=E<D)O=6YD+BYU
M<'!E<D)O=6YD72DI.PT*("` ("` ("!A<W-E<G0H:7-3;W)T960H8G-497-T

M<U-O<G1E9"AS<U1E<W1;;&]W97)";W5N9"XN=7!P97)";W5N9%TI*3L-"B` 
M("` ("` 87-S97)T*&ES4V]R=&5D*'-S<U1E<W1;;&]W97)";W5N9"XN=7!P
M97)";W5N9%TI*3L-"B` ("` ("` 87-S97)T*&ES4V]R=&5D*&US5&5S=%ML

M;W5N="`]/2!M<T-O=6YT*3L-"B` ("` ("` 87-S97)T*&US0V]U;G0 /3T 

M;V8 ;75L=&ES;W)T<SH-"B` ("!U:6YT6UT 8D]N92`](&YE=R!U:6YT6S$P



M9F]R96%C:"AI+"!R968 ;3L 8E1W;RD ;2`]('5N:69O<FTH9V5N+"`P+"`Q

M92!S;W)T<RX-"B` ("` ("` <VEZ95]T(&QO=V5R0F]U;F0 /2!U;FEF;W)M
M*&=E;BP ,"P 8D]N92YL96YG=& I.PT*("` ("` ("!S:7IE7W0 =7!P97)"

M(&EF*'5P<&5R0F]U;F0 /"!L;W=E<D)O=6YD*2!S=V%P*'5P<&5R0F]U;F0L
M(&QO=V5R0F]U;F0I.PT*("` ("` ("!R86YD;VU3:'5F9FQE*&)/;F4L(&=E

M("` =6EN=%M=('%/;F4 /2!B3VYE+F1U<"P <51W;R`](&)4=V\N9'5P+"!S
M3VYE(#T 8D]N92YD=7`L('-4=V\ /2!B5'=O+F1U<"P ;T\ /2!B3VYE+F1U
M<"P =$\ /2!B5'=O+F1U<"P-"B` ("` ("` ("` (&U/;F4 /2!B3VYE+F1U
M<"P ;51W;R`](&)4=V\N9'5P.PT*("` ("` ("!B=6)B;&53;W)T*&)/;F4L
M(&)4=V\I.PT*("` ("` ("!S=&%B;&5396QE8W1I;VY3;W)T*'-/;F4L('-4

M('-T86)L95%S;W)T*'%/;F4L('%4=V\I.PT*("` ("` ("!A<W-E<G0H:7-3
M;W)T960H<T]N92DI.PT*("` ("` ("!A<W-E<G0H:7-3;W)T960H8D]N92DI
M.PT*("` ("` ("!A<W-E<G0H:7-3;W)T960H<4]N92DI.PT*("` ("` ("!A
M<W-E<G0H:7-3;W)T960H;4]N92DI.PT*("` ("` ("!A<W-E<G0H<U1W;R`]

M("` (&%S<V5R="AQ5'=O(#T](&U4=V\I.PT*("` ('T-"B` ("!W<FET969L
<;B B4&%S<V5D('-O<G0 =&5S="XB*3L-"GT-" ``
`
end
begin 644 phobosSort.html

M(B!C;VYT96YT/2)T97AT+VAT;6P[(&-H87)S970]=71F+3 B/ T*"3QT:71L

M;V)O<U-O<G0\+V Q/ T*"3PA+2T 1V5N97)A=&5D(&)Y($1D;V, 9G)O;2!P


M9SX\+V1T/ T*/&1D/E)E='5R;G, 82!N97< 5%M=+"!S:VEP<&EN9R!I;FET

M=&EO;B!I<R!N96-E<W-A<GDL(&%N9"!T:&4 :6YI=&EA;"!V86QU97, 87)E
M(&1E9FEN:71E;'D-"B!N;W0 9V]I;F< =&\ 8F4 =7-E9"X-"CQB<CX\8G(^


M(&9U;F-T:6]N(&9O<B!S=&%B;&5396QE8W1I;VY3;W)T+ T*/&)R/CQB<CX-
M" T*/"]D9#X-"CQD=#X\8FEG/E1;,%T /'4^<7-O<G0\+W4^*%0N+BXI*%0 
M/&D^9&%T83PO:3XI.PT*/"]B:6<^/"]D=#X-"CQD9#Y5;G-T86)L92!Q=6EC
M:R!M=6QT:7-O<G0N("!3;W)T<R!.(&%R<F%Y<R!B>2!F:7)S="!A<G)A>2X-
M"B!&87-T97( =&AA;B!S=&%B;&4 =F5R<VEO;BP 86YD('-O<G1S(&EN('!L

M86)L95%S;W)T/"]U/BA4+BXN*2A4(#QI/F1A=&$\+VD^*3L-"CPO8FEG/CPO


M;&]W97( =&AA;B!U;G-T86)L92!V97)S:6]N+"!S;R!U<V4 ;VYL>2!W:&5N
M(&YE8V5S<V%R>2X-"B!!;'-O+"!P97)F;W)M86YC92!I<R!/*$Y>,BD ;VX 
M<')E+7-O<G1E9"!A<G)A>7,L(&)E8V%U<V4 8VAO;W-I;F< 86X-"B!I;G1E
M;&QI9V5N="!P:79O="!I<R!D:69F:6-U;'0 ;W( :6UP;W-S:6)L92!I;B!A
M('-T86)L92!Q<V]R="X-"B`\=3YS=&%B;&51<V]R=#PO=3X 8W)E871E<R!T
M96UP('9A<FEA8FQE<R!A;F0 9F]R=V%R9', 86QL(&1A=&$ =&\-"B!S=&%B
M;&51<V]R=$)A8VM%;F0N("!(;W=E=F5R+"!S=&%B;&51<V]R=$)A8VM%;F0 



M*%0N+BXI*%0 /&D^9&%T83PO:3XI.PT*/"]B:6<^/"]D=#X-"CQD9#Y-97)G
M92!M=6QT:7-O<G0N("!486ME<R!I;B!.(&%R<F%Y<R!A;F0 <V]R=', =&AE
M;2!B>2!T:&4-"B!F:7)S="!A<G)A>2X ($EF(&QA<W0 87)G=6UE;G0 :7, 
M82!U;&]N9RHL(&EN8W)E;65N=', =&AI<R!B>0T*('1H92!N=6UB97( ;V8 
M<W=A<', =&AA="!W;W5L9"!H879E(&)E96X ;F5C97-S87)Y('1O(&)U8F)L

M871I;F< <W1A=&ES=&EC86P 9G5N8W1I;VYS(&QI:V4-"B!+96YD86QL(&-O
M<G)E;&%T:6]N+B` 4VQO=V5R('1H86X <W1A8FQE47-O<G0 ;VX 879E<F%G
M92P =7-E(&]N;'D-"B!I9B!Y;W4 ;F5E9"!T;R!C;W5N="!T:&4 <W=A<', 

M960 3RA.(&QO9R!.*2!W;W)S="!C87-E('!E<F9O<FUA;F-E+B!,:6ME('-T

M<"!V87)I86)L97, 86YD(&9O<G=A<F1S('1H96T =&\ 8F%C:PT*(&5N9"!F

M/FUE<F=E/"]U/BA4+BXN*2A4(#QI/F1A=&$\+VD^*3L-"CPO8FEG/CPO9'0^

M/&)R/CQB<CX-" T*/"]D9#X-"CQD=#X\8FEG/E1;,%T /'4^8G5B8FQE4V]R
M=#PO
M/D)U8F)L92!M=6QT:7-O<G0 9G5N8W1I;VXN("!5<V5F=6P ;VYL>2!B96-A
M=7-E(&ET)W, 96%S>2!T;R!I;7!L96UE;G0-"B!A;F0 =&5S="!O=&AE<B!S
M;W)T:6YG(&9U;F-T:6]N<R!A9V%I;G-T+B` 0V]U;G1S('-W87!S(&EF(&QA

M/ T*/&1T/CQB:6<^5%LP72`\=3YS96QE8W1I;VY3;W)T/"]U/BA4+BXN*2A4
M(#QI
M96-T:6]N('-O<G0N("!5<V5D(&9O<B!S;6%L;"!S=6)A<G)A>7, :6X <7-O
M<G0N(`T*/&)R/CQB<CX-" T*/"]D9#X-"CQD=#X\8FEG/E1;,%T /'4^<W1A
M8FQE4V5L96-T:6]N4V]R=#PO
M+V)I9SX\+V1T/ T*/&1D/E-T86)L92!S96QE8W1I;VX <V]R="X (%5S960 
M9F]R('-M86QL('-U8F%R<F%Y<R!I;B!S=&%B;&51<V]R="!A;F0 ;65R9V53
M;W)T+ T*($EF(&QA<W0 87)G=6UE;G0 :7, 82!U;&]N9RHL(&ME97!S('1R
M86-K(&]F(&YU;6)E<B!O9B!S=V%P<R!T:&%T('=O=6QD(&AA=F4 8F5E; T*
M(&YE8V5S<V%R>2!I9B!T:&ES('=E<F4 82!B=6)B;&4 <V]R="X-"CQB<CX\

M871E9"!B>2`\82!H<F5F/2)H='1P.B\O=W=W+F1I9VET86QM87)S+F-O;2]D
M+S(N,"]D9&]C+FAT;6PB/D1D;V,\+V$^+B`\+W-M86QL/ T*"3PO8F]D>3X\

`
end

Jul 06 2008

bearophile <bearophileHUGS mailas.com> writes:

I haven't tried your code (yet), but I suggest you to not use too much long
lines (90-100 chars is probably enough).

Your code contains both the forms:
    foreach(ti, array; data) temp[ti][index] = array[$-1];
    ...
    foreach(i, array; temp) {
        data[i][0..$] = array[0..$];
    }

I suggest you to use the second form, or the following one if you want to save
a line:
    foreach (i, array; temp)
        data[i][0..$] = array[0..$];

I suggest you to avoid writing a single large unittest, but to add one block of
unittests under each function/class/method, so you can isolate them better,
disable them, etc (even better is having a standard way to give them a name, so
the program/compiler that executes the unit tests knows what
function/class/method are broken. D unittest system needs just small
improvements to become good enough for small/medium size programs).

Bye,
bearophile

Jul 06 2008

superdan <super dan.org> writes:

dsimcha Wrote:

 I've been working on implementing some statistics functions in D, and noticed
 that it would be nice if a multisort function were in Phobos.  Such a function
 would take N arrays in and sort them by the first one.  The common way to
 handle something like this seems to be to make a struct with the fields, make
 opCmp point to whatever field you want to sort by, and then use a regular
 sorting algorithm.  This is slow and a pain.  I've implemented a few different
 multisort functions, along with documentation and unit testing, and would like
 to contribute them to Phobos.  I've attached the source file and the Ddoc
 documentation.

yarp i needed this 2. sounds good but it's unnecessary. sort does all that shit
easily.

int[] arr1;
float[] arr2;
string[] arr3;
// sort three arrays as one
void mySwap(int* a, int* b)
{
    auto i = a - arr1.ptr, j = b - arr1.ptr;
    iterSwap(a, b);
    swap(arr2[i], arr2[j]);
    swap(arr3[i], arr3[j]);
}
sort!("a < b", SwapStrategy.unstable, mySwap)(arr1);

what happens is that whenever two doods in arr1 get swapped, the corresponding
doods in arr2 and arr3 get swapped too. i don't know why the docs don't give
such examples. there's just a hint "Possible uses include notifying observers,
counting the number of operations, or manipulating multiple collections in
lockstep." the lockstep thing gave it away.

& of course you deserve shoe heel beating for putting bubblesort in there. no
matter how much you warn against its usage.

Jul 06 2008

D Programming

C/C++ Programming

Other

digitalmars.D - Multisort