クイックソート

クイックソートには再帰を使わない方がいいんですか？
再帰を使わないとすると明示的にスタックで管理することになると思うのですが，整列させたい要素数がバラバラの時はどのようにすればよいですか？

No.2 ベストアンサー 回答者： a-kuma 回答日時： 2002/04/25 10:02

> クイックソートには再帰を使わない方がいいんですか？

もともと再帰的な考え方なので、無理に再帰を使わない、というメリットはあまり無い、と
思います。

一昔前のコンピュータでは、関数の呼び出しにかかる時間でさえ惜しいので、非再帰の
アルゴリズムも考えられていますけど。

逆にいうと、VB では関数やサブルーチン呼び出しにはかなりのコストがかかる(*)ので
あれば、非再帰のアルゴリズムを使うこともあり、かな。

　　(*) 私は、VB嫌いなんで、よく知りません

> 再帰を使わないとすると明示的にスタックで管理することになると思うのですが，
> 整列させたい要素数がバラバラの時はどのようにすればよいですか？

大きめに持っておくか、動的に（実行時に）確保するしかありません。

大きめに、と言っても log2(要素数)くらいの大きさで良いのですから、さして気にする
こともないでしょう。

VB って、配列のサイズを実行時に決められないんですか？
別に配列じゃなくても、整数が保持できる「コレクション（って言うんだっけ？）」でも良いんですけど。

＃ すいません、VB 知らなくて

No.3 回答者： terra5 回答日時： 2002/04/25 12:36

再帰呼び出しが可能な言語なら、

作りやすさの点で再帰を選ぶのがいいと思いますが。

関数呼び出しのオーバーヘッド等が問題になることもありますが、
まれなケースでしょう。

あと、かってに使われるスタックサイズ等が問題になるケースもあるかも知れませんが、
これも特殊なケースでしょう。


昔のBASIC,FORTRAN等では局所的な自動変数はない、
再帰呼び出しは許されていない等で、
非再帰にするしかなかったですけど(^^;;

No.1 回答者： josyo_m 回答日時： 2002/04/25 09:59

お疲れ様です。

下記のＵＲＬにサンプルが載っていました。

間違っていたらごめんなさい。

参考URL：http://www.geocities.co.jp/SilkRoad/4511/vb/sort …