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

                                                     2002 年 06 月 12 日（水）

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

                                                                    岩瀬順一

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

== 020605a2.c ==

/* 配列の挿入ソート（前回の訂正版） */
void sort(void) {
    int i, m, tmp;

    for (m=1; m<N; m++) {
        tmp = a[m];                 /* 以下で a[m] を正しい位置に挿入する */
        for (i=m-1; i>=0; i--) {
            if (a[i] > tmp) {
                a[i+1] = a[i];          /* ずらすだけ、a[m] はまだ代入しない */
            } else {
                a[i+1] = tmp; break;    /* ここで代入 */
            }
        }
        if (i == -1) {
            a[0] = tmp;                 /* あるいはここで代入 */
        }
        print();                        /* 挿入が完了するごとに印字する */
    }
}

== 020605a3.c ==

/* 配列の挿入ソート（前回の訂正版） */
void sort(void) {
    int i, m, tmp;

    for (m=1; m<N; m++) {
        tmp = a[m];                 /* 以下で a[m] を正しい位置に挿入する */
        for (i=m; i>=0; i--) {
            if (i > 0 && a[i-1] > tmp ) {
                a[i] = a[i-1];          /* ずらすだけ、a[m] はまだ代入しない */
            } else {
                a[i] = tmp; break;      /* ここで代入 */
            }
        }
        print();                        /* 挿入が完了するごとに印字する */
    }
}

== 020612a.c ==

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define N 26        /* ソートするものの個数 */
#define MAX 99      /* 数値データは 0 ... MAX */

#define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; }

int myrand(int max);
void print(int lo, int p, int hi);
void sort(int lo, int hi);

int a[N];

main() {
    int i;

    srand((unsigned)time(NULL));        /* 現在時刻で乱数の種を初期化 */

    for (i=0; i<N; i++) {
        a[i] = myrand(MAX);
    }
    print(-1, -1, -1);
    sort(0, N-1);
    print(-1, -1, -1);
    return;
}


/* 0 ... max の範囲の乱数を返す。max <= RAND_MAX でなければならない */
int myrand(int max) {
    int r;

    if (max == INT_MAX) {
        return rand();
    }

    while (1) {
        r = rand();
        if (RAND_MAX % (max+1) != max && r/(max+1) == RAND_MAX/(max+1)) {
            continue;
        } else {
            return r % (max+1);
        }
    }
}


/* 配列を印字。a[lo] から a[hi] までと a[p] には色がつく */
void print(int lo, int p, int hi) {
    int i;

    for (i=0; i<N; i++) {
        if (i == lo) {
            printf("\033[96m");         /* ここからは水色 */
        }
        if (i == p) {
            printf(" \033[93m%2d\033[96m", a[i]);   /* これだけは黄 */
        } else {
            printf(" %2d", a[i]);
        }
        if (i == hi) {
            printf("\033[m");           /* 普通の色に戻す */
        }
    }
    putchar('\n');
}


/* 配列のクイックソート（石畑清「アルゴリズムとデータ構造」p.165） */
void sort(int lo, int hi) {
    int i, p, mi, pivot;

    if (lo >= hi) {     /* lo >= hi のときは何もしなくてよい */
        return;
    }

    mi = (lo + hi) / 2;
    pivot = a[mi];      /* これを pivot に選ぶ理由は特にない */
    a[mi] = a[lo];      /* a[lo] は空いたと思おう */
    p = lo;
    i = lo + 1;

    /* 下の while の各くりかえしの最初と最後では「lo < j <= p ならば */
    /* a[j] < pivot」「p < j < i ならば a[j] >= pivot」が成り立つことに注意 */

    while (i <= hi) {
        if (a[i] < pivot) {
            p++;            /* swap(++p, i) は不可（マクロなので） */
            swap(p, i);     /* p == i なら何もしないに等しい */
        }
        i++;
    }

    a[lo] = a[p];
    a[p] = pivot;
    print(lo, p, hi);               /* 確認のため印字 */
    sort(lo, p-1), sort(p+1, hi);
}

== 020612b.c ==

/* 配列のクイックソート（これは自分で書いてみたつもり） */
void sort(int lo, int hi) {
    int i, j, mi, pivot;

    if (lo >= hi) {     /* lo >= hi のときは何もしなくてよい */
        return;
    }

    mi = (lo + hi) / 2;
    pivot = a[mi];      /* これを pivot に選ぶ理由は特にない */

    swap(mi, hi);       /* pivot は a[hi] によけておく */
    i = lo; j = hi-1;

    /* 下の while の各くりかえしの最初と最後では「k < i => a[k] < pivot, */
    /* j < k < hi => a[k] >= pivot」が成り立つことに注意 */

    while (i <= j) {
        if (a[i] < pivot) {
            i++;
        } else {
            swap(i, j); j--;
        }
    }
    /* ここへきたときは i = j+1 */
    a[hi] = a[i]; a[i] = pivot;   /* よけておいた pivot と交換 */
    print(lo, i, hi);             /* 確認のため印字 */
    sort(lo, i-1), sort(i+1, hi);
}

== 020612c.c ==

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>

#define N 26        /* ソートするものの個数 */
#define MAX 99      /* 数値データは 0 ... MAX */

#define swap(I,J) { int tmp = a[(I)]; a[(I)] = a[(J)]; a[(J)] = tmp; }

int myrand(int max);
void print(int lo, int pivot, int hi);
void sort(int lo, int hi);

int a[N];

main() {
    /* 前と同じにつき省略 */
}


/* 0 ... max の範囲の乱数を返す。max <= RAND_MAX でなければならない */
int myrand(int max) {
    /* 前と同じにつき省略 */
}


/* 配列を印字。a[lo] から a[hi] までは色つき、a[i] == pivot のときは [ つき */
void print(int lo, int pivot, int hi) {
    int i;

    for (i=0; i<N; i++) {
        if (i == lo) {
            printf("\033[96m");         /* ここからは水色 */
        }
        if (a[i] == pivot) {
            printf("[%2d", a[i]);
        } else {
            printf(" %2d", a[i]);
        }
        if (i == hi) {
            printf("\033[m");           /* 普通の色に戻す */
        }
    }
    putchar('\n');
}


/* 配列のクイックソート（石畑清「アルゴリズムとデータ構造」p.169） */
void sort(int lo, int hi) {
    int i, j, mi, pivot;

    if (lo >= hi) {     /* lo >= hi のときは何もしなくてよい */
        return;
    }

    mi = (lo + hi) / 2;
    pivot = a[mi];      /* これを pivot に選ぶ理由は特にない */

    i = lo; j = hi;

    /* 外側の while の各くりかえしの最初と最後では「k < i ならば */
    /* a[k] <= pivot」「j < k ならば a[k] >= pivot」が成り立つことに注意 */

    while (i <= j) {
        while (a[i] < pivot) {
            i++;
        }
        while (a[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(i, j); i++, j--;
        }
    }
    print(lo, pivot, hi);           /* 確認のため印字 */
    sort(lo, j), sort(i, hi);
}