挿入ソート

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                       # ソートされた結果

参考

http://www.geocities.jp/ky_webid/algorithm/004.html


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS

Last-modified: 2012-01-13 (金) 19:09:51 (2801d)