クイックソートでソート数が１個や２個でも正しくソートできるのでしょうか？

締切済

質問者：mihck
質問日時：2009/04/28 05:32
回答数：4件

使用上意味がないのですが、クイックソートでソート数が１個や２個でも正しくソートできるのでしょうか？

引数に quick_sort( a[], 0, n - 1 )と、n-1となっているために
nは0は無理そうですが、n=1なら0でうまくいくかなと思うのですが、
原理上、どうなっているのでしょうか？
詳しい方教えて下さい。

http://www.daccho-it.com/program/algo/quick.c

通報する

この質問への回答は締め切られました。

質問の本文を隠す

回答 (4件)

最新から表示
回答順に表示

No.1

回答者： kt1965
回答日時：2009/04/28 06:27

回答します。

残念ですが、1ではうまくいかないと思います。なぜならば、クィックソートの原理は、適当な数を選び、それで元配列を分割する。そのとき、適当な数が、元配列の半分になる値を選ぶ。選んだ数より小さいものを配列の前半に、選んだ数より大きいものを配列の後半に集める。入れるの前半が、長さ２以上ならば、配列の前半をクィックソートする。配列の後半が、長さ２以上ならば、配列の後半をクィックソートする。

こんな感じで、再帰的にクィックソートそのものを繰り返しながら整列させるプログラムです。

よって、条件によっては、最速になるし、最悪の場合には配列数の二乗になります。

詳しいことは、
*奥村晴彦、Ｃ言語によるアルゴリズム辞典、技術評論社、pp.55-57
*Donald E. Kunuth, The Art of Computer Programming -Vol.3-, Addison Wesley, pp.168-

では。

- 0
- 件

通報する

No.2

回答者： stomachman
回答日時：2009/04/28 11:00

　最も端的に原理を記述すると、要素数nが1どころか0でも旨く行く。

しかし、旨く行かない実装もありうるから、ご質問の場合にはやってみちゃくちゃ分かりません。（それをバグと呼ぶかどうかは、その実装の説明書き（仕様）の書きようで決まります。）

　ソートとは、与えられた一群のデータを集合とみなし、その要素xについて定義されたキー関数kの値k(x)が小さい順に要素を配列すること。クィックソートの原理は

(1) 与えられた集合Xが空のとき、長さ0の配列を返す。
(2) そうでないとき、Xのどれかの要素xを勝手に選び、それで元の集合Xを分割する。x以外の要素yについて、yのキーk(y)がk(x)より小さいものの集合Sと、k(y)がk(x)より大きいものの集合Lと、k(y)=k(x)であるものを勝手に並べた配列Bを作る。そして、SとLをクィックソートして作った配列をA, Cとするとき、Aの後ろにBを並べ、その後ろにCを並べた配列を返す。

ということです。従って、(2)で作るSやLの要素数が1や0であることもあり、その場合にもクィックソートは呼び出される。なので、要素数1や0でも正しく働かないと成り立ちません。

　実装に於いては、(2)の「そして、SとLをクィックソートして作った配列をA, Cとする」の部分について、

「SやLの要素数が0である場合には、わざわざクィックソートを呼び出さなくなって、(1)より、答は長さ0の配列に決まっている。」

ということを使って、(2)の中で条件分岐をすることで「SやLの要素数が0である場合にクィックソートを呼び出す」という手間を減らすことができる。もちろんこれでも正しい実装である。

　で、そういう形で実装すると、(2)の中からクィックソートを呼ぶ際に渡す引数（SやL）は空ではないに決まっている。なので、じゃあ(1)の判定は無駄じゃないか。そこで(1)を削除すると、これはクィックソートの原理からちょっと外れた実装です。なぜならXが空の時に正しく働かなくなってしまう。
　「空の集合をソートすることなんて絶対ないよ」と言える状況ならそれでも構わない。逆に、「クィックソートを呼び出すかどうか判別するために、いちいち空かどうかテストして分岐するなんてクダラナイ手間は掛けたくない」という状況なら、本来のクィックソートを実装すべきです。ま、普通は後者でしょう。