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

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

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

今日の課題: クイックソート[edit]

解答例?

課題1117-A （締切:11月17日，延長不可）[edit]

11月16日の演習問題を提出しチェックを受けて下さい．

課題1117-B （締切:11月24日）[edit]

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

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

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

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

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

• 分割の仕方がわかるようにするために，qs()の最初の方に

   printf("(%d %d)\n", first, last);

  とか書いてみませう
• 今までのソートの関数(SelectionSort()など)は，配列とデータの個数の二つを引数とする仕様となっていましたが，課題1110-Aで書いた関数 qs() は再帰呼び出しをする都合で，異なる引数の与え方をするようになっています．この食い違いを解消するために，qs()とは別にもう一つ

  void QuickSort(配列，データの個数)
  {
    qs()を呼ぶ
  }

  という関数QuickSort()も作って，mainからはこちらを呼ぶようにしましょう

課題1117-C （締切:11月24日，1117-A,Bを11月17日に提出した人のみ対象のボーナス課題）[edit]

上記 qs() では何度も再帰呼び出しを繰り返すため効率がよくありません．そこで，並べかえ対象が5個以下になったら単純選択法に切り替えるように工夫してみてください．課題1117-Bのソースをコピーしてquicksort2.cを作り，これを修正しましょう．