PG13-6S

Transcription

1 プログラム演習 I レポート 学籍番号 担当教員 : 小林郁夫 氏名 実習日平成 26 年 7 月 4 日 提出期限 7 月 11 日提出日 7 月 17 日 1 週遅れ 第 13 回 テーマ : 並べ替えのアルゴリズム 教員使用欄 15 S A B C 再提出 課題 1 バブルソートの実行画面

2 プログラムのソースコード // day13_akb1.cpp : コンソールアプリケーションのエントリポイントを定義します // #include "stdafx.h" #include "conio.h" extern void bubble_sort(int x[], int count); int _tmain(int argc, _TCHAR* argv[]) int x[] = 5, 1, 8, 7, 4, 2, 0 ; int i, count; // 個数を数える for (i = 0, count = 0; x[i]; i++) count++; printf(" 並べ替え前 \n"); for (i = 0; x[i]; i++) printf("%d: %d\n", i, x[i]); bubble_sort(x, count); printf("\n 並べ替え後 \n"); for (i = 0; x[i]; i++) printf("%d: %d\n", i, x[i]); _getch(); return 0; void bubble_sort(int x[], int count)

3 bool swapped; int i, y; printf("\n** バブルソートの実行 **\n"); do swapped = false; for (i = 0; i < count - 1; i += 2) if (x[i]>x[i + 1]) y = x[i]; x[i] = x[i + 1]; x[i + 1] = y; swapped = true; for (i = 1; i < count - 1; i += 2) if (x[i]>x[i + 1]) y = x[i]; x[i] = x[i + 1]; x[i + 1] = y; swapped = true; while (swapped); swapped = false; で swapped を false にする for (i = 0; i < count - 1; i += 2) で1 番目の数字から順番に見る if (x[i]>x[i + 1]) で次の数字と比較して大きかったら y = x[i]; で一時的に y に移す x[i] = x[i + 1]; で位置を交換して x[i + 1] = y; で移した数をもとに戻す swapped = true; で swapped を true にする 次に 2 番目の数字から同じように並び替えをする while (swapped); swapped が true の場合はこれをループする

4 選択ソートの実行画面 小林のミスで これは選択ソ ートですね プログラムのソースコード // day13_akb1.cpp : コンソールアプリケーションのエントリポイントを定義します // #include "stdafx.h" #include "conio.h" extern void bubble_sort(int x[], int count); extern void bucket_sort(int x[], int count); int _tmain(int argc, _TCHAR* argv[]) int x[] = 5, 1, 8, 7, 4, 2, 0 ; int i, count; // 個数を数える

5 for (i = 0, count = 0; x[i]; i++) count++; printf(" 並べ替え前 \n"); for (i = 0; x[i]; i++) printf("%d: %d\n", i, x[i]); // bubble_sort(x, count); bucket_sort(x, count); printf("\n 並べ替え後 \n"); for (i = 0; x[i]; i++) printf("%d: %d\n", i, x[i]); _getch(); return 0; void bubble_sort(int x[], int count) bool swapped; int i, y; printf("\n** バブルソートの実行 **\n"); do swapped = false; for (i = 0; i < count - 1; i += 2) if (x[i]>x[i + 1]) y = x[i]; x[i] = x[i + 1]; x[i + 1] = y; swapped = true; for (i = 1; i < count - 1; i += 2) if (x[i]>x[i + 1])

6 y = x[i]; x[i] = x[i + 1]; x[i + 1] = y; swapped = true; while (swapped); void bucket_sort(int x[], int count) int i, j; int min_index, swap; printf("\n** バケットソートの実行 **\n"); for (i = 0; i <= count - 2; i++) min_index = i; for (j = i + 1; j <= count - 1; j++) if (x[j] < x[min_index])min_index = j; swap = x[i]; x[i] = x[min_index]; x[min_index] = swap; 選択ソート要素の列を端から順に調べ 一番小さい値を持つ要素を抜き出して最初の要素と交換し さらに未整列の部分から一番小さい値を持つ要素を抜き出して 2 番目の要素と交換し という操作を繰り返してソートする ( 昇順ソートの場合 ) ( 引用 : 選択ソートは最初の要素を設定して 残りの要素と比較しながら 小さいものがあれば 交換するという方法で バブルソートと違って毎回入れ替える作業が減るため 選択ソ ートの方が早く並べ替えられる

7 おまけの課題 挿入ソート対象集合の先頭付近がソートされているとして 対象集合の未ソートの部分から要素を順次取り出し, それまでに取り出した要素の集合に順序関係を保つよう挿入してソートを行う方法 マージソート対象集合を単純に2 等分した区分にします それぞれの区分内でソートされていれば 2つの区分をマージ ( 併合 ) することにより 全体がソートされます 区分内でソートされていない場合は それをさらに2 等分して 同様な操作を行います これを繰り返すことにより全体がソートされる クイックソート全体のなかから 中間的な基準となる要素を1つ選び ( ピボット- 枢軸 -という) これより小さい要素と大きい要素の区分に分割します さらに分割した2つの区分の中で分割を行います これを繰り返してソートを行う方法 シェルソートある間隔で要素を取り出した部分列を整列し さらに間隔をつめた部分列を取り出してソートする方法です ある一定間隔おきに取り出した要素からなる部分列をそれぞれソートし ( このときに挿入ソートや他の方法を用いることもあります ) 更に間隔を詰めて同様の操作を行い 間隔が1になるまで繰り返すことによりソートが実現する ヒープソート 未整列の部分を木構造の順序木 ( ヒープ構造 ) に構成し そこから最大値又は最小値を 取り出して既整列の部分に移す この操作を繰り返して 実整列部分を縮めていく方法 ( 引用 :

8 発展課題 1 挿入ソート 実行画面 プログラムのソースコード // day13_akb1.cpp : コンソールアプリケーションのエントリポイントを定義します // #include "stdafx.h" #include "conio.h" extern void bubble_sort(int x[], int count); extern void bucket_sort(int x[], int count); void extern insertion_sort(int x[], int count); int _tmain(int argc, _TCHAR* argv[]) int x[] = 5, 1, 8, 7, 4, 2, 0 ; int i, count;

9 // 個数を数える for (i = 0, count = 0; x[i]; i++) count++; printf(" 並べ替え前 \n"); for (i = 0; x[i]; i++) printf("%d: %d\n", i, x[i]); // bubble_sort(x, count); // bucket_sort(x, count); insertion_sort(x, count); printf("\n 並べ替え後 \n"); for (i = 0; x[i]; i++) printf("%d: %d\n", i, x[i]); _getch(); return 0; void bubble_sort(int x[], int count) bool swapped; int i, y; printf("\n** バブルソートの実行 **\n"); do swapped = false; for (i = 0; i < count - 1; i += 2) if (x[i]>x[i + 1]) y = x[i]; x[i] = x[i + 1]; x[i + 1] = y; swapped = true;

10 for (i = 1; i < count - 1; i += 2) if (x[i]>x[i + 1]) y = x[i]; x[i] = x[i + 1]; x[i + 1] = y; swapped = true; while (swapped); void bucket_sort(int x[], int count) int i, j; int min_index, swap; printf("\n** バケットソートの実行 **\n"); for (i = 0; i <= count - 2; i++) min_index = i; for (j = i + 1; j <= count - 1; j++) if (x[j] < x[min_index])min_index = j; swap = x[i]; x[i] = x[min_index]; x[min_index] = swap; void insertion_sort(int x[], int count) int i, j, y; printf("\n** 挿入ソートの実行 **\n"); for (i = 1; i < count; i++) y = x[i]; for (j = i; j > 0 && x[j - 1] > y; j--) x[j] = x[j - 1];

11 x[j] = y; プログラムの説明 for (i = 1; i < count; i++) で1 番目の数字から見るでyに移すy = x[i]; for (j = i; j > 0 && x[j - 1] > y; j--) x[j] = x[j - 1]; で挿入する位置を決める x[j] = y; で y を挿入する 課題 2 実行画面

12

13 保存されたデータ 追加したプログラム

14