クイックソート実行時のエラー原因が分からない

Question

クイックソートの実装をしようとしています。
実行時にエラー(atcoderのコードテストだと終了コード139)になるのですが、エラー文が出てこず、原因(どこをどう直せばよいか)が分かりません。

環境はwindowsでエディターとしてVScodeを使用しています。
コードは以下の通りで、main直前の「quick_sort(A+j, n);」をコメントアウトすると正しくソートはできていないものの、終了はする(printfが実行されている)ので問題は「quick_sort(A+j, n);」にあるのではないかと考えています。

不足している情報や不明点があれば追記しますので指摘してください。
よろしくお願いします。

#include <stdio.h>
#include <assert.h>

// 素数
#define N 2999

int A[N];

// *p と *q の値を入れ替える関数
void swap(int *p, int *q){
  int tmp;
  tmp = *p;
  *p = *q;
  *q = tmp;
}


/*
A[0], A[1], ..., A[n-1] の中でk+1番目に小さい値を返す関数
ただし、Aの中身は書き換えてしまう。
*/

void quick_sort(int A[], int n){
  int i, j, pivot;

  if (n > 1){
  // 真ん中の要素をピボットとする
    pivot = A[n/2];
    A[n/2] = A[0];
    A[0] = pivot;

    for(i = j = 1; i < n; i++){
      //pivot以下の数字をA[i]からA[j-1]に集約
      if (A[i] <= pivot){
        swap(A+i, A+j);
        j++;
      }
    }  
    
    //pivotと一致するものを中心に寄せる
    //pivot=3なら[2, 1, 2, 3, 3, 3, …, 3, 3, 5, 6, 5, 7]のようにする
    int x, y, piv_num; // x:走査用, y;置換用
    piv_num = 0;

    for (x = y = j-1; x>=0; x--){
      if (A[x] == pivot){
        swap(A+x, A+y); //位置xにあったpivotに一致する数字を位置yに寄せる
        y--;
        piv_num++;
      }
    }

    //A[j-piv_num]からA[j-1]までの連続したpiv_num個がpivotと一致する数字
    quick_sort(A+0, j-piv_num);
    quick_sort(A+j, n);
  }
}

int main(){
  int i;
  A[0] = 0;
  A[1] = 17; //原始元
  for(i=2;i<N;i++){
    A[i] = (long long int) A[i-1] * A[1] % N;
  }

// すべての要素が同じ場合でも計算が早く終わるか確認する

  quick_sort(A, N);
  for(i=0;i<N;i++){
    if(A[i] != i) printf("ERROR %dth element is %d\n", i, A[i]);
  }
}

Comments

[hoshi-takanori]

quick_sort(A+j, n); は配列の何番目から何個の要素をソートしますか？

[1noino]

quick_sort(A+j, n)は「配列Aのj+1番目(A[j])から配列のn番目(A[n-1])までをsortする関数」として実装したつもりです。

[melian]

quick_sort(A+j, n);
=>
quick_sort(A+j, n-j);

[hoshi-takanori]

つもりなだけで、実際は j 番目から n 個の要素、つまり元の配列の A[j] 〜 A[j + n - 1] をソートしようとしてますね。

[1noino]

まさにその通りでした。melian氏のコードのように書き直したところ、エラーはでませんでした。ありがとうございます。

Answer 1

quick_sort(A+j, k)は元の配列のA[j]からA[j+k-1]までをソートすることを理解していませんでした。そのため。

quick_sort(A+j, n);
=>
quick_sort(A+j, n-j);

のように書き換えるとエラーを回避できました。

Answer 2

ざっと見て気のついたところを。

int i;
A[0] = 0;
A[1] = 17; //原始元

i は初期化されてません。
ローカル変数は初期化しないとデタラメの値もってます

---

あれ？quick_sort って再帰呼び出して終了しようがないんでは。
どういう条件でこの関数は終了するんでしょう

Comments

[hoshi-takanori]

i は次の for 文で初期化されますよ。

[y_waiwai]

ああ、1なのね。
見間違いしてました

[Zuishin]

> どういう条件でこの関数は終了するんでしょう

終了コード 139 と書いてあるので、セグメンテーション違反です。

https://atcoder.jp/contests/apg4b/tasks/APG4b_al
https://shmug.hatenablog.com/entry/2020/12/15/235915

スタックオーバーフローを意図した回答だと思いますが、問題は他にあります。

そもそも、関数の実行条件が n > 1 なので、n <= 1 の場合はそれ以上再帰呼び出ししません。