整列

5.1 選択ソートの実装（基本のみ）

以下は選択ソートを含むC言語プログラムであり，教科書リスト5.2をベースに実装される．ソースコードは，selection_sort.h，selection_sort.c，main_selection_sort.c に分割されている．また，課題5で共通の関数群（sort_util.c, sort_util.h）もここで実装する．

5.1.1 基本課題

ヘッダーファイル sort_util.h

#ifndef INCLUDE_GUARD_SORT_UTIL_H
#define INCLUDE_GUARD_SORT_UTIL_H

#include <stdbool.h>

bool is_sorted(int a[], int n);
void display(int a[], int n);

#endif

ソースファイル sort_util.c

#include <stdbool.h>
#include <stdio.h>

bool is_sorted(int a[], int n) {
    // ...
}

void display(int a[], int n) {
    // ...
}

ヘッダーファイル selection_sort.h

#ifndef INCLUDE_GUARD_SELECTION_SORT_H
#define INCLUDE_GUARD_SELECTION_SORT_H

void selection_sort(int a[], int n);

#endif

ソースファイル selection_sort.c

#include "selection_sort.h"

void selection_sort(int a[], int n) {
    // ...
}

ソースファイル main_selection_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "selection_sort.h"
#include "sort_util.h"

static int const DATA_1[] = { 3, 6, 8, 0, 5, 9, 7, 1, 2, 4 };
static int const DATA_2[] = { 4, 6, 9, 5, 3, 0, 2, 8, 7, 1 };
static int const DATA_3[] = { 6, 9, 5, 8, 7, 2, 0, 3, 1, 4 };
static int const DATA_4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
static int const DATA_5[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

void check(int const* data, int n, char const* name) {
    int* a = (int*)calloc(n, sizeof(int));
    memcpy(a, data, n * sizeof(n));

    display(a, n);
    selection_sort(a, n);
    display(a, n);

    if (!is_sorted(a, n)) {
        fprintf(stderr, "Error: %s\n", name);
        exit(EXIT_FAILURE);
    }

    free(a);
}

int main(void) {
    check(DATA_1, 10, "DATA_1");
    check(DATA_2, 10, "DATA_2");
    check(DATA_3, 10, "DATA_3");
    check(DATA_4, 10, "DATA_4");
    check(DATA_5, 10, "DATA_5");
}

ファイル Makefile

selection_sort: main_selection_sort.o selection_sort.o sort_util.o

実行例

$ make selection_sort

を実行し，コンパイルを行う．実行ファイル selection_sort を実行すると，次のような結果が表示される．

$ ./selection_sort
3 6 8 0 5 9 7 1 2 4
0 1 2 3 4 5 6 7 8 9
4 6 9 5 3 0 2 8 7 1
0 1 2 3 4 5 6 7 8 9
6 9 5 8 7 2 0 3 1 4
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
$

基本課題の説明

1. 課題共通の関数を実装し，動作を確認すること．
   • 共通の関数は以降の課題でも用いるため，ソースコードを分け，分割コンパイルを行うこと．
2. sort_util.c には，最低限以下の関数を定義すること．
   • bool is_sorted(int a[], int n)
     • 長さがnの配列aが整列されているか確認する関数である．
     • 整列されている場合はtrue，されていない場合はfalseを返す．
   • void display(int a[], int n)
     • 長さがnの配列aに含まれる要素を標準出力に表示する関数である．
     • 配列の要素間を半角スペース1文字で区切って出力すること．
     • 最後の要素を出力した後は，改行を1文字出力すること．
3. 選択ソートを実装し，以下の要件を確認すること．
   • 入力したデータが正しく整列されることを，複数の例を用いて確認すること．
     • ヒント：乱数を用いて，様々な長さやデータについて整列動作を確認しても良い
   • 適当なデータ（5 <= n < 10）を実際に整列する例を示し，動作について説明すること．

5.2 挿入ソートの実装（基本のみ）

5.2.1 基本課題

以下は挿入ソートを含むC言語プログラムであり，教科書リスト5.5をベースに実装される．ソースコードは，insertion_sort.h，insertion_sort.c，main_insertion_sort.c に分割されている．

ヘッダーファイル insertion_sort.h

#ifndef INCLUDE_GUARD_INSERTION_SORT_H
#define INCLUDE_GUARD_INSERTION_SORT_H

void insertion_sort(int a[], int n);

#endif

ソースファイル insertion_sort.c

#include "insertion_sort.h"

void insertion_sort(int a[], int n) {
    // ...
}

ソースファイル main_insertion_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "insertion_sort.h"
#include "sort_util.h"

static int const DATA_1[] = { 3, 6, 8, 0, 5, 9, 7, 1, 2, 4 };
static int const DATA_2[] = { 4, 6, 9, 5, 3, 0, 2, 8, 7, 1 };
static int const DATA_3[] = { 6, 9, 5, 8, 7, 2, 0, 3, 1, 4 };
static int const DATA_4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
static int const DATA_5[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

void check(int const* data, int n, char const* name) {
    int* a = (int*)calloc(n, sizeof(int));
    memcpy(a, data, n * sizeof(n));

    display(a, n);
    insertion_sort(a, n);
    display(a, n);

    if (!is_sorted(a, n)) {
        fprintf(stderr, "Error: %s\n", name);
        exit(EXIT_FAILURE);
    }

    free(a);
}

int main(void) {
    check(DATA_1, 10, "DATA_1");
    check(DATA_2, 10, "DATA_2");
    check(DATA_3, 10, "DATA_3");
    check(DATA_4, 10, "DATA_4");
    check(DATA_5, 10, "DATA_5");
}

ファイル Makefile

• Makefileに適宜内容を追加すること．

実行例

$ make insertion_sort

を実行し，コンパイルを行う．実行ファイル insertion_sort を実行すると，次のような結果が表示される．

$ ./insertion_sort
3 6 8 0 5 9 7 1 2 4
0 1 2 3 4 5 6 7 8 9
4 6 9 5 3 0 2 8 7 1
0 1 2 3 4 5 6 7 8 9
6 9 5 8 7 2 0 3 1 4
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
$

基本課題の説明

1. 挿入ソートを実装し，以下の要件を確認すること．
   • 入力したデータが正しく整列されることを，複数の例を用いて確認すること．
     • ヒント：乱数を用いて，様々な長さやデータについて整列動作を確認しても良い
   • 適当なデータ（5 <= n < 10）を実際に整列する例を示し，動作について説明すること．

5.3 ヒープソートの実装（基本のみ）

5.3.1 基本課題

以下はヒープソートを含むC言語プログラムであり，教科書リスト5.7~5.8をベースに実装される．ソースコードは，heap_sort.h，heap_sort.c，main_heap_sort.c に分割されている．

ヘッダーファイル heap_sort.h

#ifndef INCLUDE_GUARD_HEAP_SORT_H
#define INCLUDE_GUARD_HEAP_SORT_H

void sift_down(int a[], int i, int n);
void build_heap(int a[], int n);
void heap_sort(int a[], int n);

#endif

ソースファイル heap_sort.c

#include "heap_sort.h"

void sift_down(int a[], int i, int n) {
    // ...
}

void build_heap(int a[], int n) {
    // ...
}

void heap_sort(int a[], int n) {
    // ...
}

ソースファイル main_heap_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "heap_sort.h"
#include "sort_util.h"

static int const DATA_1[] = { 3, 6, 8, 0, 5, 9, 7, 1, 2, 4 };
static int const DATA_2[] = { 4, 6, 9, 5, 3, 0, 2, 8, 7, 1 };
static int const DATA_3[] = { 6, 9, 5, 8, 7, 2, 0, 3, 1, 4 };
static int const DATA_4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
static int const DATA_5[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

void check(int const* data, int n, char const* name) {
    int* a = (int*)calloc(n, sizeof(int));
    memcpy(a, data, n * sizeof(n));

    display(a, n);
    heap_sort(a, n);
    display(a, n);

    if (!is_sorted(a, n)) {
        fprintf(stderr, "Error: %s\n", name);
        exit(EXIT_FAILURE);
    }

    free(a);
}

int main(void) {
    check(DATA_1, 10, "DATA_1");
    check(DATA_2, 10, "DATA_2");
    check(DATA_3, 10, "DATA_3");
    check(DATA_4, 10, "DATA_4");
    check(DATA_5, 10, "DATA_5");
}

ファイル Makefile

• Makefileに適宜内容を追加すること．

実行例

$ make heap_sort

を実行し，コンパイルを行う．実行ファイル heap_sort を実行すると，次のような結果が表示される．

$ ./heap_sort
3 6 8 0 5 9 7 1 2 4
0 1 2 3 4 5 6 7 8 9
4 6 9 5 3 0 2 8 7 1
0 1 2 3 4 5 6 7 8 9
6 9 5 8 7 2 0 3 1 4
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
$

基本課題の説明

1. ヒープソートを実装すること．
   • それぞれの関数の動作については，教科書のpp. 103--106（特にリスト5.7と5.8）を参照すること
2. 以下の要件を確認すること．
   • 関数 sift_down, build_heap が正しく動作すること．
   • 入力したデータが heap_sort関数を用いて正しく整列されることを，複数の例を用いて確認すること．
     • ヒント：乱数を用いて，様々な長さやデータについて整列動作を確認しても良い
   • 適当なデータ（5 <= n < 10）を実際に整列する例を示し，動作について説明すること．

5.4 クイックソートの実装（基本のみ）

5.4.1 基本課題

以下はクイックソートを含むC言語プログラムであり，教科書リスト5.9~5.10をベースに実装される．ソースコードは，quick_sort.h，quick_sort.c，main_quick_sort.c に分割されている．

ヘッダーファイル quick_sort.h

#ifndef INCLUDE_GUARD_quick_SORT_H
#define INCLUDE_GUARD_quick_SORT_H

int partition(int a[], int pivot, int left, int right);
void quick_sort(int a[], int n);

#endif

ソースファイル quick_sort.c

#include "quick_sort.h"

int partition(int a[], int pivot, int left, int right) {
    // ...
}

void quick_sort(int a[], int n) {
    // ...
}

ソースファイル main_quick_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "quick_sort.h"
#include "sort_util.h"

static int const DATA_1[] = { 3, 6, 8, 0, 5, 9, 7, 1, 2, 4 };
static int const DATA_2[] = { 4, 6, 9, 5, 3, 0, 2, 8, 7, 1 };
static int const DATA_3[] = { 6, 9, 5, 8, 7, 2, 0, 3, 1, 4 };
static int const DATA_4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
static int const DATA_5[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

void check(int const* data, int n, char const* name) {
    int* a = (int*)calloc(n, sizeof(int));
    memcpy(a, data, n * sizeof(n));

    display(a, n);
    quick_sort(a, n);
    display(a, n);

    if (!is_sorted(a, n)) {
        fprintf(stderr, "Error: %s\n", name);
        exit(EXIT_FAILURE);
    }

    free(a);
}

int main(void) {
    check(DATA_1, 10, "DATA_1");
    check(DATA_2, 10, "DATA_2");
    check(DATA_3, 10, "DATA_3");
    check(DATA_4, 10, "DATA_4");
    check(DATA_5, 10, "DATA_5");
}

ファイル Makefile

• Makefileに適宜内容を追加すること．

実行例

$ make quick_sort

を実行し，コンパイルを行う．実行ファイル quick_sort を実行すると，次のような結果が表示される．

$ ./quick_sort
3 6 8 0 5 9 7 1 2 4
0 1 2 3 4 5 6 7 8 9
4 6 9 5 3 0 2 8 7 1
0 1 2 3 4 5 6 7 8 9
6 9 5 8 7 2 0 3 1 4
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
$

基本課題の説明

1. クイックソートを実装すること．
   • それぞれの関数の動作については，教科書のpp. 107--111（特にリスト5.9と5.10）を参照すること
2. 以下の要件を確認すること．
   • 関数 partition が正しく動作すること．
   • 入力したデータが quick_sort 関数を用いて正しく整列されることを，複数の例を用いて確認すること．
     • ヒント：乱数を用いて，様々な長さやデータについて整列動作を確認しても良い
   • 適当なデータ（5 <= n < 10）を実際に整列する例を示し，動作について説明すること．
3. ヒープソートおよびクイックソートの性能を分析せよ．
   1. ランダムな入力データを要素として持つ大きさ numdata (numdata = 1000, 2000, ..., 10,000)の配列を生成し，各整列法を実行し，整列に要するデータの比較回数を調べ，結果をグラフを用いて分析すること．
   2. ランダムな入力データを要素として持つ配列を生成し，各整列法を実行し，整列に要する実行時間を調べ，結果をグラフを用いて分析すること． 配列の大きさは，実行時間が0.1 ~ 数秒程度になるように選ぶこと (実行時間を調べる際には，課題3: ハッシュ法に記載した事項を念頭に置きましょう)．
   3. クイックソートの計算量が最悪 (すなわち，O(n²)の計算量) になるような配列を生成し，最悪の場合の性能を整列に要するデータの比較回数を調べ，結果をグラフを用いて分析すること．
   4. 上記 1 ~ 3 の実験結果から，クイックソートとヒープソートの性能について，比較，考察せよ．

5.5 基数ソートの実装（発展のみ）

5.5.1 発展課題

以下は基数ソートを含むC言語プログラムであり，教科書リスト5.9~5.10をベースに実装される．ソースコードは，radix_sort.h，radix_sort.c，main_radix_sort.c に分割されている．

ヘッダーファイル radix_sort.h

#ifndef INCLUDE_GUARD_RADIX_SORT_H
#define INCLUDE_GUARD_RADIX_SORT_H

void radix_sort(int a[], int n);

#endif

ソースファイル radix_sort.c

#include "radix_sort.h"

void radix_sort(int a[], int n) {
    // ...
}

ソースファイル main_radix_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "radix_sort.h"
#include "sort_util.h"

static int const DATA_1[] = { 3, 6, 8, 0, 5, 9, 7, 1, 2, 4 };
static int const DATA_2[] = { 63, 45, 76, 38, 38, 23, 91, 41, 37, 58 };
static int const DATA_3[] = { 297, 423, 250, 167, 482, 471, 778, 914, 798, 265 };

void check(int const* data, int n, char const* name) {
    int* a = (int*)calloc(n, sizeof(int));
    memcpy(a, data, n * sizeof(n));

    display(a, n);
    radix_sort(a, n);
    display(a, n);

    if (!is_sorted(a, n)) {
        fprintf(stderr, "Error: %s\n", name);
        exit(EXIT_FAILURE);
    }

    free(a);
}

int main(void) {
    check(DATA_1, 10, "DATA_1");
    check(DATA_2, 10, "DATA_2");
    check(DATA_3, 10, "DATA_3");
}

ファイル Makefile

• Makefileに適宜内容を追加すること．

実行例

$ make radix_sort

を実行し，コンパイルを行う．実行ファイル radix_sort を実行すると，次のような結果が表示される．

$ ./radix_sort
3 6 8 0 5 9 7 1 2 4
0 1 2 3 4 5 6 7 8 9
63 45 76 38 38 23 91 41 37 58
23 37 38 38 41 45 58 63 76 91
297 423 250 167 482 471 778 914 798 265
167 250 265 297 423 471 482 778 798 914
$

発展課題の説明

1. 基数ソートを実装せよ
   • この基数ソートは，10進数の各桁にバケットソートを適用し，整数を整列するアルゴリズムであり，配列 a の各要素 a[i] は, 0 <= a[i] < 10 とする．
2. 以下の要件を確認すること．
   • 入力したデータが radix_sort 関数を用いて正しく整列されることを，複数の例を用いて確認すること．
     • ヒント：乱数を用いて，様々な長さやデータについて整列動作を確認しても良い
   • 整数143, 322, 246, 755, 123, 563, 514, 522を要素とする配列に対して動作を確認すること．
     • 各桁の処理の後のバケットの内容を示すこと．

5.6 マージソートの実装（発展のみ）

5.6.1 発展課題

以下はマージソートを含むC言語プログラムであり，教科書リスト5.9~5.10をベースに実装される．ソースコードは，merge_sort.h，merge_sort.c，main_merge_sort.c に分割されている．

ヘッダーファイル merge_sort.h

#ifndef INCLUDE_GUARD_MERGE_SORT_H
#define INCLUDE_GUARD_MERGE_SORT_H

void merge(int a[], int left, int mid, int right);
void merge_sort(int a[], int n);

#endif

ソースファイル merge_sort.c

#include "merge_sort.h"

void merge(int a[], int left, int mid, int right) {
    // ...
}

void merge_sort(int a[], int n) {
    // ...
}

ソースファイル main_merge_sort.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "merge_sort.h"
#include "sort_util.h"

static int const DATA_1[] = { 3, 6, 8, 0, 5, 9, 7, 1, 2, 4 };
static int const DATA_2[] = { 4, 6, 9, 5, 3, 0, 2, 8, 7, 1 };
static int const DATA_3[] = { 6, 9, 5, 8, 7, 2, 0, 3, 1, 4 };
static int const DATA_4[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
static int const DATA_5[] = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

void check(int const* data, int n, char const* name) {
    int* a = (int*)calloc(n, sizeof(int));
    memcpy(a, data, n * sizeof(n));

    display(a, n);
    merge_sort(a, n);
    display(a, n);

    if (!is_sorted(a, n)) {
        fprintf(stderr, "Error: %s\n", name);
        exit(EXIT_FAILURE);
    }

    free(a);
}

int main(void) {
    check(DATA_1, 10, "DATA_1");
    check(DATA_2, 10, "DATA_2");
    check(DATA_3, 10, "DATA_3");
    check(DATA_4, 10, "DATA_4");
    check(DATA_5, 10, "DATA_5");
}

ファイル Makefile

• Makefileに適宜内容を追加すること．

発展課題の説明

1. マージソートを実装すること．
   • それぞれの関数の動作については，教科書のpp. 111--115（特にリスト5.11と5.12）を参照すること
2. 以下の要件を確認すること．
   • 関数 merge が正しく動作すること．
   • 入力したデータが merge_sort関数を用いて正しく整列されることを，複数の例を用いて確認すること．
     • ヒント：乱数を用いて，様々な長さやデータについて整列動作を確認しても良い
   • 適当なデータ（5 <= n < 10）を実際に整列する例を示し，動作について説明すること．
     • マージソートの各ステップで，動作（分割・マージ）および配列や分割の状態について示すこと．

5.7: 提出物について

5.7.1: 要件確認についての注意事項

要件確認するためには，各自で適宜 main 関数の中身を書き換え，テストパターンを追加してください．

また，レポートには，

• 「プログラムの入力となるデータが何で，それがプログラムのどの部分でどのようなロジックで処理されているため，このような実行結果が得られるから，要件を満たしている」という説明文
• その実行結果

の両方を書いてください．そうでないと，レポートの読み手(採点者)は，要件を満たすことを本当に確認出来ているのか判断出来ません．

5.7.2: 自動採点の注意点

• レポートの自動採点を行うため，以下の指示に従ってプログラムを作成，提出すること．
  • 課題中で，関数名，引数，戻り値等が指定されている場合，これらを変更しないこと．
  • 画面出力の書式は，指定されたものを守ること．

5.7.3: 提出ファイル一覧

• report5.pdf （レポート）
• Makefile
• sort_util.c
• sort_util.h
• selection_sort.c
• selection_sort.h
• main_selection_sort.c
• insertion_sort.c
• insertion_sort.h
• main_insertion_sort.c
• heap_sort.c
• heap_sort.h
• main_heap_sort.c
• quick_sort.c
• quick_sort.h
• main_quick_sort.c
• radix_sort.c（発展課題）
• radix_sort.h（発展課題）
• main_radix_sort.c（発展課題）
• merge_sort.c（発展課題）
• merge_sort.h（発展課題）
• main_merge_sort.c（発展課題）

5.7.4: 提出ファイルの構成

• ディレクトリ class5 を作成して，その中に上記ファイルを配置すること．
• class5 を ZIP で圧縮した class5.zip ファイルを manaba に提出すること．

（class5.zip）の構造）
class5/
  +- report5.pdf
  +- Makefile
  +- sort_util.c
  +- sort_util.h
  +- selection_sort.c
  +- selection_sort.h
  +- main_selection_sort.c
  +- insertion_sort.c
  +- insertion_sort.h
  +- main_insertion_sort.c
  +- heap_sort.c
  +- heap_sort.h
  +- main_heap_sort.c
  +- quick_sort.c
  +- quick_sort.h
  +- main_quick_sort.c
  +- radix_sort.c
  +- radix_sort.h
  +- main_radix_sort.c
  +- merge_sort.c
  +- merge_sort.h
  +- main_merge_sort.c

5.8 提出締切

2024年12月9日（月）13:30