挿入ソートのプログラムがわかりません。

Question

1 insertionSort(A, N) // N個の要素を含む0-オリジンの配列A
2 for i が 1 から N-1 まで
3 v = A[i]
4 j = i - 1
5 while j >= 0 かつ A[j] > v
6 A[j+1] = A[j]
7 j--
8 A[j+1] = v

-----以下、自分で考えた部分------------
例えば
[1] [2] [3] [4] [5]
3 6 2 1 4
という数字が入っていて。

プログラムに入れていくと
v = 3
j = 0
while j (= 0) >=0 && A0 >v(=3)

whileの部分でわからなくなりました。

あと、最初のプログラムのfor i がなぜ、N-1になるのでしょうか？

配列が０から始まると、N-1になると思うのですが…。

よくわからないので、教えてください。

Answer 1

質問文のコードを ruby としてエラーが発生しないようにしてみました。
ソート処理が動作するかについては関知はしてません。

def insertionSort(ary, len) # N個の要素を含む0-オリジンの配列A
  (0 .. len - 1).each do |i|
    v = ary[i]
    j = i - 1
    while j >= 0 && ary[j] > v
      ary[j + 1] = ary[j]
      j -= 1
    end
    ary[j + 1] = v
  end
end

a = [1, 3, 5, 2, 4, 6]
insertionSort(a, a.length)
p a

Comments

[退会済みユーザー]

回答ありがとうございます。

katoyさんのプログラムで、少しわかった気がします。

ありがとうございます。

Answer 2

見間違えて間違いを書きました。
また時間のある時に見ます。

Comments

[退会済みユーザー]

ありがとうございます。

お待ちしております。

[Zuishin]

ちゃんと動きました。
配列は 0 から始まりますので、N - 1 は配列の最後の要素を指します。

while の部分は何をしているかと言うと、j 以前のデータは既に整列済みですので、v 未満になる初めての要素を探しています。
そこまでのデータを全部後ろに一つずつずらしていき、v 未満になった要素の次に v を書き込みます。

例えば 2 5 3 4 というデータがあった時、i は 1 ですから、A[i] は 5 になります。これを v に代入します。
次に while ループに入ります。2 は 5 未満なので、2 の次、つまり A[i] に v つまり 5 を代入します。元の位置です。

while ループはこれで終わりました。i を一つ進めて 2 にします。
v = 3, j = 1 となります。
A[j] = 5 で v 以上ですから、3 の位置に 5 を書き、j を一つ減らします。
これで配列は 2 5 5 4 となりました。
j = 0 になったことで、A[j] = 2 で v 未満になりましたので、2 の次の位置に v = 3 を書き込みます。これで 2 3 5 4 となりました。
これで whihle を抜けます。

次は i = 3 です。これは N - 1 になります。A[i] = v = 4 です。
j = 2 で、A[j] = 5 で v 以上ですから、A[j + 1] に 5 を書き込み、j を減らします。
これで 2 3 5 5 になりました。
A[j] = 3 になり、v 未満ですから、A[j + 1] に v =4 を書きます。
これで 2 3 4 5 になりました。
while ループを抜けて i を一つ増やすと、N - 1 より大きくなりますから、これで終了です。

[Zuishin]

こうして言葉で書かれたものを読んでも、ものすごくわかりにくいと思います。
どなたかがトランプを使えとおっしゃっていましたが、それこそ頭の中だけで考えず、手を動かしてください。

紙に変数を書いて、トランプを並べて、処理を追ってみてください。
私の経験では「わからない」という人は大抵手を抜いています。
手を抜いて楽になると思っていますが、実際にはそれは逆で、かえって大変にしています。
丁寧に楽に学びましょう。

[退会済みユーザー]

ありがとうございます。

トランプが良いのですね。Wordを開いて、書きながら、処理を追ってみたのですが、よくわからなくなりました。

ありがとうございました。