Rubyでの挿入ソートを理解する

コードを見てみましょう！

def insertion_sort(array)
    for i in 1...(array.length)  # Step 1
        j = i # Step 2
        while j > 0 # Step 3
            if array[j-1] > array[j] # Step 4
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            else
                break
            end
            j = j - 1 # Step 5
        end
    end
    return array
end

ステップ1：

forから始めます 変数iを設定するループ 1に変更し、iまで増分し続けます 配列の長さに等しい。

ステップ2：

別の変数jを作成します 値1で初期化します（これがiであるため） です。

ステップ3：

次に、ネストされたwhileがあります jまで続くループ ゼロより大きい。 jから始めるので 1に等しい場合、これは少なくとも1回実行されることがわかっています。

ステップ4：

if... else ブロックは最初は恐ろしいように見えますが、心配しないでください。一度説明すると意味があります（そして、いつでもYouTubeのダンスの例に戻ることができます！）。

ifの場合 条件、[j-1]かどうかを確認します array[j]より大きい 。 j以降 現在は1ですが、基本的にarray[0]を比較します。 array[1]を使用 。配列の最初の2つの要素を比較しているので、これは理にかなっています。

最初の要素の場合（array[0] ）は次のものよりも大きい（array[1] ）、もちろん、スワップする必要があります。これは、if内で発生します。 ブロック。ただし、array[0]の値が array[1]の値よりも小さい 、そして素晴らしい！すでに並べ替えられているため、何もする必要はありません。そのため、breakを押すだけです。 elseで ブロック。

ステップ5：

ここから、jをデクリメントします 。これで、forに戻ります。 ループ、およびi 2になります 。 array[1]をどのように比較するか想像できます array[2]を使用 while内の最初の反復 ループしてから、実際にwhileを実行します jなので、もう一度ループします 2から開始 vs. 1 。