前提
C言語で連結リストを用いたクイックソートのプログラムを作成しています。
リストの要素数はプログラムの引数で指定するようにしています。
リストの要素 Node の値 value は 1 から 10000 までの整数をランダムで入れるようにします。
まだまだプログラミング初学者なため出来るだけ簡単に分かりやすくご教授いただければ幸いです。
よろしくお願いします。(c言語)
実現したいこと
以下のような実行をイメージしています。
>./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
該当のソースコード
C
1//qsort.c 2#include <stdio.h> 3#include <stdlib.h> 4#include <time.h> 5#include <math.h> 6 7typedef struct node Node; 8 9struct node { 10 int value; 11 Node *next; 12}; 13 14Node *prepare_head(int); 15Node *generate_node(); 16int gen_random_num(int); 17void print_list(Node *); 18Node *quick_sort_list (Node *); 19Node *concatante (Node *, Node *); 20 21int main(int argc, char *argv[]) 22{ 23 Node *head; 24 int n; 25 26 n = atoi(argv[1]); 27 28 srand((unsigned int)time(NULL)); // 現在時刻の情報で初期化 29 30 head = prepare_head(n); 31 printf("generated list\n"); 32 print_list(head); 33 head = quick_sort_list(head); 34 printf("sorted list\n"); 35 print_list(head); 36 37} 38Node *concatante (Node *a, Node *b) 39{ 40 Node *p; 41 if (a == NULL) 42 return b; 43 else if (b == NULL) 44 return a; 45 for (p = a; p->next != NULL; p = p->next) 46 p->next = b; 47 return a; 48} 49Node *quick_sort_list (Node *c) 50{ 51 int pivot; 52 Node *t; 53 Node *l_pivot = NULL; 54 Node *e_pivot = NULL; 55 Node *r_pivot = NULL; 56 57 if (c == NULL || c->next == NULL) 58 return c; 59 60 pivot = c->value; 61 62 while(c->next != NULL) { 63 t = c->next; 64 if (c->value < pivot) { 65 c->next = l_pivot; 66 l_pivot = c; 67 } 68 else if (c->value == pivot) { 69 c->next = e_pivot; 70 e_pivot = c; 71 } 72 else if (c->value > pivot) { 73 c->next = r_pivot; 74 r_pivot = c; 75 } 76 } 77 78 l_pivot = quick_sort_list (l_pivot); 79 r_pivot = quick_sort_list (r_pivot); 80 81 return concatante (l_pivot, concatante (e_pivot, r_pivot)); 82} 83Node *prepare_head(int n) 84{ 85 int i; 86 Node *p, *q, *head; 87 head = generate_node(); 88 p = head; 89 for(i = 0;i < n;i++) { 90 q = generate_node(); 91 q->value = gen_random_num(10000); 92 p->next = q; 93 p = q; 94 } 95 return head; 96} 97void print_list(Node *head) 98{ 99 Node *p = head; 100 while(p->next != NULL) { 101 p = p->next; 102 printf(" %d",p->value); 103 } 104 printf("\n"); 105} 106Node *generate_node() 107{ 108 Node *p = (Node *)malloc(sizeof(Node)); 109 p->next = NULL; 110 return p; 111} 112int gen_random_num(int max) 113{ 114 return (int)(rand()*(max + 1.0)/(1.0+RAND_MAX)); 115}
![guest](/img/icon/icnUserSample.jpg)