===============================================================================

                                                     2002 年 06 月 05 日（水）

            2002 年度「応用数理Ｃ３」「計算数学１」

                                                                    岩瀬順一

===============================================================================

== 020605a.c ==

/* 配列の挿入ソート */
void sort(void) {
    int i, m;

    for (m=1; m<N; m++) {
        for (i=m-1; i>=0; i--) {    /* 以下で a[m] を正しい位置に挿入する */
            if (a[i] > a[i+1]) {
                swap(i, i+1);
                print();            /* swap() を呼ぶごとに印字する */
            } else {
                break;
            }
        }
/*      print();                    /* 挿入が完了するごとに印字する */
    }
}

== 020605b.c ==

/* 配列のシェルソート */
void sort(void) {
    int gap, j, i, m;

    for (gap = 1; gap < N; gap = 3*gap+1) {
        ;
    }

    for (gap /= 3; gap > 0; gap /= 3) {
        for (j = 0; j < gap; j++) {
            for (m = 1; j+m*gap < N; m++) {
                for (i = m-1; i >= 0; i--) {    /* 以下で a[j+m*gap] を挿入 */
                    if (a[j+i*gap] > a[j+(i+1)*gap]) {
                        swap(j+i*gap, j+(i+1)*gap);
                        print();                /* swap() を呼ぶごとに印字 */
                    } else {
                        break;
                    }
                }
            }
        }
    }
}

== 020605c.c ==

/* 配列のシェルソート（その２）*/
    int gap, l, k;

    /* gap の初期設定をする for ループは前と同じ */

    for (gap /= 3; gap > 0; gap /= 3) {
        for (k = gap; k < N; k++) {
            for (l = k-gap; l >= 0; l -= gap) { /* 以下で a[k] を挿入 */
                if (a[l] > a[l+gap]) {
                    swap(l, l+gap);
                    print();                    /* swap() を呼ぶごとに印字 */
                } else {
                    break;
                }
            }
        }
    }
}