2007-01-29

クイックソート

ソート

Javaで紹介されていたソースをなぞる形でパールで書いてみた。まったく同じものを作るのもつまらないので、複数列のデータを、特定の列の値でソートすることとした。

また、double型データでの版も作ってみた(あくまでもオリジナルのサイトが本物で、それのint->doubleの変化だけの代物。とはいえ、コピーペーストしたい向きには、オリジナルサイトの著者に敬意を払っていただければと思います)。

特定列は有理数とし、その値に基づく、整数順序列をクイックソートで発生させ、その順序列を使って、他の列をソートする。

こちらの紹介記事をなぞったが、上記仕様を実装するため、また、perlでの値の受け渡しがへたなために、何度も値のdeep copyを行うソースとなっている。その結果、せっかく速いはずのクイックソートの本領を発揮できていないかもしれないけれど・・・



#! /usr/bin/perl -w


use File::Basename;


&main(@ARGV);

exit;


sub main(@){

  

  my @tmpdata=(1,3,6,2,4,5,1);
  my @sorted = sortD(@tmpdata);

  for(my $i=0;$i<@sorted;$i++){

   print $tmpdata[$sorted[$i]];

  }

}


sub pivotD{

 my ($data,$order,$i,$j)=@_;

 my $k=$i+1;

 while($k<=$j && @$data[@$order[$i]]==@$data[@$order[$k]]){

  $k++;

 }

 if($k>$j){

  my $ret=-1;

  return $ret;

 }

 if(@$data[@$order[$i]]>=@$data[@$order[$k]]){

  return $i;

 }

 return $k;

}

sub partitionD{

 my ($data,$order,$i,$j,$x)=@_;

 my @Order;

 for(my $y=0;$y<@$order;$y++){

  $Order[$y]=@$order[$y];

 }

 my $l=$i;

 my $r=$j;

 while($l<=$r){

  while($l<=$j && @$data[$Order[$l]]<$x){

   $l++;

  }

  while($r>=$i && @$data[$Order[$r]]>=$x){

   $r--;

  }
  if($l>$r){

   last;

  }

  my $t=$Order[$l];

  $Order[$l]=$Order[$r];

  $Order[$r]=$t;

  $l++;$r--;

 }

 my $OrderRet = \@Order;

 return ($l,$OrderRet);
}

sub quickSortD{

 my ($data,$order,$i,$j)=@_;

 my @Order;

  my @Order2;

  my @Order3;

  my @Order4;

  my $Order2Ref;

  my $Order3Ref;

  my $Order4Ref;

 for(my $x=0;$x<@$order;$x++){

  $Order[$x]=@$order[$x];

  $Order4[$x]=@$order[$x];

 }

 if($i==$j){
  return $order;

 }

 my $OrderRef=\@Order;

 my $p = pivotD($data,$OrderRef,$i,$j);

 if($p!=-1){

  my ($k,$Order2Ret)=partitionD($data,$OrderRef,$i,$j,@$data[$Order[$p]]);

  for(my $y=0;$y<@Order;$y++){

   $Order2[$y]=@$Order2Ret[$y];

  }

  my $OrderRef2=\@Order2;

  $Order3Ref=quickSortD($data,$OrderRef2,$i,$k-1);

  for(my $y=0;$y<@Order;$y++){

   $Order3[$y]=@$Order3Ref[$y];

  }

  my $OrderRef3=\@Order3;

  $Order4Ref=quickSortD($data,$OrderRef3,$k,$j);

  for(my $y=0;$y<@Order;$y++){

   $Order4[$y]=@$Order4Ref[$y];

  }
 }

 my $returnRef = \@Order4;

 return $returnRef;

}

sub sortD{

 my $data=\@_;

 my @order;
 for(my $i=0;$i<@$data;$i++){
  $order[$i]=$i;

 }

 my $orderRef=\@order;

 my $num = @order;

 my $retRef =quickSortD($data,$orderRef,0,$num-1);

 my @ret;

 for(my $i=0;$i<@order;$i++){

  $ret[$i]=@$retRef[$i];

 }

 return @ret;

}


	  

	  /*

		 * quicksortDouble

		 */

		 /*

		   * 軸要素の選択

		   * 順に見て、最初に見つかった異なる2つの要素のうち、

		   * 大きいほうの番号を返します。

		   * 全部同じ要素の場合は -1 を返します。

		   */

		  public static int pivotDouble(double[] a,int i,int j){

		    int k=i+1;

		    while(k<=j && a[i]==a[k]){

		      k++;

		      //if(notifier!=null) notifier.notifyCompare(k,-1);

		    }

		    if(k>j) return -1;

		    if(a[i]>=a[k]) return i;

		    return k;

		  }
		  /*

		   * パーティション分割

		   * a[i]〜a[j]の間で、x を軸として分割します。

		   * x より小さい要素は前に、大きい要素はうしろに来て、

		   * 大きい要素の開始番号を返します。

		   */

		  public static int partitionDouble(double[] a,int i,int j,double x){

		    int l=i,r=j;

		    while(l<=r){

		      while(l<=j && a[l]<x){

			l++;

			//if(notifier!=null) notifier.notifyCompare(l,j);

		      }

		      while(r>=i && a[r]>=x){

			r--;

			//if(notifier!=null) notifier.notifyCompare(r,i);

		      }

		      if(l>r) break;

		      //int t=a[l];

		      double t=a[l];

		      a[l]=a[r];

		      a[r]=t;

		      //if(notifier!=null) notifier.notifyExchange(l,r);

		      l++; r--;

		    }

		    return l;

		  }
		  /*

		   * クイックソート（再帰用）

		   * 配列aの、a[i]からa[j]を並べ替えます。

		   */

		  public static void quickSortDouble(double[] a,int i,int j){

		    if(i==j) return;

		    int p=pivotDouble(a,i,j);

		    if(p!=-1){

		      int k=partitionDouble(a,i,j,a[p]);

		      quickSortDouble(a,i,k-1);

		      quickSortDouble(a,k,j);

		    }

		  }
		  /*

		   * ソート

		   */

		  public static void sortDouble(int[] a){

		    quickSort(a,0,a.length-1);

		  }