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

練習問題（１）:配列の中身を反転するプログラム

ソリューション名　(example1_1)、ソースファイル名　(example1_1.c)

#include <stdio.h> /* printf()利用のため */
#include <stdlib.h> /* rand()利用のため */

/**
 * 配列の中身の順番を反転させる関数
 * @param a 反転させる配列
 * @param n 配列の要素数
 */
void
reverse_int(int a[], int n) 
{
/* ここを実装せよ */
}

/**
 * 配列の中身を表示する関数
 * @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");
}

int
main(void) 
{
    int i;
    int n = 10;
    int a[10];

    /* n個の0以上100未満の疑似一様整数乱数の生成し配列aに格納 */
    for (i = 0; i < n; i++) {
        a[i] = rand() % 100;
    }
    /* 配列の中身の表示 */
    print_array(a, n);
    /* 配列の中身の順番を反転 */
    reverse_int(a, n);
    /* 配列の中身の表示 */
    print_array(a, n);
    return 0;
}

出力例

2 33 43 62 29 0 8 52 56 67
67 56 52 8 0 29 62 43 33 2

練習問題（２）:文字列を反転させるプログラム

ソリューション名　(example1_2)、ソースファイル名　(example1_2.c)

#include <stdio.h>

/**
 * 文字列の長さをはかる関数
 * @param str 文字列
 * @return 文字列の長さ
 */
size_t
strlen(const char* str) 
{
    size_t len = 0;
    int i = 0;

    while (str[i++] != '\0') {
        len++;
    }
    /* 上の別の書き方
    while (*str++) {
        len++;
    }
    */
    return len;
}

/**
 * 文字列を反転させる関数
 * @param str 反転対象の文字列
 */
void
reverse_char(char* str) 
{
/* ここを実装せよ */
}

int
main(void) 
{
    char str[]="UTSUNOMIYA";

    printf("%s\n", str); /* UTSUNOMIYAと出力 */
    /* 文字列の反転 */
    reverse_char(str);
    printf("%s\n", str); /* AYIMONUSTUと出力 */
    return 0;
}

出力例

UTSUNOMIYA
AYIMONUSTU

練習問題（３）：バブルソート

ソリューション名　(example1_3)、ソースファイル名　(example1_3.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
bubble_sort(int a[], int n) 
{
/* ここを実装せよ */
/* どうしてもわからない場合のヒント */
'http://www.ced.is.utsunomiya-u.ac.jp/lecture/2014/prog/p1/kadai3/hint1_3_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(); 
    /* バブルソート関数の呼び出し */
    bubble_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とした場合の実行時間を比較せよ。
追加課題）　関数bubble_sort中で配列の要素の比較、交換の回数をそれぞれ出力できるように改造せよ。

出力例

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