From: soda@sran230.sra.CO.JP (Noriyuki Soda)
Subject: Re: Quick sort and Heap sort.
	<WD.92Aug18174843@hakobe.kurims.kyoto-u.ac.jp>
	<SODA.92Aug18202947@sran230.sra.CO.JP>
Organization: Software Research Associates, Inc., Japan
Date: Tue, 18 Aug 1992 13:30:44 GMT
Distribution: fj

$BO@;]$H$O4X(B$B78$"$j$^$;$s$,!"0lE@13$r=q$$$F$7$^$$$^$7$?!#D{@5$7$^$9!#(B

In article <SODA.92Aug18202947@sran230.sra.CO.JP> soda@sran230.sra.CO.JP (Noriyuki Soda) writes:

 |	  $B!&F1$8CM$@$1$G9=@.$5$l$?G[Ns(B
 |		  $B!J(BSun $B$N(B qsort(3) $B$,:G0-$K$J$C$?$N$O$3$NNc$G$9$h$M!K(B

$B5$$K$J$C$F!";n$7$F$_$?$N$G$9$,!"$3$l$O4V0c$$$G$7$?!#(B
Sun $B$N(B qsort $B$O!"F1$8CM$@$1$G9=@.$5$l$?G[Ns$KBP$7$F$O:G0-$K$J$i$J$$$h(B
$B$&$G$9!#$5$9$,$K(B Sun $B$N(B qsort() $B$N%=!<%9$J$I<j85$K$"$k$O$:$,$J$$$N$G$9(B
$B$,!";n$7$K(B 4.3BSD-tahoe $B$N(B free $B$J(B qsort() $B$G;n$7$F$_$k$H(B Sun $B$N(B 
qsort() $B$HF1MM$J>I>u$r<($7$?$N$G!"$=$l$K$D$$$F=q$-$^$9!#(B

$B!t(B tahoe $B$,<j85$K$J$$>l9g$O!"(Bemacs/etc/qsort.c $B$,(B tahoe $B$N(B qsort() $B$H(B
$B!t(B $B;z2<$20J30KX$s$IF1$8$b$N$N$h$&$G$9$+$i!"$3$l$G$bF1MM$G$9!#(B
$B!t(B $BA0$N(B$B5-;v$G=q$$$?(B GNU libc-1.01 $B$N(B qsort() $B$OF1$8(B quick sort $B$H8@$C(B
$B!t(B $B$F$b(B tahoe/emasc $B$H$OA4A3JL$N%"%k%4(B$B%j%:%`$r;H$C$F$$$^$9!#(B

tahoe $B$N(B qsort $B$G$O(B

		while (i < mid && qcmp(i, mid) <= 0)
			i $B$r1&$K?J$a$k(B;
		while (j > mid && qcmp(mid, j) <= 0)
			j $B$r:8$K?J$a$k(B;

$B$H$$$C$?%k!<%W$GG[Ns$rJ,3d$7$F$$$^$9!#:G(B$B=i$NB<>e$5$s$N5-;v$K$"$C$?Nc$N(B
$B$h$&$K!"G[NsMWAG$NCM$N<oN`$,>/$J$$>l9g$K$O!"(Bwhile $B$NDd;_>r7o$N$I$A$i$+(B
$B$,$9$0$K@.$jN)$C$F$7$^$$G[Ns$NJ,3d$,C<$NJ}$G5/$-$F!":G0-$NNc$H$J$C$?$h(B
$B$&$G$9!#$3$l$HF17OE}$N(B quick sort $B$r;H$C$F$$$k>l9g$K$O!"(B

	$BG[Ns$r9=@.$9$kMWAG$N<oN`$,G[Ns$NBg$-$5$KHf$Y$F>/$J$$$H!"(B
	$BIQHK$K:G0-%1!<(B$B%9$,5/$-$k(B

$B$H8@$($=$&$G$9!#$?$@$7!"G[NsMWAG$,$9$Y$FF1$8CM$N>l9g$K$O(B tahoe $B$N%"%k(B
$B%4%j%:%`$OJ,3d$,$A$g(B$B$&$I??Cf$G5/$-$F!":GA1$N%1!<%9$H$J$j$^$9!#(B

$B$3$l$KBP$7!"(BGNU libc $B$N%"%k%4%j%:%`$G$O!"(B

		while (qcmp(i, mid) < 0)
			i $B$r1&$K?J$a$k(B;
		while (qcmp(mid, j) < 0)
			j $B$r:8$K?J$a$k(B;

$B$GJ,3d$7$F$$$^$9!#$3$N(B$B>l9g$b(B while $B$NDd;_>r7o$,$9$0$K@.$jN)$C$F$7$^$&(B
$B$N$G$9$,!"$3$N(B while $B%k!<%W$,Dd;_$7$F$b(B $B$9$0$K$=$3$rJ,(B$B3dE@$K7h$a$k$N$G(B
$B$O$J$/!"(Bi $B$H(B j $B$,$V$D$+$k$^$G$5$i$K>e5-$r7+$jJV$7(B i >= j $B$H$J$C$?;~E@(B
$B$G$=$3$rJ,3dE@(B$B$K$7$F$$$^$9!#=>$C$FG[Ns$r9=@.$9$kMWAG$N<oN`$,G[Ns$NBg$-(B
$B$5$KHf$Y$F>/$J$/$F$b!"J,3d$K;H$&(B mid $B$NCM$,NI(B$B$$$b$N$G$"$j$5$($9$l$PNI(B
$B$$J,3d$,5/$3$j$^$9!#$=$7$F(B mid $B$O%=!<%H$9$kNN0h$N1&C<!":8C<!"Cf1{$N%a(B
$B%G%#%"(B$B%s$r5a$a$F$=$l$K$7$F$$$k$N$G!":G0-%1!<%9$O5)$K$7$+5/$-$^$;$s!#(B

$B0J>e!"<XB-$G$7$?!#(B

$B!t(B $B!&F1$8CM$@$1$G(B$B9=@.$5$l$?G[Ns$KBP$7$F!":G0-$K$J$k(B quick sort $B$N(B 
$B!t(B   variant $B$,$"$k!#(B
$B!t(B $B!&:G0-$K$J$i$J$$(B variant $B$b(B$B$"$k!#(B
$B!t(B $B$H$$$&$3$H$KJQ$o$j$O$"$j$^$;$s!#(B
$B!t(B $B!&G[Ns$r9=@.$9$kMWAG$N<oN`$,G[Ns$NBg$-$5$KHf$Y$F>/$J$$$H(B$B!"IQHK(B
$B!t(B   $B$K:G0-%1!<%9$,5/$-$k(B quick sort $B$N(B variant $B$,$"$k!#(B
$B!t(B $B!&:G0-$K$J$i$J$$(B variant $B$b$"$k(B
$B!t(B $B$H$$$&Nc$,A}$($?$@$1$G$9!#(B
--
soda@sra.co.jp		SRA $B@hC<5;=Q3+H/It(B	$BA>EDE/G7(B (Soda Noriyuki)
--
soda@sra.co.jp		$BA>ED(B $BE/G7(B
Newsgroups: fj.comp.misc