2015 Data Structures and Algorithms



#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define     N   10  /* データの件数 */
 
int     sort[N];
 
void BubbleSort(void) {
    int i, j, flag;
 
    do {
        flag = 0;
        for(i = 0; i < N - 1; i++) {
            /* 先頭から順に見ていって */
            if(sort[i] > sort[i + 1]) {
                /* 左右の並びがおかしければ入れ替える */
                flag = 1;
                j = sort[i];
                sort[i] = sort[i + 1];
                sort[i + 1] = j;
            }
        }
        /* 1度も並べ替えをせずに見終わったら終了 */
    } while(flag == 1);
}
 
int main(void) {
    int i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i]=rand();
        printf("%d ",sort[i]);
    }
 
    printf("\nソート開始:\n");
    BubbleSort();
 
    printf("\nソート終了:\n");
 
    for(i=0;i<N;i++) {
        printf("%d ",sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




  1. データの件数をどこまで増やせばlist1-1.cとの間で明らかな実行時間の差(数秒程度の差)が現れるか、調べてみよう。(時間の計測についてはここを参照。)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define     N   10  /* データの件数 */
 
int     sort[N];
 
void BubbleSort(void) {
    int i, j, flag, k;
 
    k = 0;
    do {
        flag = 0;
        for(i = 0; i < N - 1 - k; i++) {
            if(sort[i] > sort[i+1]) {
                flag = 1;
                j = sort[i];
                sort[i] = sort[i + 1];
                sort[i + 1] = j;
            }
        }
        k++;
    } while(flag == 1);
}
 
int main(void) {
    int i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i]=rand();
        printf("%d ",sort[i]);
    }
 
    printf("\nソート開始:\n");
    BubbleSort();
 
    printf("\nソート終了:\n");
 
    for(i=0;i<N;i++) {
        printf("%d ",sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




コードを次のように変更しよう。
  1. 逆順にソートしてみよう。
  2. データの件数をどこまで増やせばlist1-2.cよりも明らかに(数秒程度)早く終わるようになるか、調べてみよう。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define     N   10  /* データの件数 */
 
int sort[N];
 
void QuickSort(int bottom,int top,int *data) {
    int lower, upper, div, temp;
    if(bottom >= top) {
        return;
    }
    /* 先頭の値を「適当な値」とする */
    div = data[bottom];
    for(lower = bottom, upper = top; lower < upper;) {
        while(lower <= upper && data[lower] <= div) {
            lower++;
        }
        while(lower <= upper && data[upper] > div) {
            upper--;
        }
        if(lower < upper) {
            temp = data[lower];
            data[lower] = data[upper];
            data[upper] = temp;
        }
    }
    /* 最初に選択した値を中央に移動する */
    temp = data[bottom];
    data[bottom] = data[upper];
    data[upper] = temp;
 
    QuickSort(bottom, upper - 1, data);
    QuickSort(upper + 1, top, data);
}
 
int main(void) {
    int i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i] = rand();
        printf("%d ", sort[i]);
    }
 
    printf("\nソート開始:\n");
    QuickSort(0, N - 1, sort);
 
    printf("\nソート終了:\n");
 
    for(i = 0; i < N; i++) {
        printf("%d ",sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define     N   10  /*データの件数*/
 
int sort[N];
 
int compare(const void *arg1, const void *arg2) {
    return(*((int *)arg1) - *((int *)arg2));
}
 
int main(void) {
    int i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列をランダムに初期化する */
        sort[i] = rand();
        printf("%d ", sort[i]);
    }
 
    printf("\nソート開始:\n");
    qsort(sort, N, sizeof(sort[0]), compare);
 
    printf("\nソート終了:\n");
 
    for(i = 0; i < N; i++) {
        printf("%d ", sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




  1. 逆順にソートしてみよう。
  2. データの件数をどこまで増やせばlist1-2.cよりも明らかに(数秒程度)早く終わるようになるか、調べてみよう。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define     N   10  /* データの件数 */
 
int     sort[N];
int     buffer[N];
 
void MergeSort(int n,int x[]) {
    int i, j, k, m;
    if(n <= 1) {
        return;
    }
    m = n / 2;
 
    /* ブロックを前半と後半に分ける */
    MergeSort(m, x);
    MergeSort(n - m, x + m);
 
    /* 併合(マージ)操作 */
    for(i = 0; i < m; i++) {
        buffer[i] = x[i];
    }
    j = m;
    i = k = 0;
    while(i < m && j < n) {
        if(buffer[i] <= x[j]) {
            x[k++] = buffer[i++];
        } else {
            x[k++] = x[j++];
        }
    }
    while(i < m) {
        x[k++]=buffer[i++];
    }
}
 
int main(void) {
    int     i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i] = rand();
        printf("%d ", sort[i]);
    }
 
    printf("\nソート開始:\n");
    MergeSort(N, sort);
 
    printf("\nソート終了:\n");
 
    for(i = 0; i < N; i++) {
        printf("%d ", sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




  1. データの件数をどこまで増やせばlist1-2.cよりも明らかに(数秒程度)早く終わるようになるか、調べてみよう。
  2. データの件数を増やした上で、収縮率を0.1刻みで変えてみて、実行時間が最も短い収縮率を求めてみよう。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N   10  /* データの件数 */
 
int sort[N];
 
void CombSort(void) {
    int i, temp, flag, gap;
    gap = N;
 
    do {
        gap = (gap * 10) / 13;
        /* 収縮率は1.3(gapが毎回1/1.3になる) */
        if(gap == 0) {
            gap = 1;
        }
 
        flag = 1;
        /* 先頭から順に見ていって */
        for(i = 0; i < N - gap; i++) {
            /* 距離がgapだけ離れた要素を比較し,
                並びがおかしければ */
            if (sort[i] > sort[i + gap]) {
                /* 入れ替える */
                flag = 0;
                temp = sort[i];
                sort[i] = sort[i + gap];
                sort[i + gap] = temp;
            }
        }
 
        /* 1度も並べ替えをせずに,gap=1で見終わったら終了 */
    } while((gap > 1) || flag != 1);
}
 
int main(void) {
    int i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i] = rand();
        printf("%d ", sort[i]);
    }
 
    printf("\nソート開始:\n");
    CombSort();
 
    printf("\nソート終了:\n");
 
    for(i=0;i<N;i++) {
        printf("%d ", sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N    10 /* データの件数 */
 
int sort[N];
 
void InsertSort(void) {
    int i, sorted, temp, insert;
 
    /* 最初から最後まですべてソート済みになるまで繰り返す */
    for(sorted = 0; sorted < N - 1; sorted++) {
        /* ソート済み領域の直後の値を取り出す */
        insert = sort[sorted + 1];
 
        /* 挿入する場所を見つける(リニアサーチ) */
        for(i = 0; i <= sorted; i++) {
            if(sort[i] > insert) {
                break;
            }
        }
 
        /* ソート済み領域直後の値を挿入する */
        while(i <= sorted + 1) {
            temp = sort[i];
            sort[i] = insert;
            insert = temp;
            i++;
        }
    }
}
 
int main(void) {
    int i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i] = rand() % 1000;
        printf("%d ", sort[i]);
    }
 
    printf("\nソート開始:\n");
    InsertSort();
 
    printf("\nソート終了:\n");
 
    for(i = 0; i < N; i++) {
        printf("%d ",sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}




コードについて次のことを確認しよう。
  1. データの件数を増やしていくと、クイックソートとの実行時間の差がどのように開いていくか、調べてみよう。(N=400000ぐらいにしても、二分程度で終わるはず。クイックソートはもっと早く終わる。できるだけNは大きめに設定して、クイックソートと比較する。データの件数は最低3通りで試す。例えば、N=500000,N=300000,N=100000、など。)
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define N   10  /* データの件数 */
 
int sort[N];
 
void BinaryInsertSort(void) {
    int i, sorted, temp, insert;
    int left, mid, right; /* バイナリサーチ用の追加変数 */
 
    /* 最初から最後まですべてソート済みになるまで繰り返す */
    for(sorted = 1; sorted < N; sorted++) {
        /* ソート済み領域の直後の値を取り出す */
        insert = sort[sorted];
 
        /* 挿入する場所を見つける(バイナリサーチ) */
        left = 0;
        right = sorted;
        while(left < right) {
            mid = (left + right) / 2;
 
            if(sort[mid] < insert) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        i = left;
 
        /* ソート済み領域直後の値を挿入する
            (単純挿入ソートと同じ) */
        while(i <= sorted) {
            temp = sort[i];
            sort[i] = insert;
            insert = temp;
            i++;
        }
    }
}
 
int main(void) {
    int     i;
 
    srand((unsigned int)time(NULL));
 
    printf("ソート準備:\n");
    for(i = 0; i < N; i++) {
        /* 配列にランダムな値を格納 */
        sort[i] = rand() % 1000;
        printf("%d ", sort[i]);
    }
 
    printf("\nソート開始:\n");
    BinaryInsertSort();
 
    printf("\nソート終了:\n");
 
    for(i = 0; i < N; i++) {
        printf("%d ", sort[i]);
    }
 
    printf("\n");
 
    return EXIT_SUCCESS;
}