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

Question

前提・実現したいこと

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

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

ピボットをを両端と中央での値の３個の値の中央値として実装したいけど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

該当のソースコード

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/ツールのバージョンなど）

Answer 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 と変数の並びが一致し, 式通りに書くことが出来ます.

Comments

[jimbe]

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

[n4t4dekoko]

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

Answer 2

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

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

Comments

[n4t4dekoko]

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

[n4t4dekoko]

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

[jimbe]

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] にアクセスすることになります.