ソートアルゴリズム：挿入ソート - 講義で与えられた擬似コードが正しくないようです。

Question

私はアルゴリズムと呼ばれる基本クラスに参加しています。ソートアルゴリズムを研究しています。挿入ソートアルゴリズムの例として以下の擬似コードが与えられました。しかし、私はそれが間違っていると思います。 - 最初のカードは「すでに注文」されているので、それはそれ以来、2から始まり

私は最初の行を理解する：あなたはまた、このスクリーンショットでは、講義ノートにここでそれを見ることができます

For i in {2,..,n}: 
    For j in {i,..,2}: 
     If a(j)<a(j-1), swap a(j) and a(j-1) 
     Else, Break 

これまでのところ唯一のカードです。

2行目は間違いですか？どのように私は私が2からjを使用することができますか？もちろん、これは将来的に成り立つことはありません。また、ブレークインが少なくインデントされるべきではありませんか？だから2つのタブの代わりに1つのタブだけ？ここで

編集

は、アルゴリズムの "主な考え方" です。あなたが見ているように、インデックスjの範囲はここから間違っているようです。

EDIT2 だからここに私はこの擬似コードを読んで、私の心の中で何が起こるかを記述してみてください： 私はリスト(5,3,8,7,2,4,1,6)があるとします。私は|と書いて "手"をデッキから分離し、また、私がどの要素を見ているのかを強調するために5_と書きます。だからここに私達は行く：

i = 1, (5|3,8,7,2,4,1,6) 
i = 2, (5,3|8,7,2,4,1,6), now j in {2}, so we only have j = 2, a(j=2)=3 < a(j=1)=5, hence swap 3 with 5 
i = 3, (3,5,8|7,2,4,1,6), j in {2,3}, so j=2 gives a(j=2)=5 !< a(j=1)=3 SO WE BREAK! 
i = 4, (3,5,8,7|2,4,1,6), j in {2,3,4}, so j = 2 gives a(j=2)=5 !< a(j=1)=3, SO WE BREAK 

、あなたは我々が2から開始するので、我々はそれを破るため、これは常に今から起こるのだろう見るように！私達はちょうどあなたが以下の仮定を行う場合は、コードが有効である条件

Answer 1

に違反するので、そうでもjの増加のための整数の集合かかわらず、我々は、さらに2を行くことができない。

• の配列を長さNはインデックスを持ちます。1..N
• forループは、方向に関係なく指定された範囲をカバーします。したがって、for x in {a,...,b}はa, a+1, a+2, ..., b-1, b if a <= bになりますが、a, a-1, a-2, ..., b+1 b if a >= bになります。

Answer 2

2番目の行は、i番目の要素（外側ループで実行中）を取り込み、その前のパーティションに挿入しようとしているので間違いではありません。この要素をソートする前に、この要素をパーティションと比較する必要があります。

このSOポストが良い可視化を持っています Insertion Sort vs. Selection Sort