クイックソート

解決済

質問者：ijiri
質問日時：2002/04/25 09:40
回答数：3件

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

通報する

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

質問の本文を隠す

回答 (3件)

ベストアンサー優先
最新から表示
回答順に表示

No.2ベストアンサー

回答者： a-kuma
回答日時：2002/04/25 10:02

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

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

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

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

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

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

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

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

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

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

- 0
- 件

通報する

No.3

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

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

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

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

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

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