HSPポータル
サイトマップ お問い合わせ


HSPTV!掲示板


未解決 解決 停止 削除要請

2007
1231
ます再起処理の書き直し3解決


ます

リンク

2007/12/31(Mon) 17:41:09|NO.12961

ゲーム作成にクイックソートを使おうと思い、
http://hspdev-wiki.net/?Sort%2FQuick
を使うことにしたのですが、配列の要素数が多いとスタック領域のオーバーフローが起きてしまいます。
そこで、下記のように再起処理を使わないのうに書き直したのですがstartIndexとendIndexの値がおかしいようで、エラーが出てしまいます。
どこを直せば正しく動作するでしょうか?

#module QuickSortSample // 配列変数の入れ替え target(i1) ⇔ target(i2) #deffunc qsExchange array target, int i1, int i2, local tmp tmp = target(i1) : target(i1) = target(i2) : target(i2) = tmp return #const stackMax 2000 // 再帰用命令(内部利用) #deffunc qsArgo array target, int startIndex_, int endIndex_, local std, local lastExchangedIndex dim startIndexes,stackMax dim endIndexes,stackMax dim shoribasho,stackMax stackIndex=0 startIndexes(0)=startIndex_ endIndexes(0)=endIndex_ shoribasho(0)=0 shorinext = 0 ;1なら1回目のqsArgo飛ばし 2なら2回目も飛ばし repeat startIndex=startIndexes(stackIndex) endIndex=endIndexes(stackIndex) std = target(startIndex) // 基準値(簡単のために一番端の要素を選択) lastExchangedIndex = startIndex // 最後に基準値より小さい値を格納した要素 stackIndex++ if shorinext=0{ // 基準値よりも小さい値をひとまとまりにする repeat endIndex - startIndex, startIndex + 1 if target(cnt) < std { // 降順にしたい場合はここを変更する lastExchangedIndex++ qsExchange target, lastExchangedIndex, cnt } loop if startIndex < lastExchangedIndex { // 基準値よりも小さい数値を格納した要素があった qsExchange target, startIndex, lastExchangedIndex // 基準値を正しい位置に移動 if startIndex < lastExchangedIndex - 1 { // 基準値よりも小さい値が複数ある場合、それらに対して再帰的にソートを実行 // qsArgo target, startIndex, lastExchangedIndex - 1,jun startIndexes(stackIndex) = startIndex endIndex(stackIndex) = lastExchangedIndex-1 shoribasho(stackIndex)=1 shorinext=0 continue } } } if shorinext!2{ if lastExchangedIndex < length(target) - 2 { // 基準値よりも大きい値が複数ある場合、それらに対して再帰的にソートを実行 // qsArgo target, lastExchangedIndex + 1, length(target) - 1,jun startIndexes(stackIndex) = lastExchangedIndex + 1 endIndexes(stackIndex) = length(target)-1 shoribasho(stackIndex)=2 shorinext=0 continue } } if cnt=0:break shorinext = shoribasho(stackIndex) stackIndex-- continue cnt-1 loop return #deffunc qSort array target qsArgo target, 0, length(target) - 1 return #global // 以下 動作確認用サンプル randomize s = "ソート前:" dim test, 100 repeat length(test) test(cnt) = rnd(1000) s += str(test(cnt)) + ", " loop mes s qSort test s = "ソート後:" repeat length(test) s += str(test(cnt)) + ", " m += str(jun(cnt)) + ", " loop mes s stop



この記事に返信する


f

リンク

2008/1/1(Tue) 20:59:47|NO.12985

放置も良くなさそうなので一応。

とりあえずアルゴリズムの勉強でなくて、結果が欲しいだけなら、
ANTARES氏のサイトにサンプルあるので行って見れ。

2.6仕様だが、再帰の処理をしない処理に直すより簡単でね。
モジュール化も、やろうと思えば出来るだろう。

ANTARES氏は帰省中?



naznyark

リンク

2008/1/2(Wed) 03:06:41|NO.12992

直接の回答ではないですが上記の開発wikiのページ
http://hspdev-wiki.net/?Sort%2FQuick
非再帰版のクイックソートのモジュールをアップしました。



ます

リンク

2008/1/2(Wed) 10:41:15|NO.12994

皆さん、ありがとうございました。
とりあえず、ソートできるようにならないことには進まないので
naznyarkさんの非回帰版を使わせていただきます。
fさんに紹介して頂いたANTARESさんのサイトもとても参考になりました。
いずれ、自分でも非回帰版を作れるようになりたいと思います。



ONION software Copyright 1997-2021(c) All rights reserved.