[ [[高橋のページ:http://tortoise1.math.ryukoku.ac.jp/~takataka/index-j.html]] ]
[ [[プログラミングおよび実習II2006]] ]
*プログラミングおよび実習II 2006年10月13日 [#v5b5d76d]
#contents
**今日の課題: バブルソートによる並べかえのプログラム [#a292e5de]
テストの得点を表すデータがいくつか与えられたときに,
+それらを配列に格納する
+それらを昇順にバブルソートする
+できた配列の内容を表示する
というプログラムを作りましよう.前回同様に,
-データは整数,データ件数は最大50
-はじめにデータ件数を入力し,次に各データを順番に入力する
こととします.
***課題1013-A(締切: 今日の実習開始後すぐ,締切後チェック対象外) [#r14ff2dc]
-10月12日の演習問題のプリントを提出し,チェックを受けてください.
***課題1013-B(締切: 今日の実習終了時)[#t4fd0fbc]
-課題Aを元にしてプログラムを完成させ,動作を確認しましょう.
-作成するソースファイル名は bubblesort.c として下さい.
-以下のことに注意してください.
--前回の selectionsort1.c などを流用すると楽でしょう.
--前回でてきた関数 PrintData() を使い,元のデータ,並べかえ途中の様子,結果,を出力するようにしてください.並べかえ途中の様子を表示するには,第iステップの作業終了後に PrintData() を呼ぶようにしたらよいです.
***課題1013-C(おまけ,締切: 今日の実習終了時,締切後チェック対象外) [#t4fd0fbc]
-これはおまけ課題です.課題Bができた人が対象です.やらなくても実習成績の減点はありませんが,やると加点があるでしょう.
-講義中に説明した改良法(途中のステップで交換が一度も起こらなかったら処理を打ち切る)を実現したプログラムを作成し,動作を確認してください.
-課題Bの bubblesort.c の中に,このような改良を施した関数 BubbleSort2() を追加して, main() からそれを呼ぶようにしたらよいでしょう.
***課題1013-D(さらにおまけ,締切: 来週の実習開始後すぐ,締切後チェック対象外) [#t4fd0fbc]
-これはおまけ課題です.課題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文の方がわかりやすい鴨
***おまけ [#kaabd933]
http://tortoise1.math.ryukoku.ac.jp/~takataka/course2006/prog2/PrintDataBubble.png
ひつこくおまけ
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