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

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

ただいまの
回答率

88.78%

セグメンテーション違反とクイックソートについて

解決済

回答 2

投稿

  • 評価
  • クリップ 0
  • VIEW 666

n4t4dekoko

score 11

前提・実現したいこと

大学のC言語の課題で自分で配列を作ってクイックソートを行い、それをかかった時間とともに表示する(ただしpivotは配列の両端と中央での値の3個の値の中央値とする)プログラムを作成したいです。

発生している問題・エラーメッセージ

ピボットをを両端と中央での値の3個の値の中央値として実装したいけどSegmentation fault: 11と出てきてしまいどこがダメなのかがわからないです。

./a.out
How many arraysize do you want?
100
before sort
1  57  56  1  65  7  98  62  49  14  29  70  71  80  93  46  5  54  11  95  90  59  14  55  41  86  67  26  90  70  93  87  89  83  14  70  29  19  90  61  77  76  5  2  41  75  27  22  60  11  55  54  6  3  35  17  27  36  69  27  49  63  39  12  3  33  34  18  53  89  92  58  42  99  55  71  83  11  49  4  36  11  3  99  99  4  43  60  90  2  82  46  69  29  45  3  99  0  75  68  
sorting・・・
Segmentation fault: 11

該当のソースコード

```C言語
include<stdio.h>
include<stdlib.h>
include<time.h>

int nrandom();
int *make_data();
void showdata();

int pivot_midium(int x,int y,int z){
/* x is left y is middle z is right */
if((x>=y && x<=z) || (x<=y && x>=z)) return x;
else if((y>=x && y<=z) || (y<=x && x>=z)) return y;
else  return z;
}

int nrandom(int n){
return (int)(n*(double)rand()/((double)RAND_MAX+1.0));
}
int *make_data(unsigned int s,int n){
int i,*data;
srand(s);
data=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++){
data[i]=nrandom(n);
}
return data;
}
void showdata(int x[], int n){
int i;
for (i = 0; i < n ; i++)
printf("%d  ", x[i]);
printf("\n");
}

void my_qsort(int a[],int left,int right){
int tmp,pivot,i,j,middle;
middle=a[(left+right)/2];
i=left;
j=right;
pivot = pivot_midium(left,middle,right);
while(1){
while(a[i]<pivot) i++;
while(a[j]>pivot) j--;
if(i>=j) break;
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
i++;
j--;
}
if(left<i-1) my_qsort(a,left,i-1);
if(j+1 < right) my_qsort(a,j+1,right);
}

int main(){
int *arr;
int i,size;
clock_t start,end;

printf("How many arraysize do you want?\n");
scanf("%d",&size);
arr=make_data(2019,size);
printf("before sort\n");
showdata(arr,size);
printf("sorting・・・\n");
start=clock();
my_qsort(arr,0,size);
end = clock();
printf("after sort\n");
showdata(arr,size);
printf("sort time is :%lf sec\n",(double)(end-start)/CLOCKS_PER_SEC);
return 0;
}

試したこと

pivotを両端/2にしてpivot_midiamと38,41行目のmiddle=a[(left+right)/2];とpivot = pivot_midium(left,middle,right);行めを削除したら動くようにはなりました。

補足情報(FW/ツールのバージョンなど)

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

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

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

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

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

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

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

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

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

0

pivot_midium の elseif の条件が間違っています.

main での my_qsort の第三引数が size では, malloc した領域の外をアクセスします.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/19 03:02

    sizeを一度別の変数に入れて第三引数に入れたらきちんと動きました!ありがとうございます。
    それと質問なのですがsizeをそのまま入れるとどうしてmallocした領域の外をアクセスにするんですか?sizeはint型の整数をいれてそのまま第三引数に入れられると思ったのですが・・・

    キャンセル

  • 2019/05/19 03:02

    sizeを一度別の変数に入れて第三引数に入れたらきちんと動きました!ありがとうございます。
    それと質問なのですがsizeをそのまま入れるとどうしてmallocした領域の外をアクセスにするんですか?sizeはint型の整数をいれてそのまま第三引数に入れられると思ったのですが・・・

    キャンセル

  • 2019/05/19 09:33

    size 変数自体が問題なのではありません. size の値が問題です.
    動作が想定と違う場合, まず変数の値の変化を追ってみては如何でしょう. 「size に 100 を入れると make_data は s=2019, n=100 で sizeof(int) が 4 だと 4*100=400バイト確保して, …, my_qsort は left=0, right=100 になって...」という具合です.

    int *a=malloc(n*sizeof(int)); によって確保されるメモリ領域 a を int 配列としてアクセスする場合, 有効範囲は a[0]~a[size-1] です. 配列を a[100] と作成したら有効範囲は a[0]~a[99] となるのと同じです.
    my_qsort の第3引数は内部で j に入れられ, a[j] として a の領域にアクセスします. size が 100 だった場合, size → right → j ですので j も 100 となり a[100] にアクセスすることになります.

    キャンセル

-1

また pivot_midium 内での if の条件ですが, このように複数の変数の関係を記述する場合, 不等号の向きを一致させると式が纏まり, 分かり易くなると思います.
x, y, z で中間の値を求める場合, 左(もしくは右)から小,中,大となる関係として書きます. 例えば

x が中間の場合に !0 となる条件(y<=x<=z or z<=x<=y):
(x>=y && x<=z) || (x<=y && x>=z) → (y<=x && x<=z) || (z<=x && x<=y)

y が中間の場合に !0 となる条件(x<=y<=z or z<=y<=x):
(y>=x && y<=z) || (y<=x && x>=z) → (x<=y && y<=z) || (z<=y && y<=x)

です.
y<=x<=z → y<=x && x<=z と変数の並びが一致し, 式通りに書くことが出来ます.

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/05/19 10:07

    またコメントと回答を間違えました. 失礼しました...

    キャンセル

  • 2019/05/19 17:02

    無事解決しました。ご丁寧に説明いただきありがとうございます。m(_ _)m

    キャンセル

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

  • ただいまの回答率 88.78%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

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