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

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

ただいまの
回答率

90.12%

バブルソート, シェルソート, クイックソートの実現

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 0
  • VIEW 1,037
退会済みユーザー

退会済みユーザー

前提・実現したいこと

Cで三角形の構造体を面積(辺の和)でソートするプログラムを実現したいです。Segmentation faultが表示されるのですが原因がわからないのでご教授願いたいです。

[追記]
A[SIZE]をポインタを用いないものに変更しましたがどのソートを実行してもソートされません。

1
Side : 224.210646
Area : 2072.541918
 2
Side : 200.143520
Area : 1352.474029
 3
Side : 186.673849
Area : 1447.508549
 4
Side : 240.090907
Area : 1719.078096
 5
Side : 142.866303
Area : 967.710959
 6
Side : 164.552194
Area : 935.697066
 7
Side : 95.511362
Area : 172.333253
 8
Side : 224.741866
Area : 1657.931090
 9
Side : 185.111045
Area : 1389.912227
10
Side : 143.538119
Area : 446.386604

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

Segmentation fault: 11が表示されます。

該当のソースコード

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

#define SIZE 100000
#define XMAX 100
#define YMAX 100
#define ZMAX 100
#define TEST_NUM 10

typedef struct POINT {
  int x;
  int y;
  int z;
} point_t;

typedef struct TRIANGLE {
  point_t p[3];
} triangle_t;

triangle_t A[SIZE];

//A[]の初期化
void init_triangle(triangle_t t[], int n)
{
  int i, j;

  for (i = 0; i < n; i++) {
    for (j = 0; j < 3; j++) {
      t[i].p[j].x = 0;
      t[i].p[j].y = 0;
      t[i].p[j].z = 0;
    }
  }
}

//三角形の辺の和, 面積を出力
void print_triangle(triangle_t t)
{
  double ss, s[3]; //面積の和, 各辺
  double a; //面積

    s[0] = sqrt(pow((double)(t.p[1].x - t.p[0].x), 2) + pow((double)(t.p[1].y - t.p[0].y), 2) + pow((double)(t.p[1].z - t.p[0].z), 2)); 
    s[1] = sqrt(pow((double)(t.p[2].x - t.p[1].x), 2) + pow((double)(t.p[2].y - t.p[1].y), 2) + pow((double)(t.p[2].z - t.p[1].z), 2)); 
    s[2] = sqrt(pow((double)(t.p[0].x - t.p[2].x), 2) + pow((double)(t.p[0].y - t.p[2].y), 2) + pow((double)(t.p[0].z - t.p[2].z), 2)); 
    ss = s[0] + s[1] + s[2];

    printf("Side : %f\n", ss);

    ss /= 2;
    a = sqrt(ss * (ss - s[0]) * (ss - s[1]) * (ss - s[2]));

    printf("Area : %f\n", a);
}

//三角形生成
triangle_t create_triangle()
{
  int x[3], y[3], z[3]; //各座標
  double s[3]; //各辺の長さ
  triangle_t tr; //三角形
  int i;


  for (i = 0; i < 3; i++) {
    x[i] = rand() % XMAX;
    y[i] = rand() % YMAX;
    z[i] = rand() % ZMAX;
    //printf("%4d %4d %4d\n", x[i], y[i], z[i]);
  }

  s[0] = sqrt(pow((double)(x[1] - x[0]), 2) + pow((double)(y[1] - y[0]), 2) + pow((double)(z[1] - z[0]), 2)); 
  s[1] = sqrt(pow((double)(x[2] - x[1]), 2) + pow((double)(y[2] - y[1]), 2) + pow((double)(z[2] - z[1]), 2)); 
  s[2] = sqrt(pow((double)(x[0] - x[2]), 2) + pow((double)(y[0] - y[2]), 2) + pow((double)(z[0] - z[2]), 2)); 
  //for (i = 0; i < 3; i++) printf("%f\n", s[i]);

  //三角形成立条件
  if (s[0] + s[1] > s[2] && s[1] + s[2] > s[0] && s[2] + s[0] > s[1]) {
    for (i = 0; i < 3; i++) {
      tr.p[i].x = x[i];
      tr.p[i].y = y[i];
      tr.p[i].z = z[i];
    }
    //printf("   x      y      z\n");
    //for (i = 0; i < 3; i++) printf("%d %6d %6d %6d\n", i + 1, ptr.p[i].x, ptr.p[i].y, ptr.p[i].z);
    return tr;
  }
  else {
    for (i = 0; i < 3; i++) {
      tr.p[i].x = x[i];
      tr.p[i].y = y[i];
      tr.p[i].z = z[i];
    }
    return tr;
  }
}

//三角形の面積(等しければ3辺の和)を比較し前者が小さければ負, 後者が小さければ正を返す
int cmp_triangle(triangle_t t1, triangle_t t2)
{
  double a1, a2; //各面積
  double s1[3], s2[3]; //各辺
  double ss1, ss2; //辺の和の1/2

  s1[0] = sqrt(pow((double)(t1.p[1].x - t1.p[0].x), 2) + pow((double)(t1.p[1].y - t1.p[0].y), 2) + pow((double)(t1.p[1].z - t1.p[0].z), 2)); 
  s1[1] = sqrt(pow((double)(t1.p[2].x - t1.p[1].x), 2) + pow((double)(t1.p[2].y - t1.p[1].y), 2) + pow((double)(t1.p[2].z - t1.p[1].z), 2)); 
  s1[2] = sqrt(pow((double)(t1.p[0].x - t1.p[2].x), 2) + pow((double)(t1.p[0].y - t1.p[2].y), 2) + pow((double)(t1.p[0].z - t1.p[2].z), 2)); 
  ss1 = (s1[0] + s1[1] + s1[2]) / 2;

  s2[0] = sqrt(pow((double)(t2.p[1].x - t2.p[0].x), 2) + pow((double)(t2.p[1].y - t2.p[0].y), 2) + pow((double)(t2.p[1].z - t2.p[0].z), 2)); 
  s2[1] = sqrt(pow((double)(t2.p[2].x - t2.p[1].x), 2) + pow((double)(t2.p[2].y - t2.p[1].y), 2) + pow((double)(t2.p[2].z - t2.p[1].z), 2)); 
  s2[2] = sqrt(pow((double)(t2.p[0].x - t2.p[2].x), 2) + pow((double)(t2.p[0].y - t2.p[2].y), 2) + pow((double)(t2.p[0].z - t2.p[2].z), 2)); 
  ss2 = (s2[0] + s2[1] + s2[2]) / 2;

  //printf("%f\n", ss1);
  //printf("%f\n", ss2);

  //printf("The latter's side = %f\n", sqrt(ss2  (ss2 - s2[0])  (ss2 - s2[1])  (ss2 - s2[2])));

  //ヘロンの公式
  a1 = sqrt(ss1 * (ss1 - s1[0]) * (ss1 - s1[1]) * (ss1 - s1[2]));
  a2 = sqrt(ss2 * (ss2 - s2[0]) * (ss2 - s2[1]) * (ss2 - s2[2]));
  printf("%f\n", a1);
  printf("%f\n", a2);

  if (a1 < a2) return -1;
  else if (a1 > a2) return 1;
  else {
    if (ss1 < ss2) return -2;
    else if (ss1 > ss2) return 2;
    else return 0;
  }
}

//cmp_triangleの結果を文字で出力するバージョン
void print_cmp_triangle(triangle_t t1, triangle_t t2)
{
  int cmp = cmp_triangle(t1, t2);

  if (cmp == -1) printf("The former's area is smaller than the latter.\n");
  else if (cmp == 1) printf("The former's area is larger than the latter.\n");
  else if (cmp == -2) printf("The former's side is smaller than the latter.\n");
  else if (cmp == 2) printf("The former's side is larger than the latter.\n"); 
  else printf("Both of areas and sides are same.\n");
}

//スワップ
void swap(triangle_t *x, triangle_t *y)
{
  triangle_t *tmp;

  tmp = x;
  x = y;
  y = tmp;
}

//バブルソート
void bubble_sort(triangle_t t[], int n)
{
  int i, j;

  for (i = 0; i < n; i++)
    for (j = n - 1; j > i; j--)
      if (cmp_triangle(t[j - 1], t[j]) > 0) swap(&t[j - 1], &t[j]);
}

//シェルソート
//G:ギャップ列
void shell_sort(triangle_t t[], int n)
{
  int i, j, k = 0;
  int K;
  int G[n];

  //G[k] = 2^(k+1)-1 : Hibbardの方法
  for (i = 0; G[i] < n; i++) G[i] = (pow(2, k + 1)) - 1;
  K = i - 1;

  for (k = K; k >= 0; k--) {
    for (i = G[k]; i < n; i++) {
      triangle_t tmp = t[i];
      j = i - G[k];
      while (j >= 0 && cmp_triangle(tmp, t[j]) < 0) {
        t[j + G[k]] = t[j];
        j -= G[k];
      }
      t[j + G[k]] = tmp;
    }
  }
}

//クイックソートにおける分割処理
int partition(triangle_t t[], int pivot, int left, int right)
{
  t[right] = t[pivot];
  int l = left;
  int r = right;

  while (1) {
    while (cmp_triangle(t[l], t[right]) < 0) l++;
    while (l <= r && cmp_triangle(t[r], t[right]) >= 0) r--;
    if (l < r) swap(&t[l], &t[r]);
    else break;
  }

  swap(&t[l], &t[right]);
  return l;
}

//左端, 中央, 右端のうち真ん中の値の要素のインデックスを出力する
int middle_value(triangle_t t[], int n)
{
  triangle_t B[3] = {t[0], t[n / 2], t[n - 1]};
  triangle_t max = B[0], min = B[0], mid;
  int i;

  //最大の判定
  for (i = 1; i <= 2; i++)
    if (cmp_triangle(B[i], max) > 0) max = B[i];

  //最小の判定
  for (i = 1; i <= 2; i++)
    if (cmp_triangle(B[i], max) < 0) max = B[i];

  //中間値を求める
  for (i = 0; i < 3; i++)
    if (cmp_triangle(B[i], max) != 0 && cmp_triangle(B[i], min) != 0) mid = B[i];

  if (cmp_triangle(mid, t[0]) == 0) return 0;
  else if (cmp_triangle(mid, t[n / 2])) return n / 2;
  else if (cmp_triangle(mid, t[n - 1])) return n - 1;
  else return -1;
}

//クイックソート
void quick_sort(triangle_t t[], int left, int right, int n)
{
  if (left < right) {
    int pivot = middle_value(t, n);

    int p = partition(t, pivot, left, right); //分割処理
      //A[pivot]未満のデータをA[left],...,A[p-1]に集める
      //A[pivot]以上のデータをA[p+1],...,A[right]に集める
      //A[pivot]の値をA[p]に入れる

    quick_sort(t, left, p - 1, n);
    quick_sort(t, p + 1, right, n);
  }
}

int main()
{
  int i;

  //ソートテスト
  triangle_t T[TEST_NUM];
  //init_triangle(T, TEST_NUM);
  srand((unsigned)time(NULL));
  for (i = 0; i < TEST_NUM; i++) T[i] = create_triangle();

  //bubble_sort(T, TEST_NUM);
  shell_sort(T, TEST_NUM);
  //quick_sort(T, 0, TEST_NUM - 1, TEST_NUM);

  for (i = 0; i < TEST_NUM; i++) {
    printf("%2d\n", i + 1);
    print_triangle(T[i]);
  }

  return 0;
}
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

+2

こんにちは。

取り敢えず、shell_sort()関数のローカル変数k(小文字の方)が初期化されていないようですが、これは現在のフォルトとは無関係のようです。

bubble_sort()関数で呼び出したcmp_triangle()関数内の下記行で落ちてました。

s1[0] = sqrt(pow((double)(t1->p[1].x - t1->p[0].x), 2) + pow((double)(t1->p[1].y - t1->p[0].y), 2) + pow((double)(t1->p[1].z - t1->p[0].z), 2));

t1がNULLでした。
確かに、A[]変数が初期化されていないです。

triangle_t *A[SIZE];

は、triangle_t型へのポインタの配列です。A[x](xは0~SIZE-1)にtriangle_t変数へのポインタを設定する必要が有ります。
簡単に対処するなら、下記がお薦めです。

triangle_t A[SIZE];として、cmp_triangle(&A[j - 1], &A[j])で呼び出す。

これに合わせてAを直接アクセスしている関数の修正が必要です。
例えば、init_triangle()A[i]->p[j].x = 0;A[i].p[j].x = 0;などです。

他にも似たような不具合が幾つかありそうな感じがします。
私はVisual Studio 2015を使ってやってみました。IDEを使えば、例外が発生したタイミングで一旦停止し、そこまでの呼び出し履歴が表示されるので、簡単に原因をつかむことができます。

Segmentation fault: 11ということはgcc系のコンパイラをお使いと思います。
gccの方のIDEもいくつかあるようですので、使うと便利ですよ。
(gccの方が具体的には把握してないので紹介できません。ごめんなさい。)

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2016/07/24 20:01

    すみません、途中送信してしまいました。
    今度はソートがされないです。

    キャンセル

  • 2016/07/24 20:56

    ソート対象を3つくらいにして、ソート関数のループの中で、その3つの状態を全てprintf()で表示してみて下さい。
    ソートアルゴリズムに比べて、想定外の動作をしている部分がある筈です。
    それを見つけて修正しましょう。

    キャンセル

  • 2016/07/26 09:14

    解決しました。
    ありがとうございました。

    キャンセル

+1

落ちているところはChironianさんの言うとおりです。宗教的な理由でWindowsではなくMacを使わなければならないなら、XcodeでもVisual Studio 2015のような事はできるはずですので、お試しください。

たぶん、一番おかしな所はtriangle_t *create_triangle()です。理由は「ポインタを返しているが、予め確保された領域を引数として渡しているわけでも、malloc等で動的に確保されているわけでもない」からです。C言語では、関数内部のローカル変数で確保された領域は、関数の終了と共にすべて破棄されます(staticなローカル変数を除く)。そして、returnで返されるのはのみであり、もしそれがポインタであれば、ポインタ値そのものだけです。ポインタの先は渡されず、もし、それがローカル変数の領域なら、関数の終了と共に破棄されます。つまり、次のようなコードはおかしな動作になります。

int *hoge(void)
{
  int a;
  int *p;
  a = 0;
  p = &a;
  return p;
}


上の関数hoge()を呼び出して得る返り値のポインタが全くの使い物にならない理由はわかりますか?上と同じ事をtriangle_t *create_triangle()はしています。これを理解の上、どのようにメモリが確保されているのか、全体を見直してみてください。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

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