挿入ソート

 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