クイックソート・計数ソート・基数ソート・シェルソート
この演習では、クイックソートと様々なソートについて学び、各手法をC言語で実装する方法について学びます。
問題の難易度の目安【易】⭐ 【標準】⭐⭐【難】⭐⭐⭐
こちらの動画が参考になると思います。
問題1⭐⭐
Partitionのアルゴリズムにしたがって，以下のプログラムを完成させましょう．
./a.out 2 8 7 1 3 5 6 4
と実行すれば、
2 8 7 1 3 5 6 4
pivot = 3
2 1 3 4 7 5 6 8
と表示されます。
Note
授業で習った，Partitionについて学習します。
問題2⭐⭐
Quicksortのアルゴリズムにしたがって、以下のプログラムを完成させましょう。
./a.out 2 8 7 1 3 5 6 4
と実行すれば、
2 8 7 1 3 5 6 4
1 2 3 4 5 6 7 8
と表示されます。
Note
授業で習った，Quick Sortについて学ぶ。
問題3⭐
中央値を求めるプログラムを完成させましょう。
./a.out 2 8 7 1 3 5 6 4
と実行すれば、
median 4.50
と表示されます。
Note
入力されるデータはソートされてないので、ソートしてからやると楽です。
問題4⭐⭐
配列中の重複する値を消し、ソートして表示するプログラムを完成させましょう。
./a.out 3 4 1 2 1 3 5 3 2 1 4 5 6
と実行すれば、
3 4 1 2 1 3 5 3 2 1 4 5 6
1 2 3 4 5 6
と表示されます。
1つ目の表示が与えられた配列で、2目の表示が重複のない配列となります。 配列の表示にはprint_ary関数を使いましょう。
問題5⭐
文字列をソートするプログラムを作成しましょう。
./a.out holomico
と実行すると、
chilmooo
と表示されます。
問題6⭐
フィボナッチ数列の配列での実装にしたがって，プログラムを完成させましょう。
./a.out 10
実行すれば，
fib(10) = 55
と表示されます。
Note
資料とは異なり，f[0] = 0; f[1] = 1;と考えてください。
問題7⭐⭐
計数ソートのアルゴリズムにしたがって，以下のプログラムを完成させなさい．
./a.out 6 5 3 0 2 3 0 3
と実行すれば、
5 3 0 2 3 0 3
0 0 2 3 3 3 5
と表示されます。
入力する最初の値は数列の範囲指定で、それ以降が数列になります。 数列に含まれている数字より小さい数字を範囲指定とすると，おかしくなります。
Note
授業で習った計数ソートの学習
問題8⭐⭐
このプログラムは，指定した桁の数で計数ソートを行うプログラムです。
./a.out 2 329 457 657 839 436 720 355
と、指定する桁を3（百の桁）として入力すると、
329 457 657 839 436 720 355
329 355 457 436 657 720 839
となり、
指定する桁を2（十の桁）で実行すれば、
329 457 657 839 436 720 355
329 720 839 436 457 657 355
と表示されます。
Note
基数ソートを作る一歩手前の実装について学ぶ．
問題9⭐⭐
基数ソートのアルゴリズムにしたがって， 以下のプログラムを完成させましょう。
./a.out 329 457 657 839 436 720 355
と実行すれば、
329 457 657 839 436 720 355
720 355 436 457 657 329 839
720 329 436 839 355 457 657
329 355 436 457 657 720 839
と、それぞれの桁でソートされた結果を表示するようにしましょう。
Note
授業で習った，基数ソートについて学ぶ．
問題10⭐
シェルソートのアルゴリズムにしたがって、 以下のプログラムを完成させましょう。
./a.out 58 12 39 90 49 26 68 47 15 39
と実行すれば、
58 12 39 90 49 26 68 47 15 39
39 12 15 58 47 26 68 49 39 90
15 12 39 26 39 49 47 58 68 90
12 15 26 39 39 47 49 58 68 90
と表示されます。
Note
授業で習った，シェルソートについて学ぶ．