Piano Improvisation

2011/04/03

MELにクイックソートを行うqsortはありますが、応用目的で利用するためにクイックソートをMELで作りました。再帰を使うバージョンと使わないバージョンの2つです。

こちらは再帰を使ったクイックソートのMELスクリプトです。


global proc QuickSort(float $ary[],int $left,int $right)
{
  if($left>=$right){ return; }

  int $center, $itr_L, $itr_R;
  float $medianVal = $ary[$left];
  $itr_L = $left;
  $itr_R = $right;
  while($itr_L < $itr_R){
    while($itr_L<$itr_R && $medianVal<$ary[$itr_R]){
      $itr_R--;
    }
    if($itr_L<$itr_R){
      $ary[$itr_L] = $ary[$itr_R];
      $itr_L++;
    }
    while($itr_L<$itr_R && $ary[$itr_L]<$medianVal){
      $itr_L++;
    }
    if($itr_L<$itr_R){
      $ary[$itr_R] = $ary[$itr_L];
      $itr_R--;
    }
  }
  $center = $itr_L;
  $ary[$center] = $medianVal;

  QuickSort($ary, $left, $center-1);
  QuickSort($ary, $center+1, $right);
}


Example

float $ary[]={3,35,2,11,44,1,2,32,35};
QuickSort($ary, 0, size($ary)-1);
print($ary);
//0 1 2 2 3 11 32 35 35 44


こちらは配列をスタック代わりに用いて再帰を使わずに作ったものです。

global proc QuickSort(float $ary[])
{
  int $i, $itr_L, $itr_R, $center;
  int $left_stack[], $right_stack[];
  float $medianVal;
  $left_stack[0] = 0;
  $right_stack[0] = size($ary);
  $i = 0;
  while($i>=0){
    $itr_L = $left_stack[$i];
    $itr_R = $right_stack[$i];
    if($itr_L>=$itr_R){
      $i--;
      continue;
    }
    $medianVal=$ary[$itr_L];
    while($itr_L < $itr_R){
      while(($medianVal <= $ary[$itr_R])
          && ($itr_L < $itr_R))
      { $itr_R--; }
      if($itr_L < $itr_R){
        $ary[$itr_L] = $ary[$itr_R];
        $itr_L++;
      }
      while(($ary[$itr_L] <= $medianVal)
          && ($itr_L < $itr_R))
      { $itr_L++; }
      if($itr_L < $itr_R){
        $ary[$itr_R] = $ary[$itr_L];
        $itr_R--;
      }
    }
    $center = $itr_L;
    $ary[$center] = $medianVal; 

    $left_stack[$i+1] = $center + 1;
    $right_stack[$i+1] = $right_stack[$i];
    $right_stack[$i] = $center - 1;
    $i++;
  }
}



Example

float $ary[]={3,35,2,11,44,1,2,32,35};
QuickSort($ary);
print($ary);
//0 1 2 2 3 11 32 35 35 44

  このエントリーをはてなブックマークに追加    

<<「制作記録」の記事一覧に戻る

関連記事