プログラミングおよび実習II/20061013

[ 高橋のページ ] [ プログラミングおよび実習II2006? ]

プログラミングおよび実習II 2006年10月13日 †[edit]

今日の課題: バブルソートによる並べかえのプログラム †[edit]

テストの得点を表すデータがいくつか与えられたときに，

1. それらを配列に格納する
2. それらを昇順にバブルソートする
3. できた配列の内容を表示する

というプログラムを作りましよう．前回同様に，

• データは整数，データ件数は最大50
• はじめにデータ件数を入力し，次に各データを順番に入力する

こととします．

課題1013-A（締切： 今日の実習開始後すぐ，締切後チェック対象外） †[edit]

• 10月12日の演習問題のプリントを提出し，チェックを受けてください．

課題1013-B（締切： 今日の実習終了時） †[edit]

• 課題Aを元にしてプログラムを完成させ，動作を確認しましょう．
• 作成するソースファイル名は bubblesort.c として下さい．
• 以下のことに注意してください．
  • 前回の selectionsort1.c などを流用すると楽でしょう．
  • 前回でてきた関数 PrintData() を使い，元のデータ，並べかえ途中の様子，結果，を出力するようにしてください．並べかえ途中の様子を表示するには，第iステップの作業終了後に PrintData() を呼ぶようにしたらよいです．

課題1013-C（おまけ，締切： 今日の実習終了時，締切後チェック対象外） †[edit]

• これはおまけ課題です．課題Bができた人が対象です．やらなくても実習成績の減点はありませんが，やると加点があるでしょう．
• 講義中に説明した改良法（途中のステップで交換が一度も起こらなかったら処理を打ち切る）を実現したプログラムを作成し，動作を確認してください．
• 課題Bの bubblesort.c の中に，このような改良を施した関数 BubbleSort2() を追加して， main() からそれを呼ぶようにしたらよいでしょう．

課題1013-D（さらにおまけ，締切： 来週の実習開始後すぐ，締切後チェック対象外） †[edit]

• これはおまけ課題です．課題Cができた人が対象です．やらなくても実習成績の減点はありませんが，やると加点があるでしょう．
• 以下のアイデアをもとに，さらなる改良を施しましょう
• 改良した関数の名前は BubbleSort3 としましょう．

＜ステップ0の途中＞
  0     1     2     3     4     5     6     7     8     9
[  1] [  2] [  3] [  4] [  5] [  8] [  6] [  7] [  9] [ 10]
                                 o(^-^)o

このようなデータの場合，j = 6 のときに5番目と6番目が交換されて

＜ステップ0終了時＞
  0     1     2     3     4     5     6     7     8     9
[  1] [  2] [  3] [  4] [  5] [  6] [  8] [  7] [  9] [ 10]
↑確

となった後は，第 i = 0 ステップの処理では一度も交換がおこりません．ということは，実は，この第0ステップ終了時点では，0番目が確定できるだけではなく，1番目から5番目までもソート済みとして確定できることになります．

したがって，次に第 i = 1 ステップに進むのではなく，i = 1から5までのステップを飛ばして，次はいきなり第 i = 6 ステップに進むことができます．

＜ステップ6の途中＞
 0     1     2     3     4     5     6     7     8     9
[  1] [  2] [  3] [  4] [  5] [  6] [  8] [  7] [  9] [ 10]
↑確  ↑確  ↑確  ↑確  ↑確  ↑確    o(^-^)o

そして，第7ステップでは一度も交換がおこらないので，（改良第1弾によって）このステップを終了した時点で処理を終えられることになります．

以下のような方針で考えるとよい鴨

• 第iステップで最後に交換が起こった場所を覚えておく
• 次のステップに進むときには，iを一つ増やすのではなく…
• iのループはfor文よりwhile文の方がわかりやすい鴨

おまけ †[edit]

ひつこくおまけ

PrintDataBubble()をさらに改造するなら…

--- step 5 ---
 [  1] [  2] [  3] [  4] [  5] [  7] [  6] [  8] [  9] [ 10]
  ***   ***   ***   ***   ***          o(^-^)o
--- step 5 ---
 [  1] [  2] [  3] [  4] [  5] [  7] [  6] [  8] [  9] [ 10]
  ***   ***   ***   ***   ***    o(>_<)o
--- step 6 ---
 [  1] [  2] [  3] [  4] [  5] [  6] [  7] [  8] [  9] [ 10]
  ***   ***   ***   ***   ***   ***                o(^-^)o