アルゴリズムイントロダクション第１巻 挿入ソート

買ってきたけど早くも挫折しそう。 ひとつひとつ書いてくことにする。

http://stackoverflow.com/questions/6788987/cant-get-insertion-sort-from-introduction-to-algorithms-3rd-ed-right-where-is
ソースコードはここから拝借。

//挿入ソート
INSERTION-SORT(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
    
    while (i > 0 and A[i] > key)
        A[i + 1] = A[i]
        i = i - 1
    A[i + 1] = key


//A = {5, 2, 4, 6, 1, 3}とする。


////////////////////////////////////////////////////////////////////////////


INSERTION-SORT(A)
    for j = 2 to A.length
    // j = 2
        key = 2 //key = A[j]
        i = 1   //i = j - 1
    
    while (i = 1, A[1] = 5 > key よりtrue) //(i > 0 and A[i] > key : true)
        A[2] = A[1] = 5 //A[i + 1] = A[i]
        // A = {5, 5, 4, 6, 1, 3}となった。
        i = 0       //i = i - 1
        //i < 0よりwhile抜ける

    A[1] = 2 //A[i + 1] = key

    // A = {2, 5, 4, 6, 1, 3}となった。




INSERTION-SORT(A)
    for j = 2 to A.length
    // j = 3
        key = 4 //key = A[j]
        i = 2   //i = j - 1

    while (i = 2, A[2] = 5 > key よりtrue) //(i > 0 and A[i] > key : true)
        A[3] = A[2] = 5 //A[i + 1] = A[i]
        // A = {2, 5, 5, 6, 1, 3}となった。
        i = 1       //i = i - 1
        //A[1] = 2よりwhile抜ける

    A[2] = 4 //A[i + 1] = key

    // A = {2, 4, 5, 6, 1, 3}となった。



INSERTION-SORT(A)
    for j = 2 to A.length
    // j = 4
        key = 6 //key = A[j]
        i = 3   //i = j - 1

    while (i = 3, A[3] = 5 < key よりfalse) //(i > 0 and A[i] > key : true)

    A[4] = 6 //A[i + 1] = key

    // A = {2, 4, 5, 6, 1, 3}となった(変化なし)


INSERTION-SORT(A)
    for j = 2 to A.length
    // j = 5
        key = 1 //key = A[j]
        i = 4   //i = j - 1

    while (i = 4, A[4] = 6 > key = 1 よりtrue) //(i > 0 and A[i] > key : true)
        A[5] = A[4] = 6 //A[i + 1] = A[i]
        // A = {2, 4, 5, 6, 6, 3}となった
        i = 3       //i = i - 1

    while (i = 3, A[3] = 5 > key = 1 よりtrue) //(i > 0 and A[i] > key : true)
        A[4] = A[3] = 5 //A[i + 1] = A[i]
        // A = {2, 4, 5, 5, 6, 3}となった
        i = 2       //i = i - 1

    while (i = 2, A[2] = 4 > key = 1 よりtrue) //(i > 0 and A[i] > key : true)
        A[3] = A[2] = 4 //A[i + 1] = A[i]
        // A = {2, 4, 4, 5, 6, 3}となった
        i = 1       //i = i - 1

    while (i = 1, A[1] = 2 > key = 1 よりtrue) //(i > 0 and A[i] > key : true)
        A[2] = A[1] = 2 //A[i + 1] = A[i]
        // A = {2, 2, 4, 5, 6, 3}となった
        i = 0       //i = i - 1
        //while(false)になった

    A[1] = key = 1 //A[i + 1] = key

    // A = {1, 2, 4, 5, 6, 3}となった


INSERTION-SORT(A)
    for j = 2 to A.length
    // j = 6
        key = 3 //key = A[j]
        i = 5   //i = j - 1

    while (i = 5, A[5] = 6 > key = 3 よりtrue) //(i > 0 and A[i] > key : true)
        A[6] = A[5] = 6 //A[i + 1] = A[i]
        // A = {1, 2, 4, 5, 6, 6}となった
        i = 4       //i = i - 1

    while (i = 4, A[4] = 5 > key = 3 よりtrue) //(i > 0 and A[i] > key : true)
        A[5] = A[4] = 5 //A[i + 1] = A[i]
        // A = {1, 2, 4, 5, 5, 6}となった
        i = 2       //i = i - 1

    while (i = 3, A[3] = 4 > key = 3 よりtrue) //(i > 0 and A[i] > key : true)
        A[4] = A[3] = 4 //A[i + 1] = A[i]
        // A = {1, 2, 4, 4, 5, 6}となった
        i = 2       //i = i - 1

    while (i = 2, A[2] = 2 < key = 3 よりfalse) //(i > 0 and A[i] > key : true)


    A[3] = key = 3 //A[i + 1] = key

    // A = {1, 2, 3, 4, 5, 6}となった

j = 5, 6のときが動きが分かりやすかった。
ある点(A[j])をkeyとして保存しておいて、その左の点(A[j-1])の値をコピーする。
そうやって、ある値を右にコピーするってのを繰り返していく。

んで、ある値がkeyより小さくなったらそこにkeyを入れる。

A = {1, 2, 4, 5, 6, 3}
key = 3とする。

A = {1, 2, 4, 5, 6, 6}
左の点の値をコピー

A = {1, 2, 4, 5, 5, 6}
左の点の値をコピー

A = {1, 2, 4, 4, 5, 6}
左の点の値をコピー

A = {1, 2, 3, 4, 5, 6}
2 は keyより小さいので、ここにkeyを入れる。

ここまで書いてみて気づいたんだけど、これらを簡潔にまとめたのがテキストp.15の図2.2なんだなぁ。(「挿入ソート」でイメ検すると出てくる図ね)

挿入ソート - Google 検索

図見てもまるで理解できずここまで一つ一つ追っていかないと分からないの恥ずかしい極みだけど、まぁいいか
それより今年の４月に社会人になってプログラマとしてお金をいただいてきたのに、今までアルゴリズムをまったく勉強しなかったことのほうが色々とアレ。 来年新入社員が入ってくるまでに多少は成長しておかんと。