連結リスト（単方向リスト）を用いたクイックソートのプログラムの作成

Question

前提

C言語で連結リストを用いたクイックソートのプログラムを作成しています。
リストの要素数はプログラムの引数で指定するようにしています。
リストの要素 Node の値 value は 1 から 10000 までの整数をランダムで入れるようにします。
まだまだプログラミング初学者なため出来るだけ簡単に分かりやすくご教授いただければ幸いです。
よろしくお願いします。（ｃ言語）

実現したいこと

以下のような実行をイメージしています。

＞./qsort 10
generated list
7019, 7431, 4192, 3673, 6593, 1236, 9108, 5213, 5460, 8572
sorted list
1236, 3673, 4192, 5460, 5213, 6593, 7019, 7431, 8572, 9108

そのためにquick_sort_list にある
pivotの値より小さい要素をl_pivotに集め、
pivotの値と同じ大きさの要素をe_pivotに集め、
pivotの値より大きい要素をr_pivotに集める部分を修正して
所望の動作が出来るようにしたいです。

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

エラーなくコンパイルすることが出来るのですが、ソートをしたはずのリストが表示されずに以下のような実行になってしまいます。これを修正して上記のような実行になる様にしたいです。

＞./qsort 10
generated list
9604 7228 8288 2305 8323 9013 7967 3979 7798 1795
sorted list

該当のソースコード

//qsort.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

typedef struct node Node;

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

Node *prepare_head(int);
Node *generate_node();
int gen_random_num(int);
void  print_list(Node *);
Node *quick_sort_list (Node *);
Node *concatante (Node *, Node *);

int main(int argc, char *argv[])
{
  Node *head;
  int  n;

  n = atoi(argv[1]);

  srand((unsigned int)time(NULL)); // 現在時刻の情報で初期化

  head = prepare_head(n);
  printf("generated list\n");
  print_list(head);
  head = quick_sort_list(head);
  printf("sorted list\n");
  print_list(head);

}
Node *concatante (Node *a, Node *b)
{
  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;
}
Node *quick_sort_list (Node *c)
{
  int pivot;
  Node *t;
  Node *l_pivot = NULL;
  Node *e_pivot = NULL;
  Node *r_pivot = NULL;

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

  pivot = c->value;

  while(c->next != NULL) {
    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));
}
Node *prepare_head(int n)
{
  int i;
  Node *p, *q, *head;
  head = generate_node();
  p = head;
  for(i = 0;i < n;i++) {
    q = generate_node();
    q->value = gen_random_num(10000);
    p->next = q;
    p = q;
  }
  return head;
}
void  print_list(Node *head)
{
  Node *p = head;
  while(p->next != NULL) {
    p = p->next;
    printf(" %d",p->value);
  }
  printf("\n");
}
Node *generate_node()
{
  Node *p = (Node *)malloc(sizeof(Node));
  p->next = NULL;
  return p;
}
int gen_random_num(int max)
{
  return (int)(rand()*(max + 1.0)/(1.0+RAND_MAX));
}

Comments

[jimbe]

推奨していない質問 → https://teratail.com/help/avoid-asking

それぞれの関数が想定通りに動作しているのかを確認してみてください。

[4431]

concatante、quick_sort_list以外は想定通りの動作をしていると思われます。

[jimbe]

>想定通りの動作をしていると思われます。

思われます、は確認しているとは言えません。
二つの関数が怪しいと考えているのであれば、それらを優先的に確認するべきと思います。

prepare_head で作ったリストは head はデータを入れない形になっているようです ( print_list も head の value は表示していません ) が、 concatante や quick_sort_list はそのようにしていますでしょうか。

[hoshi-takanori]

そもそも連結リストは quick sort に向いてないという話が…。
https://cs.stackexchange.com/questions/84723/why-dont-we-use-quick-sort-on-a-linked-list

Answer 1

問題は 3 つです。

１. prepare_head 関数が生成し print_list 関数のパラメータが前提としているリストの構造と、quick_sort_list, concatante 関数のパラメータが前提としているリストの構造が違っている。

前者は head ノードは value を設定せず next の先が実際のデータであるのに対し、後者は head からデータであることになっています。
main 関数での head の使い方も恐らく後者です。前者だとしたらメモリリークがあります。

２. quick_sort_list 関数の while 内で、ループしても変数 c が正しく次のノードを指していない。

変数 t に c->next を保存した上で c->next を更新しているのに、 t が使われていません。

３. concatante 関数が a の後ろに b を正しく連結出来ていない

pig_vba さんがご自身の回答のコメントで指摘されています。

Answer 2

※普通に誤回答なので折りたたみます。無視してください

  while(c->next != NULL) {
    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の初期値はNULLなのでこれ全部c->nextにNULLが挿入されているように見えます。

    if (t->value < pivot) {
      //入れ替え処理
    }

私はこうだと思ったんですけど、間違えてたらすみません

Comments

[4431]

申し訳ございません。修正してみましたが、正しく動作しませんでした。ご回答ありがとうございます。

[pig_vba]

お力に添えられず申し訳ございません。
あと別の項目になりますが、*concatante関数はnode aの後ろにnode bを結合する関数でしょうか?そうであるならばaの末尾に結合だと思うので
for (p = a; p->next != NULL; p = p->next);
p->next = b;
こうではないでしょうか？

[jimbe]

該当 while は 大小関係に合わせて各 pivot リストの先頭に追加しているので、追加の処理自体は間違っておりません。
ただ…最後に重要な処理が足りないです。( t は何の為にあるのでしょう。)

>//c->valueとt->valueを入れ替える処理

少なくとも、 リストを使用しているのは value を直接入れ替えるのでは無く Node のポインタの繋ぎ変えで入れ替えるということですので、この部分は合わないと思います。

[pig_vba]

やっぱりそうでしたか。余計混乱させるだけなので自分は静観しておきます

[jimbe]

concatante の指摘は合っていると思います。