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

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

ただいまの
回答率

90.49%

  • C

    4638questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • ソート

    85questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。

片方向リストを使ったクイックソートのプログラムについて質問があります

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,834

ccccididid

score 17

#include <stdio.h>

struct node
{
 int value;
 struct node *next;
};

static struct node *
concatante (struct node *a, struct node *b)
{
 struct node *p;
  if (a == NULL)
    return b;
  else if (b == NULL)
    return a;
  for (p = a; p->next != NULL; p = p->next)
    ;
  p->next = b;
  return a;
}

struct node *
quick_sort_list (struct node *c)
{
  int pivot;
  struct node *t;
  struct node *l_pivot = NULL;
  struct node *e_pivot = NULL;
  struct node *r_pivot = NULL;

  if (c == NULL || c->next == NULL)
    return c;

  pivot = c->value;

  for (; c != NULL; c = t)
    {
      t = c->next;
      if (c->value < pivot)
        {
          c->next = l_pivot;
          l_pivot = c;
        }
      else if (c->value == pivot)
        {
          c->next = e_pivot;
          e_pivot = c;
        }
      else if (c->value > pivot)
        {
         c->next = r_pivot;
         r_pivot = c;
        }
    }

  l_pivot = quick_sort_list (l_pivot);
  r_pivot = quick_sort_list (r_pivot);

  return concatante (l_pivot, concatante (e_pivot, r_pivot));
}




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

struct node *quick_sort_list (struct node *);

struct node
{
  int value;
  struct node *next;
};

static void
print_nodes (struct node *p)
{
  for (; p != NULL; p = p->next)
    printf (" %d", p->value);
  printf ("\n");
}

int
main ()
{
  int list[] = { 1, 3, 7, 4, 2, 6, 5 };
  struct node *nodes = NULL;
  int i;

  for (i = sizeof list / sizeof list[0] - 1; i >= 0; --i)
     {
      struct node *p = malloc (sizeof *p);
      if (p == NULL)
       {
          perror ("malloc");
          exit (EXIT_FAILURE);
       }
      p->value = list[i];
      p->next = nodes;
      nodes = p;
    }

  print_nodes (nodes);
  nodes = quick_sort_list (nodes);
  print_nodes (nodes);

  exit (EXIT_SUCCESS);
}

以下のプログラムでわからないところがあります

クイックソートの際、3つの条件で別々のリストに代入していますが
各条件にある以下の部分の一行目の存在意義がいまいちわかりません

c->next = l_pivot;
l_pivot = c;

わかる方教えてください

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

質問への追記・修正、ベストアンサー選択の依頼

  • Chironian

    2016/12/26 15:22

    質問欄右上の<code>を押してでてくる'''の間にソースをコピペすると綺麗に表示できますよ。

    キャンセル

  • ccccididid

    2016/12/26 15:38

    ありがとうございます 修正しました

    キャンセル

回答 2

checkベストアンサー

0

クイックソートアルゴリズムを復習せずに書いているので多少曖昧な部分は許してください。

クイックソートは、適当な値を中央値として、それより低い値のリスト、高い値のリストを仕訳していくことによって徐々に順序を整えていくアルゴリズムです。低い値のリストを作ったら、そのリストの中でまた同じように低い値のリスト、高い値のリストを作ります。これを、リストの仕訳ができなくなるところまで繰り返して最後に繋ぎ合わせます。
(それが if (c == NULL || c->next == NULL) return c;の部分です)

質問にあるc->next = l_pivot;というのは、低い値のリストを作成している部分になります。
片方向のリストなので低い値のリスト作成時には先頭に向かって値を追加していっています。

ちょっと分かりづらいので、各要素が全てpivotを下回りl_pivotに含まれる場合を図で説明します。
[0][1][2] と要素が並んでいた場合

・1回目の代入
l_pivotは最初はNULLです。
今現在持っている要素のc->NextにNULLを設定し、要素をl_pivotに設定します。
[0]->Next = NULL;
l_pivot = [0];
l_pivotから見た要素の並びは [0];

・2回目以降の代入
1つ前の要素を現在の要素のNextフィールドに設定し、要素をl_pivotに設定します。
[1]->Next = [0];
l_pivot = [1];
l_pivotから見た要素の並びは [1][0];

[2]->Next = [1];
l_pivot = [2];
l_pivotから見た要素の並びは [2][1][0];

となります。

クイックソートアルゴリズムでは、こうやって値をざっくり今の中央値より低い値、高い値により分け、それらを後に繋ぎなおすことでソートしていきます。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

0

たとえば[6,5,2,3,1,4]というリストをソートするとして

5を処理するときに該当のif文の中に入ります。この時、cは5の入れ物を指すポインタ、l_pivotはnullなので、
5の入れ物の次はnullになり、l_pivotには5を指すポインタが入ります。

5->null

次に2を処理するときはcは2の入れ物を指すポインタ、l_pivotは5の入れ物を指すポインタが入っているので、
2の入れ物からは以下のように連結したリストが見えるようになります。

2->5->null

3に関しても同様です。
3->2->5->null

この時、3の次が2であることはl_pivotに2の入れものが入っていることから分かりますが、2の次が何であるかはc->next = l_pivotをして一つ前のl_pivotの入れ物のポインタを保存しておかないとわからないのです。そのためc->next = l_pivotをしているのです。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

  • C

    4638questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • ソート

    85questions

    複数のデータを、順序性に従って並べ替えること。 データ処理を行う際に頻繁に用いられ、多くのアルゴリズムが存在します。速度、容量、複雑さなどに違いがあり、高速性に特化したものにクイックソートがあります。