バブルソート・選択ソート・マージソート

この演習では、基本的なソートについて学び、各手法をC言語で実装する方法について学びます。

問題の難易度の目安【易】⭐ 【標準】⭐⭐【難】⭐⭐⭐

アルゴリズム論Iを取ってない人は、以下の動画を参考にされるといいでしょう。 他にも動画はあると思うので、自分にあった動画を探してみてください。

• バブルソート
• 選択ソート
• マージソート

問題1 ⭐

指定された2つのインデックスの要素の大小関係を表示するプログラムを完成させましょう。

./a.out 1 3 7 5 1 2 8 3

と入力すると、

7 5 1 2 8 3
  x   x
-> Greater

という表示になります（5は2より大きいので）．

最初の2つの数字が入れ替える２つのインデックスを表し、それ以降を配列として考えます。

大きい場合はGreater，小さい場合はLess，等しい場合はEqualと表示します．

なお，入力するインデックスの順番が変わると結果も変わります．

./a.out 3 1 7 5 1 2 8 3

というコマンドを入力すると，

7 5 1 2 8 3
  x   x
-> Less

という表示になります（2は5より小さい）。

問題2 ⭐

指定された2つのインデックスの要素を入れ替えるように、プログラムを完成させましょう。

./a.out 1 3 7 5 1 2 8 3

と入力すると、

7 5 1 2 8 3
  x   x
7 2 1 5 8 3

という表示になります。

最初の2つの数字が入れ替える２つのインデックスを表し、それ以降を配列として考えます。

1番目と3番目の要素が入れ替わっているのがわかるでしょう。

Note

配列の中身を入れ替える。メモリのイメージをしっかりと。

問題3 ⭐⭐

バブルソートをするプログラムを作ってみましょう。 配列の要素の入れ替えるが起きるたびに、配列を表示してください。

./a.out 7 5 1 2 8 3

と入力して、実行すると

7 5 1 2 8 3
7 5 1 2 3 8
7 1 5 2 3 8
1 7 5 2 3 8
1 7 2 5 3 8
1 2 7 5 3 8
1 2 7 3 5 8
1 2 3 7 5 8
1 2 3 5 7 8

と表示されます。

プログラムが動作するように、プログラムを完成させましょう！

Note

バブルソートについて学びます。

問題4 ⭐⭐

選択ソートをするプログラムを作ってみましょう。 swap関数が終わったあとに、配列を表示してください。

./a.out 7 5 1 2 8 3

と入力して、実行すると

7 5 1 2 8 3
1 5 7 2 8 3
1 2 7 5 8 3
1 2 3 5 8 7
1 2 3 5 8 7
1 2 3 5 7 8

と表示されます。

プログラムが動作するように、プログラムを完成させましょう！

Note

選択ソートについて学びます。 バブルソートより入れ替えの回数が少ないことに気づきましょう。

問題5 ⭐⭐

配列のインデックスが3つ（p、q、r）与えられたとします。 このとき、pからq、q + 1からrの要素を表示するプログラムを作りましょう。

./a.out  2 3 6 1 2 3 4 5 6 7 8

と入力して、実行すると

3 4
5 6 7

と表示されます。

プログラムへ与えられる最初の数字3つがインデックスとして使われ、残りが配列として与えれます。 この例の場合は、p = 2, q = 3, r = 6となります。 配列のインデックスは0からはじまっていることに注意しましょう。

問題6 ⭐⭐

与えられた2つの配列を結合した新しい配列を作るプログラムを作りましょう。

./a.out 1 2 3 / 4 5

と入力すると、

1 2 3
4 5
1 2 3 4 5

と表示されます。

プログラムに与える引数は、/ で2つの配列に分けられています。

プログラムが動作するように、プログラムを完成させましょう。

問題7 ⭐⭐

配列の最後にINT_MAXを追加するプログラムを作りましょう。

./a.out 11 45 141 919

と入力すると、

11 45 141 919
11 45 141 919 2147483647

と表示されます。

2147483647 は int型の最大値です。limits.hで定義されています。

プログラムが動作するように，プログラムを完成させましょう．

Note

INT_MAXはコンパイルされる際にint型の最大値に置き換えられるため，数値と同じように扱って大丈夫です。 たとえば，int a = INT_MAXと書けます。

問題8 ⭐⭐⭐

プログラムは，2つの配列の要素を比較し，小さい方から新しい配列に代入し，表示するプログラムです．

./a.out  1 3 5 7 9 / 2 4 6 8

と入力すると

1 2 3 4 5 6 7 8 9

と表示されるはずです。

プログラムが動作するように，プログラムを完成させましょう．

問題9 ⭐⭐⭐

手続きMergeのアルゴリズムにしたがって，プログラムを完成させましょう。

./a.out 15 17 13 10 12 19 16

と入力すると

実行すれば，

15 17 13 10 12 19 16
12 15 17 13 10 19 16

と表示されるはずです。

Note

授業で習った，手続きMergeについて学ぶ．

問題10 ⭐⭐⭐

Merge Sortのアルゴリズムにしたがって，プログラムを完成させましょう。

実行すると、

4 2 30 6 40 50 20 5
2 4 5 6 20 30 40 50

と表示するはずです。

Note

授業で習った，Merge Sortについて学ぶ。