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

Question

#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;

わかる方教えてください

Comments

[Chironian]

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

[ccccididid]

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

Answer 1

たとえば[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をしているのです。

Answer 2

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

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

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

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

となります。

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