質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
GCC

GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

解決済

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

1noino
1noino

総合スコア10

GCC

GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

2回答

0評価

0クリップ

233閲覧

投稿2022/06/25 22:13

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

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

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

GCC

#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]); } }

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

hoshi-takanori

2022/06/25 23:13

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

2022/06/25 23:24

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

2022/06/26 00:13

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

2022/06/26 00:16

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

2022/06/26 01:29

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

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

GCC

GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。