* 挿入ソート [#ve190b32]
sub insert_sort {
my @nums = @_;
for (my $x = 1; $x < @nums; $x++) {
for ( my $i = $x ; $i >= 1 && $nums[ $i - 1 ] > $nums[$i] ; $i-- ) {
my $temp = $nums[ $i - 1 ];
$nums[ $i - 1 ] = $nums[$i];
$nums[$i] = $temp;
}
}
return @nums;
}
my @nums = (5,3,6,2,8,4,1,7);
my @nums2 = insert_sort(@nums
ORIG: 5,3,6,2,8,4,1,7 # 配列の最初の状態
1: (5,3,6,2,8,4,1,7) # 添え字1から始める
1: 5,3 (5,3,6,2,8,4,1,7) -> (3,5,6,2,8,4,1,7) # 添え字1の値3を添え字0の値5を比較する。順番じゃないのでひっくり返す。
# 添え字0は対象じゃないのでここで終わり。
=====
2: (3,5,6,2,8,4,1,7) # 添え字2に移る
# 添え字2の値6を添え字1の値5を比較する。このままで良い。
=====
3: (3,5,6,2,8,4,1,7) # 添え字3に移る
3: 6,2 (3,5,6,2,8,4,1,7) -> (3,5,2,6,8,4,1,7) # 添え字3の値2を添え字2の値6と比較する。順番じゃないのでひっくり返す。
2: 5,2 (3,5,2,6,8,4,1,7) -> (3,2,5,6,8,4,1,7) # 添え字2に移る。添え字2の値2と添え字1の値5を比較する。順番じゃないのでひっくり返す。
1: 3,2 (3,2,5,6,8,4,1,7) -> (2,3,5,6,8,4,1,7) # 添え字1に移る。添え字1の値2と添え字0の値3を比較する。順番じゃないのでひっくり返す。
=====
4: (2,3,5,6,8,4,1,7) # 以下同様。
=====
5: (2,3,5,6,8,4,1,7)
5: 8,4 (2,3,5,6,8,4,1,7) -> (2,3,5,6,4,8,1,7)
4: 6,4 (2,3,5,6,4,8,1,7) -> (2,3,5,4,6,8,1,7)
3: 5,4 (2,3,5,4,6,8,1,7) -> (2,3,4,5,6,8,1,7)
=====
6: (2,3,4,5,6,8,1,7)
6: 8,1 (2,3,4,5,6,8,1,7) -> (2,3,4,5,6,1,8,7)
5: 6,1 (2,3,4,5,6,1,8,7) -> (2,3,4,5,1,6,8,7)
4: 5,1 (2,3,4,5,1,6,8,7) -> (2,3,4,1,5,6,8,7)
3: 4,1 (2,3,4,1,5,6,8,7) -> (2,3,1,4,5,6,8,7)
2: 3,1 (2,3,1,4,5,6,8,7) -> (2,1,3,4,5,6,8,7)
1: 2,1 (2,1,3,4,5,6,8,7) -> (1,2,3,4,5,6,8,7)
=====
7: (1,2,3,4,5,6,8,7)
7: 8,7 (1,2,3,4,5,6,8,7) -> (1,2,3,4,5,6,7,8)
=====
RESULT: 1,2,3,4,5,6,7,8 # ソートされた結果
** 参考 [#je8d60aa]
http://www.geocities.jp/ky_webid/algorithm/004.html