非再帰版クイックソート for Java

ちょっと必要になったので。

import java.lang.*;

public class XXXXX{
   static final int ARRAYSIZE = 20;
   
   public static void main(String args[]){
      int array[] = new int[ARRAYSIZE];
      for(int i=0; i<ARRAYSIZE; i++){
         array[i] = (int)(Math.random()*ARRAYSIZE);
      }
      for(int i=0; i<ARRAYSIZE; i++){
         System.out.println(array[i]);
      }
      System.out.println("----------");
      QuickSort qs = new QuickSort(array);
      qs.sort();
      qs.print();
   }
}

abstract class Sort{
   protected int a[];

   Sort(int array[]){
      a = new int[array.length];
      for(int i=0; i<array.length; i++){
         a[i] = array[i];
      }
   }
   public abstract void sort();
   protected void swap(int a[], int i, int j){
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
   }
   protected void print(){
      for(int i=0; i<a.length; i++){
         System.out.println(a[i]);
      }
   }
}

class BubbleSort extends Sort{
   BubbleSort(int array[]){super(array);}
   public void sort(){
      final int N = a.length - 1;
      for(int i=0; i<N; i++){
         for(int j=0; j<N-i; j++){
            if(a[j] > a[j+1]){
               swap(a, j, j+1);
            }
         }
      }
   }
}

class QuickSort extends Sort{
   static final int STACKSIZE = 32;
   QuickSort(int array[]){super(array);}
   public void sort(){ // non-recursive
      int lstack[] = new int[STACKSIZE];
      int rstack[] = new int[STACKSIZE];
      int sp = 1, l, r, pivot;
      lstack[0] = 0;
      rstack[0] = a.length-1;
      while(sp > 0){
         sp--;
         l = lstack[sp];
         r = rstack[sp];
         if(l < r){
            pivot = partition(a, l, r, (l + r)/2);
            lstack[sp] = l;
            rstack[sp] = pivot-1;
            lstack[sp+1] = pivot+1;
            rstack[sp+1] = r;
            sp+=2;
         }
      }
   }
   private int partition(int a[], int left, int right, int pivot){
      int l=left+1, r=right, x=a[pivot];
      swap(a, left, pivot); // set pivot as the first element of partition
      while(true){
         while(l < right && a[l] <= x) l++;
         while(r > left  && a[r] >  x) r--;
         if(l >= r) break;
         swap(a, l, r);
      }
      swap(a, left, r); // swap pivot for the last element of low-partition
      return r;
   }
}

クイックソート、アルゴリズムは超簡単のくせに実装するとなると細かいところがめんどくせー。トリッキーな実装はやめて、できるだけ素直に書いたので後で読んで分かりやすい・・・と思う。それにしても、ついでに書いたバブルソートが簡単すぎて笑えてくる。

余談ですが

「クイックソート 非再帰」でぐぐると最初に出てくるこちらのサイト。
http://www.drk7.jp/MT/archives/000995.html
なるほど、スタックを自前で実装するのかーと非常に参考になったのですが、実はそのままだとコードにミスがあって期待通りに動きません*1。

use strict;
my @array = qw(10 5 5 5 7 6 5);
qsort_array(\@array, 0, $#array);
print "@array\n";

$ perl sort.pl
10 5 5 5 5 6 7

最初の10が残ってるよ！
なんでこんなことになるかというと理屈は簡単で

while ($array->[$i] < $pivot && $i < $right) { $i++; }
while ($array->[$j] >= $pivot && $left < $j) { $j--; }
if( $i >= $j ){ last; }

このロジックだと、qw(10 5 5 5 7 6 5)を処理したときに$i=$j=0になってしまって、swapせずにループを抜けてしまうから。
無理やり動くようにするには

($array->[$left], $array->[($left+$right)/2]) = ($array->[($left+$right)/2], $array->[$left]);
$i++;
while (1) {
  #ここはオリジナルどおり
}
($i, $j) = ($j, $i);
($array->[$i], $array->[$left]) = ($array->[$left], $array->[$i]);

こんな感じでしょうか？pivotをいったん端っこに退避させて、最後に戻す。$jを新しいpivotとして使いたいので、$iとswapしておくという変な処理を追加してます。条件分岐とかしてもいいけど、これが一番分かりやすいような気がします。

・・・なんでそんなこと言うかというと、俺がはまったから・・・

余談2

Perlの豆知識

$ perl -e '($i, $j)=(1, 2);($i, $j)=($j, $i); print "$i, $j\n"'
2, 1

一時変数なしのswap！無駄に便利！

*1:$iがiになってる・・・とかはおいといて