ソートについて（その他質問あります）

質問

こんにちわ。Ｃプログラム初心者の学生です。
友達のプログラムについての質問なので詳しくは説明できませんが、よろしくお願いします。
ソートのプログラム（いろいろなソート）を作ったのですが、ソートする範囲を6万以上（0～59999）にすると必ずエラーが出てプログラムが終了してしまいます。
最終的には10万以上の値をソートしたいのですが、エラーが出て困っています。
値の生成についてはランダムで、配列に格納してやるという形にしています。
やはり、配列数が0万以上はサポートしていないのか、メモリの問題でしょうか？

これは私の質問ですが、処理の高速化についてアドバイスいただきたいです。私が知ってるのは、掛け算割り算はあまり使わない、なるべく値の受け渡しはポインタを使った方がいい・・・という程度です。
あとこれから初心者Ｃプログラマとしてステップアップしていくために重要なこととかあれば教えて下さい。
ちなみに今はＭＦＣについて少し勉強しています。

まとまりの無い文になってしまいましたが、よろしくお願いします。

回答No.2

MovingWalk · ベストアンサー

配列変数をAUTO変数として宣言していませんか？
main()
{
int array[100000];
．．．．
}
AUTO変数はスタックという特別なメモリ領域にとられるため、大きなサイズを
確保すると不足する場合があります。下記のようにしてみてください。
static int array[100000];

尚、通常大きなサイズの変数を利用するときは、malloc()関数を使って
領域を確保します。説明は省略しますので、調べてみてください。

以下に、参考URLを載せておきます。参考にしてください。
http://www.pro.or.jp/~fuji/mybooks/cpro/cpro.4.5.2.html
http://ecoeng.im.kindai.ac.jp/c/
http://homepage1.nifty.com/toshio-k/prog/c/

お礼

回答ありがとうございます。
なるほど。static変数で宣言するとは気づきませんでした。
でも、スタック（後入れ先だしですよね？）というメモリ領域ではなぜ不足するのか・・・。もし知っていればご回答下さい。（初心者的な質問ですいません）
私も、malloc()関数で領域を確保してみればと友達に言ったのですが、なんか難しそうといって敬遠していました。
私自身も勉強しないとダメですね・・（笑）
有難うございました。また何かあれば質問させていただきますので、その時はよろしくお願いします！！

回答No.4

MovingWalk

＃２です。

VCがどうなのかは知りませんが、あくまでも一般論です。
プログラムのメモリ配置は、こちらに書かれているようになります。
http://www1.cts.ne.jp/~clab/hsample/Point/Point19.html

このうち、スタックサイズは通常リンク時に指定されたサイズとなります。
そしてスタックは、関数の戻り番地や引数、AUTO変数などに使われます。
ですから、AUTO変数のサイズを多くとったり、関数呼び出しのネスティングが
深くなると、スタックを消費して「スタックオーバフロー」になることが
あります。クイックソートなどの再起呼び出しを行う処理では、
このネスティングが深くなるのでその可能性が高くなります。
AUTO変数の配列だけのせいだけではなく、このことも一因かもしれませんね。

参考URL：

http://www1.cts.ne.jp/~clab/hsample/Point/Point19.html

お礼

またまたご回答有難うございますｍ（＿＿）ｍ
初心者にとったらまだ難しい内容ですが、なんとなくですがわかりました。
本当に助かりました。
初心者から脱却するために精進します。
また何かありましたらよろしくお願いします。

回答No.3

toysmith

環境に関する記述がいっさい無いので答えにくいのですが…
MFCとの記述があるので、32ビット系WindowsOSを想定します。
16ビット版MFCなんてことはないですよね？

> エラーが出て困っています
実行時エラーですか？コンパイル／リンクエラーですか？
ソート対象のデータは静的な配列ですか？動的メモリブロックを配列として参照しているのですか？
ソート対象データは一括して処理しているのですか？部分ソートを繰り返しているのですか？
そもそも、OSとコンパイラは何ですか？
ソート対象データの型は？

> 処理の高速化についてアドバイスいただきたいです
> なるべく値の受け渡しはポインタを使った方がいい
コンパイラの最適化が有効に機能するようにトリッキーなコードを書かない。
かけ算／割り算をさけるためにトリッキーなコードを書いてしまったら最適化が有効に機能しないことがあります。
素直に、シンプルに、定石通りに書いたプログラムが結局早く実行されます。

> 初心者Ｃプログラマとしてステップアップしていくために重要なこと
素直にアルゴリズムを記述することが第一歩です。
Cのコードでどんなにがんばってもアセンブラ高速アルゴリズムを使ってで書いたコードより速くすることはできません。
どんなにがんばってトリッキーなコードを書いても設計段階で高速化を意識したプログラムには勝てません。
CPUのクロックがGHzを超えているような時代に数クロック速くするためにトリッキーなコードを書くのはナンセンスです。

お礼

すいません・・。環境の記述は必須ですよね。
WindowsOS、コンパイラはＶＣ6.0、実行時のエラー、ＡＵＴＯ変数で動的、その他は友達の作ったプログラムをじっくり見てみないと分かりません。
処理の高速化についてですが、無理にトリッキーなコードを書く必要はないんですね。コンパイラの最適化を阻害してしまいかねない、ってことですよね。
ＳＥを目指す者として、勉強を重ねないとダメですね。
ほんと初心者的な質問を詳しく回答していただいて有難うございました。

回答No.1

ymmasayan

ソートで考えられるのは配列の添え字３２７６７オーバー、６５５３５オーバー、配列のメモリ－オ－バー位ですね。

お礼

さっそく、回答ありがとうございます。
やっぱりメモリオーバーですか。
いろいろ改善してみる必要がありますね。
有難うございました！！