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

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

プログラミングおよび実習II 2005年10月20日[edit]

今日の課題: 単純交換法(バブルソート)によるデータの並べかえ[edit]

解答例?

課題1020-A (締切:10月20日,延長不可)[edit]

10月19日の講義資料の演習問題(バブルソートの関数を紙に書く)を提出してください.

課題1020-B(締切:10月27日)[edit]

整数のデータが与えられたときに,

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

というプログラムを作りましよう.名前は bubblesort.c としてください. これまでの score1.c などと同様に,

  • データの数は最大100個
  • まずデータの数を入力し,次に各データを順番に入力する

こととします.ただし,以下のことに気をつけて作成して下さい.

  • 配列の中身の表示には,前回でてきた関数 PrintData2() を使う
  • データの並べかえには,課題1020-Aで紙に書いた関数 BubbleSort() を使う.ただし,関数中の適当なところで PrintData2() を呼ぶ(おまけに示した PrintDataBubble() でもよいです)ようにして,並べかえの途中経過がわかるようにして下さい.

課題1020-C (締切:10月27日,課題1020-Bを10月20日に提出した人のみ対象のボーナス課題,延長不可)[edit]

  • 講義中に説明した改良法(途中の段階で交換が一度も起こらなかったら処理を打ち切る)を実現したプログラムを作成し,動作を確認してください.

改良した関数の名前は BubbleSort2,プログラムのファイル名は bubblesort2.c としましょう.

課題1020-D (締切:10月27日,課題1020-Cのチェックを受けた人のみ対象のボーナス課題,延長不可)[edit]

以下のアイデアをもとに,さらなる改良を施しましょう

  0     1     2     3     4     5     6     7     8     9
[ 10] [  9] [  8] [  7] [  6] [  5] [  3] [  4] [  2] [  1]
                                      o(^-^)o

このようなデータの場合,第 i = 0 段階の処理では,j = 7 のときに7番目と6番目が交換されて

  0     1     2     3     4     5     6     7     8     9
[ 10] [  9] [  8] [  7] [  6] [  5] [  4] [  3] [  2] [  1]
<--------------------------------------->

となった後は,一度も交換がおこりません.ということは,実は,この第0段階終了時点では,0番目が確定できるだけではなく,1番目から6番目までもソート済みとして確定できることになります.

したがって,i = 1から6までの段階を飛ばして,次はいきなり第 i = 7 段階に進むことができます.そして,第7段階では一度も交換がおこらないので,この段階を終了した時点で処理を終えられる(改良第1弾)ことになります.

改良した関数の名前は BubbleSort3,プログラムのファイル名は bubblesort3.c としましょう.

おまけ[edit]

http://tortoise1.math.ryukoku.ac.jp/~takataka/course2005/prog2/PrintDataBubble.png

ポインタについて復習しよう[edit]

こちらをどうぞ: 「ポインタの話


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2014-08-13 (水) 13:45:19 (1770d)