プログラミング演習１（課題２：整列：第３回目）

練習問題（３－１）:挿入ソート

ソースファイル名　(example3_1.c)

#include <stdio.h> /* printf()利用のため */
#include <stdlib.h> /* rand()利用のため */
#include <time.h> /* clock()利用のため */
#define N 10 /* 整列対象要素数 */

/**
 * 配列の中身を表示する関数
 * @param a 表示する配列
 * @param n 配列の要素数
 */
void
print_array(const int a[], int n) 
{
    int i;

    for (i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

/**
 * 整列されているかどうか確認する関数 
 * @param a 確認対象配列
 * @param n 配列の要素数
 */
void
is_sorted(const int a[], int n) 
{
    int i;
    for (i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
	        printf("昇順に整列されていません\n");
    	    return;
		}
    }
    printf("昇順に整列されています\n");
}

/**
 * 挿入ソート
 * @param a 整列対象配列
 * @param n 配列の要素数 
 */
void
insertion_sort(int a[], int n) 
{
/* ここ実装せよ */
/* どうしてもわからない場合のヒント */
'http://www.ced.is.utsunomiya-u.ac.jp/lecture/2024/prog/p1/kadai2/hint3_1_1.html'
}

int 
main(void)
{
    int i;
    int n = N; /* 整列対象要素数 */
    int a[N]; 
    clock_t start,end;

    /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */
    for (i = 0; i < n; i++) {
        a[i] = rand();
	    /* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */
    }
    /* 昇順にソートされているか確認（デバッグ用） */
    is_sorted(a, n); 
    /* 配列の中身を確認（デバッグ用） */
    print_array(a, n);
    /* 開始時刻の取得 */
    start = clock();
    /* 挿入ソート関数の呼び出し */
    insertion_sort(a, n); 
    /* 終了時刻の取得 */
    end = clock(); 
    /* 配列の中身を確認（デバッグ用） */
    print_array(a, n); 
    /* 昇順にソートされているか確認（デバッグ用） */
    is_sorted(a, n); 
    /* 実行時間の表示 */
    printf("%d 個の要素の挿入ソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); 
    return 0;
}

追加課題）　要素数(N)を100, 1000, 10000, 100000とした場合の実行時間を比較せよ
追加課題）　関数insert_sort中で配列の要素の比較、交換の回数をそれぞれ出力できるように改造せよ

出力例

昇順に整列されていません
昇順に整列されています
比較を 24962883 回、交換を 24952888 回行いました
10000 個の要素の挿入ソートの実行に 0.405000 [秒]かかりました

練習問題（３－２）:クイックソート

ソースファイル名 (example3_2.c)

#include <stdio.h> /* printf()利用のため */
#include <stdlib.h> /* rand()利用のため */
#include <time.h> /* clock()利用のため */
#define N 10 /* 整列対象要素数 */

/**
 * 配列の中身を表示する関数
 * @param a 表示する配列
 * @param n 配列の要素数
 */
void
print_array(const int a[], int n) 
{
    int i;

    for (i = 0; i < n; i++) {
	printf("%d ", a[i]);
    }
    printf("\n");
}

/**
 * 整列されているかどうか確認する関数 
 * @param a 確認対象配列
 * @param n 配列の要素数
 */
void
is_sorted(const int a[], int n) 
{
    int i;
    for (i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
 	    printf("昇順に整列されていません\n");
    	    return;
	}
    }
    printf("昇順に整列されています\n");
}

/**
 * クイックソートの本体
 * @param a 整列対象配列
 * @param l 対象の最初の要素番号
 * @param r 対象の最後の要素番号 
 */
void
quick_sort_core(int a[], int l, int r) 
{
/* ここを実装せよ */
}

/**
 * これまでの整列関数のインターフェースにあわせるクイックソート呼び出し関数 
 * @param a 整列対象配列
 * @param n 配列の要素数 
 */
void
quick_sort(int a[], int n) {
    quick_sort_core(a, 0, n - 1);
}

int 
main(void)
{
    int i;
    int n = N; /* 整列対象要素数 */ 
    int a[N]; 
    clock_t start,end;

    /* 0からRAND_MAXの一様乱数をn個生成し、配列aに格納 */
    for (i = 0; i < n; i++) {
        a[i] = rand();
	/* 出力確認(print_array)するときは a[i]=rand()%100 としておくと見やすい */
    }
    /* 昇順にソートされているか確認（デバッグ用） */	
    is_sorted(a, n);
    /* 配列の中身を確認（デバッグ用） */
    print_array(a, n);
    /* 開始時刻の取得 */
    start = clock();
    /* クイックソート関数の呼び出し */
    quick_sort(a, n);
    /* 終了時刻の取得 */
    end = clock();
    /* 配列の中身を確認（デバッグ用） */
    print_array(a, n);
    /* 昇順にソートされているか確認（デバッグ用） */
    is_sorted(a, n); 
    /* 実行時間の表示 */
    printf("%d 個の要素のクイックソートの実行に %f [秒]かかりました\n", n, (double)(end - start) / CLOCKS_PER_SEC); 
    return 0;
}

追加課題）　要素数(N)を100, 1000, 10000, 100000とした場合の実行時間を比較せよ
追加課題）　関数quick_sort_core中で配列の要素の比較、交換の回数をそれぞれ出力できるように改造せよ