Double型ソート方法

締切済

質問者：xxxsinxxx
質問日時：2007/10/06 16:34
回答数：4件

お世話になります。
VB初心者ですが宜しくお願いします。
ソートについてなのですが、Double型の配列(要素数8191)をソートしたいのですが処理が早いソート方法はあるのでしょうか。
クイックソートで試してみたのですがスタック領域が不足しています。
とのエラーメッセージが表示され処理が停止します。
スタック領域を消費しないソート方法などあればご教授宜しくお願いします。

通報する

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

質問の本文を隠す

回答 (4件)

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

No.4

回答者： a-saitoh
回答日時：2007/10/06 22:14

クイックソートは自作ですか？

プログラムを間違えているからスタックが不足するのでしょう。
再帰呼び出しの際に、ソート対象のデータのコピーを渡しているとか。

クイックソートはインプレースソートなので、8191要素くらいでスタックが足りなくなることは考えにくいです。

- 0
- 件

通報する

No.3

回答者： imogasi
回答日時：2007/10/06 20:47

＃１で示唆されている、再帰型（リカーシブな）のアルゴリスムを使っているからだと思います。

http://e-words.jp/w/E383AAE382ABE383BCE382B7E383 …
http://www.geocities.jp/kmctecyh/k_gozen/gozen03 …
にあるように
「リカーシブは、プログラムの中から自分自身を呼び出すことを言う。自分自身を定義するの
に自分自身よりも１次低い集合を用いる。その部分集合はより低次の部分定義を用いて定義する
ことを繰り返して表現する。
クィックソートは、適当にサンプリングして得られたデータＮに着目し、Ｎ以下のデータ系
列とＮ以上のデータ系列に分割する。このデータＮを軸(ピボット)という。データＮを軸とし
て、その軸の値より小さい要素は軸より前方へ、大きな要素は軸より後方へ振り分ける。適当な
長さの系列になるまで分割を繰り返し、それぞれの系列をソートすれば１つのソート済み系列と
なる。
分割の繰返しに再帰呼び出し(リカーシブ)を利用した高速の整列法である。」
ーーー
質問者がどこかで見たアルゴリズムがリカーシブなものであったのでしょう。理系の先生のクイックソートの記述には、これが多そう。
しかしすぐ質問のような事態になるでしょう。戻った時の情報を
蓄えていかないとならないから。
どこか再帰を使わないクイックソートのアルゴリズムを見つけるしかないでしょう。
http://edu.inf.shizuoka.ac.jp/lecture/2007/X121/ …
に考え方とC言語の簡単例がある。
「再帰的でない　クイックソート」などでWEB照会しては。