このコードでセグメンテーションフォルトが発生する理由を誰にでも教えてください

Question

私は様々なディストリビューションでテストしていますが、逆順（降順）のソート済み配列が入力として与えられると、セグメンテーションフォルトが発生します。ときどき逆ソートされた配列でもうまく動作することがありますが、時には、特に大きな逆ソート配列（> 100000）でセグメント化エラーエラーが発生することがあります。再帰呼び出し深度の限界、再帰呼び出し深度の限界、再帰呼び出し深度の限界、再帰呼び出しの深さ、再帰呼び出しの深さ、再帰的プログラムを記述する際の予防措置について注意しなければならないことがあります。

Answer 1

の値として、常にa[lower]を使用する代わりに、upperとlower間のランダムな値を使用します。

逆順ソート配列は、パーティションスキームの最悪の場合です。n要素の配列にn-1回を繰り返し表示します。

この病理学的なケースを避けるためにパーティションスキームを試してみることはできますが、quick_sort関数で深い再帰を避ける方法があります。病理学的症例は非常に遅いが、もはやクラッシュすることはない。

#include <stdio.h> 
#include <time.h> 

int partition(double *a, int lower, int upper) { 
    /* assuming lower < upper */ 
    int i = lower, j = upper; 
    double t = a[lower], temp; 
    while (i <= j) { 
     while (i <= upper && a[i] <= t) 
      i++; 
     while (a[j] > t) 
      j--; 
     if (i < j) { 
      temp = a[i]; 
      a[i] = a[j]; 
      a[j] = temp; 
     } 
    } 
    temp = a[lower]; 
    a[lower] = a[j]; 
    a[j] = temp; 
    return j; 
} 

void quick_sort(double *a, int lower, int upper) { 
    while (lower < upper) { 
     int j = partition(a, lower, upper); 
     if (j - lower < upper - j) { 
      if (lower < j - 1) { 
       quick_sort(a, lower, j - 1); 
      } 
      lower = j + 1; 
     } else { 
      if (j + 1 < upper) { 
       quick_sort(a, j + 1, upper); 
      } 
      upper = j - 1; 
     } 
    } 
} 

int main(void) { 
    double a[65536]; 
    for (int n = 2; n <= (int)(sizeof(a)/sizeof(*a)); n += n) { 
     for (int i = 0; i < n; i++) { 
      a[i] = n - i; 
     } 
     clock_t t = clock(); 
     quick_sort(a, 0, n - 1); 
     t = clock() - t; 
     for (int i = 1; i < n; i++) { 
      if (a[i - 1] > a[i]) { 
       printf("out of order at %d: %f > %f\n", i - 1, a[i - 1], a[i]); 
       return 1; 
      } 
     } 
     printf("a[%d] sorted in %.3f msec\n", n, (double)t * 1000.0/CLOCKS_PER_SEC); 
    } 
    return 0; 
} 

出力：ここ

がコードである

a[2] sorted in 0.002 msec 
a[4] sorted in 0.001 msec 
a[8] sorted in 0.001 msec 
a[16] sorted in 0.001 msec 
a[32] sorted in 0.000 msec 
a[64] sorted in 0.002 msec 
a[128] sorted in 0.006 msec 
a[256] sorted in 0.021 msec 
a[512] sorted in 0.074 msec 
a[1024] sorted in 0.287 msec 
a[2048] sorted in 1.185 msec 
a[4096] sorted in 5.104 msec 
a[8192] sorted in 19.497 msec 
a[16384] sorted in 78.140 msec 
a[32768] sorted in 297.297 msec 
a[65536] sorted in 1175.032 msec 

はあなたの2番目の質問、に関してはどのような要因には依存して再帰的なプログラムを書きながら撮影するために必要なものを予防策のでしょうか？スタック空間上の

• 制限されている実装固有の（ような概念がある場合）、異なるシステムは非常に異なる制限があります：小型組み込みシステム上のわずか数キロバイトから数メガバイトに決定的な答えはありません大規模なシステムでは

• 何千回も繰り返すことは危険であり、自動ストレージを備えた大規模なアレイもそうです。上記のコードでは、64K doubleの配列を定義していますが、これは現代の汎用コンピュータでは問題ではありませんが、小さなデジタルセンサーでは多すぎる可能性があります。より小さい半分のアプローチでのの繰り返しの最大再帰レベルは、log（N）（N=65536の場合は16）であり、すべてのシステムでOKである必要があります。

Answer 2

はい、セグメント化はあまりにも深い再帰のためです。あなたが速いあなたの関数でソートする逆配列を持っている場合は、必ずtの値としてa[lower]を使用するよう

は、partation機能でtは常にレルム内最大または最小値になります。つまり、戻り値がpartationの場合は、配列が逆転したときに常にupperまたは 'lower'に等しくなります。これにより、（上位 - 下位）再帰の総数が発生し、必ずエラーが発生します。これを避けるために、あなたが原因スタックオーバーフローのセグメンテーションフォールトを持ってt

#include <stdlib.h> 
#include <time.h> 

int partation(double *a, int lower, int upper) 
{ 
    int i = lower, j = upper; 
    double t = a[rand() % (upper - lower) + lower], temp; 
    while (i <= j) 
    { 
     while (i <= upper&&a[i] <= t) i++; 
     while (a[j]>t) j--; 
     if (i <= j) 
     { 
      temp = a[i]; a[i] = a[j]; a[j] = temp; 
     } 
    } 
    temp = a[lower]; 
    a[lower] = a[j]; 
    a[j] = temp; 
    return j; 

} 

void quick_sort(double *a, int lower, int upper) 
{ 
    int j; 
    if (lower >= upper) return; 
    else 
    { 
     j = partation(a, lower, upper); 
     quick_sort(a, lower, j - 1); 
     quick_sort(a, j + 1, upper); 
    } 
} 

int main() 
{ 
    srand(time(0)); 
    /*input the value of a here*/ 
    /*double a[10000]; 
    for (int i = 10000 - 1, index = 0; --i;++index) 
    { 
     a[index] = i; 
    }*/ 
    quick_sort(a, 0, 9999); 
    return 0; 
}