アルゴリズムとデータ構造
演習第 9 回
ソート2(最速のソート)

最も速いソート方法であるクイックソート (アルゴリズムC 第1巻 p.133) について学びます。

問題1印刷用 PostScript

(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) での分割処理を実際の数字で確認してみてください。
クイックソートの分割

問題2

クイックソートを行う関数を作りなさい。 プログラムは以下の条件を満たすこと。(ex09-2-skel.c

まずはデータの個数を 10 個くらいにし、配列 a の内容を ソート前とソート後に表示して、うまく動いているかを確認してください。

演習第8回の問題3をやった人は、 シェルソートよりもどのくらい速いか確認してみてください。

問題3

教科書に載っている quicksort 関数には実は間違いがある。 データがある条件を満たしている場合は、 うまくソートすることができない可能性がある。 どのような条件のときにうまく動かないかを考え、 プログラムを修正しなさい。

教科書のままでも大抵の場合はうまく動いてしまいますが、 Segmentation Fault になる可能性もあります。


Written by わかまつなおき