情報理工学演習Ⅲ 演習課題(第6回)

テーマ  :ソート
実施日  :2020年5月28日(木)
担当   :有村 博紀,堀山 貴史,金森 憲太朗(TF),加井 丈志(TA)
授業連絡先:enshuiii-csit@ist.hokudai.ac.jp(演習課題の提出・質問など)
担当連絡先:kanamori@ist.hokudai.ac.jp(金森),kai@ist.hokudai.ac.jp(加井)


以下の各問に関して,それぞれプログラムを実装せよ. 実装したコードは必ず,以下に示す提出様式を守って, 本授業のメールアドレス(enshuiii-csit@ist.hokudai.ac.jp)宛にメールで提出すること.

例:学生番号02180000の学生の場合

メール本文には,学生番号,所属コース,名前,実施回(第6回演習),解いた問題番号を記載すること. 課題提出によって出席をとるため,解いている途中の状態でも構わないので,演習時間内に一度は提出すること.

実装にはC言語を用い,gcc(ver.4.8.5 以降)でコンパイルすること.

コンパイル・実行例
% gcc 6_1.c		// コンパイル
% ./a.out		// 実行

演習時間内に解き終わらなかった場合は,次回の演習時間までに提出すること.期間中であれば,何度でも再提出してよい. 提出状況等は本授業のホームページまたはELMSグループ(moodle)上に掲示予定なので,適宜確認すること.

問題番号に * が付されたものは,発展課題である.解答は必須ではないが,解ければ成績評価に加点されるので,是非挑戦してほしい.


【問1】 以下の Sample 1 は,非負整数が $n$ 個並んだ数列を受け取り,これを昇順にソートするバブルソートのプログラムである.これを 6_1.c として実装せよ.

Sample 1
 1: #include <stdio.h>
 2: #include <stdlib.h>
 3:
 4: /* 配列を出力する関数 */
 5: void printArray(int* array, int size) {
 6:     int i;
 7:     for (i = 0; i < size; i++) {
 8:         printf("%d ", array[i]);
 9:     }
10:     printf("\n");
11:     return;
12: }
13:
14: /* バブルソートする関数 */
15: void bubbleSort(int* array, int start, int end) {
16:   int i = start;
17:   int flag = 1;
18:   while (flag == 1) {
19:     flag = 0;
20:     for(int j = end; j > i; j--){
21:       if(array[j - 1] > array[j]) {
22:         int tmp = array[j];
23:         array[j] = array[j - 1];
24:         array[j - 1] = tmp;
25:         flag = 1;
26:       }
27:     }
28:     i++;
29:   }
30:   return;
31: }
32:
33: int main() {
34:     int n;
35:     scanf("%d", &n);
36:     int* array = (int*) malloc(sizeof(int) * n);
37:     int i;
38:     for (i = 0; i < n; i++) {
39:         scanf("%d", &array[i]);
40:     }
41:     bubbleSort(array, 0, n - 1);
42:     printArray(array, n);
43:     return 0;
44: }

実装したプログラム 6_1.c に以下の Input 1 を入力して実行し,結果を確認せよ.最初の行の整数は $n$ である.

Input 1

100
913 232 598 0 736 210 162 571 360 532 292 279 681 287 34 469 124 431 347 343 386 328 806 855 516 49 534 987 482 958 931 477 465 554 943 505 169 954 741 937 296 10 890 179 463 814 358 492 62 601 366 755 979 644 832 524 13 494 117 956 679 263 858 513 268 800 393 68 891 372 792 865 311 38 182 71 276 75 710 113 468 448 351 106 245 416 48 290 221 54 953 587 201 222 762 346 703 312 419 392

尚,このような長大な標準入力は,ファイルとして保存(たとえば,input.txt として保存)し,実行の際に以下のようにリダイレクト処理を用いてプログラムに入力する方法が便利である.

実行例
% ./a.out < input.txt	// 実行

【問2】 非負整数が $n$ 個並んだ数列を受け取り,これを昇順にソートするクイックソートのプログラムを 6_2.c として実装せよ.
入力は以下の形式で標準入力から与えられるものとする.出力は Sample 1 の出力と同様に,各要素の直後に半角スペースを置いてこれらを区切り,数列全体の出力の末尾には改行を入れること.

入力形式

$n$
$num_0~~num_1~~\cdots ~~num_n$

実装したプログラム 6_2.c に以下の Input 2 を入力して実行し,結果を確認せよ.

Input 2

100
913 232 598 0 736 210 162 571 360 532 292 279 681 287 34 469 124 431 347 343 386 328 806 855 516 49 534 987 482 958 931 477 465 554 943 505 169 954 741 937 296 10 890 179 463 814 358 492 62 601 366 755 979 644 832 524 13 494 117 956 679 263 858 513 268 800 393 68 891 372 792 865 311 38 182 71 276 75 710 113 468 448 351 106 245 416 48 290 221 54 953 587 201 222 762 346 703 312 419 392

【問3*】 非負整数が $n$ 個並んだ数列を受け取り,これを昇順にソートするヒープソートのプログラムを 6_3.c として実装せよ.
入力は以下の形式で標準入力から与えられるものとする.出力は Sample 1 の出力と同様に,各要素の直後に半角スペースを置いてこれらを区切り,数列全体の出力の末尾には改行を入れること.

入力形式

$n$
$num_0~~num_1~~\cdots ~~num_n$

実装したプログラム 6_3.c に以下の Input 3 を入力して実行し,結果を確認せよ.

Input 3

100
913 232 598 0 736 210 162 571 360 532 292 279 681 287 34 469 124 431 347 343 386 328 806 855 516 49 534 987 482 958 931 477 465 554 943 505 169 954 741 937 296 10 890 179 463 814 358 492 62 601 366 755 979 644 832 524 13 494 117 956 679 263 858 513 268 800 393 68 891 372 792 865 311 38 182 71 276 75 710 113 468 448 351 106 245 416 48 290 221 54 953 587 201 222 762 346 703 312 419 392