ソート色々。

Programming Perl

適当に勘で書く。Perlのスライスは便利だなあと思う。

バブルソート。

for($i=$#a;$i>0;--$i){
  for($j=0;$j<$i;++$j){
    @a[$j,$j+1] = @a[$j+1,$j] if($a[$j]>$a[$j+1]);
  }
}

「一番簡単なソート」的なあつかいをされていることがあるけど、そんなにわかりやすくもない気がする。二重のループで範囲を狭めていくあたりが。

比較（セレクション）ソート。

for($i=0;$i<$#a;++$i){
  for($m=$j=$i;$j<@a;++$j){
    $m=$j if($a[$m]>$a[$j]);
  }
  @a[$i,$m]=@a[$m,$i];
}

バブルソートよりか、比較ソートの方が理解がされやすい気がする。こっちだってループが二重になってはいるけれど、内側のループは「一番小さい数を探す」という、副作用の無いループ。ループの中のループで配列の中身をあれこれ入れ替えながら進む、「ふくざつ」なバブルソートよりいーかんじ。

挿入（インサーション）ソート。

for($i=1;$i<@a;++$i){
  $t = $a[$i];
  for($j=$i;$j>0&&$a[$j-1]>$t;--$j){$a[$j]=$a[$j-1]}
  $a[$j]=$t;
}

バブルソート、選択ソート同様の基本的なソート。バブルソート、選択ソートなんかよりかは速い。と聞いたことがある気がする。


なんとなくソート3つ書いたけど、ここまではカンペ無しで適当に書ける。あんまり書いたことの無いソートを書いてみようというつもりで書き始めたので本題はこれから。なのだけれど、眠いから明日以降。続かないかも。

test