MELにクイックソートを行うqsortはありますが、応用目的で利用するためにクイックソートをMELで作りました。再帰を使うバージョンと使わないバージョンの２つで す。
こちらは再帰を使ったクイックソートの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
