最も速いソート方法であるクイックソート (アルゴリズムC 第1巻 p.133) について学びます。
(1) 次のように並んでいる数列を、 マージソートを用いてソートしなさい。 ただし、途中の過程も書くこと。
5 1 4 3 8 2 6 7
(2) 以下はクイックソートを行う関数と、それに対するコメント文である。
各コメントがプログラムのどの部分に対応するかを書きなさい。
(3) 次のように並んでいる数列を、(2) の関数で行っている処理と 同じようにして分割しなさい。
5 7 3 6 2 8 1
(1) マージソート
(アルゴリズムC 第1巻 p.185)
は、細かく分割して、それを並び直しながら
再び統合(マージ)していくソート方法です。
分割する分少し手間がかかって遅そうですが、
ソートされているもの同士を統合することは簡単にできます。
例えば次の図のようにソートされた二つの配列がある場合、
先頭同士を比べて、小さい方を取って並べてゆけばよいことになります。
下の図を参考にして、解いてみてください。
(2) クイックソートは、軸を適当に決めて軸の値より小さい方と 大きい方に分け(分割)、分けたものに対して再び同様のことをしていく方法です。 適当でもできてしまいそうですが、分割の方法を中心にプログラムをよく読んで 理解してください。
(3) 次の図を参考に、(2) での分割処理を実際の数字で確認してみてください。
クイックソートを行う関数を作りなさい。 プログラムは以下の条件を満たすこと。(ex09-2-skel.c)
まずはデータの個数を 10 個くらいにし、配列 a の内容を ソート前とソート後に表示して、うまく動いているかを確認してください。
演習第8回の問題3をやった人は、 シェルソートよりもどのくらい速いか確認してみてください。
教科書に載っている quicksort 関数には実は間違いがある。 データがある条件を満たしている場合は、 うまくソートすることができない可能性がある。 どのような条件のときにうまく動かないかを考え、 プログラムを修正しなさい。
教科書のままでも大抵の場合はうまく動いてしまいますが、 Segmentation Fault になる可能性もあります。