teratail
回答率
85.30%
teratail header banner
teratail header banner
質問するログイン新規登録
トップCに関する質問クイックソート双方向リスト

編集履歴

質問編集履歴

11

数値の間隔の修正

2023/12/25 13:41

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -1,6 +1,6 @@
1
1
  双方向リストのクイックソートにて
2
2
  並び替えが以下のように上手くいかないです。
3
- > 0 1 2 3 35 5 6 6 6 6 67 7 7 8 7 7 8 9 10 9
3
+ > 0 1 2 3 3 5 5 6 6 6 6 7 7 7 8 7 7 8 9 10 9
4
4
 
5
5
  ```C
6
6
  #include<stdio.h>
C

10

コード再表示

2023/12/25 13:29

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -1,2 +1,199 @@
1
+ 双方向リストのクイックソートにて
2
+ 並び替えが以下のように上手くいかないです。
3
+ > 0 1 2 3 35 5 6 6 6 6 67 7 7 8 7 7 8 9 10 9
4
+
5
+ ```C
6
+ #include<stdio.h>
7
+ #include<stdlib.h>
8
+
9
+ struct node {
10
+ int data;
1
- @@@@@@@@@@@@@@@@@@
11
+ struct node *prev;
2
- @@@@@@@@@@@@@@@@@@
12
+ struct node *next;
13
+ };
14
+
15
+
16
+ void print_list(struct node *start);
17
+ void sort_list(struct node **arg_s, struct node **arg_e);
18
+ void swap(struct node **left, struct node **right);
19
+ void trade(struct node **l, struct node **r,struct node **s , struct node **e);
20
+
21
+ #define MAX 1000
22
+
23
+ int main(void) {
24
+ struct node *start, *end, *new,*temp;
25
+ int i;
26
+
27
+ start = end = NULL;
28
+ for (i = 0; i < MAX * 5; i++) {
29
+ new = malloc(sizeof(struct node));
30
+ if (new == NULL) {
31
+ fprintf(stderr, "メモリ割り当て失敗\n");
32
+ // ここで適切なクリーンアップを行う
33
+ exit(EXIT_FAILURE);
34
+ }
35
+ new->data = rand() % MAX;
36
+ new->prev = new->next = NULL;
37
+
38
+ if (start == NULL) {
39
+ start = end = new;
40
+ } else {
41
+ end->next = new;
42
+ new->prev = end;
43
+ end = end->next;
44
+ }
45
+ }
46
+
47
+
48
+ printf("ソート前:\n");
49
+ print_list(start);
50
+
51
+ sort_list(&start, &end);
52
+
53
+ printf("ソート後:\n");
54
+ print_list(start);
55
+
56
+ // メモリの解放処理
57
+ while (start != NULL) {
58
+ temp = start;
59
+ start = start->next;
60
+ free(temp);
61
+ }
62
+
63
+ return 0;
64
+ }
65
+
66
+ void print_list(struct node *start)
67
+ {
68
+ struct node *p;
69
+
70
+ p=start;
71
+ while(p!=NULL)
72
+ {
73
+ printf("%d ",p->data);
74
+ p=p->next;
75
+ }
76
+ printf("\n");
77
+ }
78
+
79
+ void sort_list(struct node **arg_s,struct node **arg_e)
80
+ {
81
+ struct node *start,*end,*left,*right,*s1,*s2,*e1,*e2;
82
+ int pivot;
83
+
84
+ //引数を普通のポインタ型に変える
85
+ start = *arg_s;
86
+ end =*arg_e;
87
+
88
+ left =start;
89
+ right =end;
90
+
91
+ //基準値を決定する。
92
+ pivot=left->data;
93
+
94
+ while(left!=right&&left->prev!=right)
95
+ {
96
+ //pivot以上が出るまで繰り返す。
97
+ while(left->data < pivot)
98
+ {
99
+ left=left->next;
100
+ }
101
+
102
+ 　　　//pivot未満が出るまで繰り返す。
103
+ while(right->data >pivot)
104
+ {
105
+ right=right->prev;
106
+ }
107
+
108
+ if(left->prev!=right&&left!=right)
109
+ {
110
+ //leftとrightを交換する。
111
+ trade(&left,&right,&start,&end);
112
+ //nextを代入する。
113
+ left=left->next;
114
+ right=right->prev;
115
+ }
116
+ }
117
+
118
+ s2=right->next;
119
+ e1=right;
120
+
121
+ s1=start;
122
+ e1->next=NULL;
123
+ e2=end;
124
+ e2->next=NULL;
125
+
126
+
127
+ if(s1!=e1)
128
+ {
129
+ sort_list(&s1,&e1);
130
+ }
131
+ if(s2!=e2)
132
+ {
133
+ sort_list(&s2,&e2);
134
+ }
135
+
136
+ //連結し直す。
137
+ e1->next=s2;
138
+ s2->prev=e1;
139
+
140
+ //戻り値を設定する
141
+ *arg_s=s1;
142
+ *arg_e=e2;
143
+ }
144
+
145
+
146
+ //leftとrightを交換する関数。
147
+ void trade(struct node **l, struct node **r,struct node **s , struct node **e)
148
+ {
149
+ struct node *start,*end,*left,*right;
150
+
151
+ //引数を普通のポインタ型に変える
152
+ start = *s;
153
+ end =*e;
154
+ left =*l;
155
+ right =*r;
156
+
157
+ if(left == start)
158
+ {
159
+ start = right;
160
+ }
161
+ else
162
+ {
163
+ left->prev->next = right;
164
+ }
165
+
166
+ // 後側要素を参照していたprevが、前側の要素を参照するように変更
167
+ if(right == end)
168
+ {
169
+ end = left;
170
+ }
171
+ else
172
+ {
173
+ right->next->prev = left;
174
+ }
175
+
176
+ // start/endに関係ない部分を交換する
177
+ left->next->prev = right;
178
+ swap(&left->next, &right->next);
179
+ right->prev->next = left;
180
+ swap(&left->prev, &right->prev);
181
+ swap(&left, &right);
182
+
183
+ *l=left;
184
+ *r=right;
185
+ *s=start;
186
+ *e=end;
187
+ }
188
+
189
+ // 構造体のポインタ同士を交換する関数
190
+ void swap(struct node **left, struct node **right)
191
+ {
192
+ struct node *tmp;
193
+
194
+ tmp = *left;
195
+ *left = *right;
196
+ *right = tmp;
197
+ }
198
+
199
+ ```
C
C

9

2020/12/05 12:17

投稿

natsu158
natsu158

スコア1

title CHANGED
@@ -1,1 +1,1 @@
1
- c言語 クイックソート
1
+ クイックソート双方向リスト
body CHANGED
File without changes

8

2020/12/05 12:17

投稿

natsu158
natsu158

スコア1

title CHANGED
@@ -1,1 +1,1 @@
1
- クイックソート双方向リスト
1
+ c言語 クイックソート
body CHANGED
@@ -1,209 +1,2 @@
1
- 双方向リストのクイックソートで昇順をしたいのですが上手く行きません。
2
- だいたいはソートできるのですが
3
- (0 0 3 1 1 2 2 10)みたいになってしまいます。どこがいけないのでしょうか？
4
- ```c言語
5
- ex.h
6
- struct node
7
- {
8
- int data;
9
- struct node *prev;
1
+ @@@@@@@@@@@@@@@@@@
10
- struct node *next;
2
+ @@@@@@@@@@@@@@@@@@
11
- };
12
-
13
- void print_list(struct node *start);
14
- void print_list_reverse(struct node *end);
15
- void sort(struct node **arg_s, struct node **arg_e);
16
-
17
- #include<stdio.h>
18
- #include<stdlib.h>
19
- #include<time.h>
20
- #include "ex.h"
21
-
22
- #define MAX 10000
23
- int main(void)
24
- {
25
- struct node *start, *end, *new;
26
- int i;
27
- clock_t ct;
28
-
29
- srand((unsigned int)time(NULL));
30
-
31
-
32
- start =end =NULL;
33
- for(i=0;i<MAX*5;i++)
34
- {
35
-
36
- new = malloc(sizeof(struct node));
37
- new->data =rand()% MAX ;
38
- new->prev =new->next=NULL;
39
-
40
- if(start ==NULL)
41
- {
42
- start =end =new;
43
- }
44
- else
45
- {
46
- end->next = new;
47
- new->prev =end;
48
- end = end->next;
49
- }
50
- }
51
-
52
-
53
- print_list(start);
54
-
55
- clock();
56
- sort(&start, &end);
57
- ct = clock();
58
-
59
-
60
- printf("ソート後:\n");
61
- print_list(start);
62
-
63
- printf("ソート後(逆順):\n");
64
- print_list_reverse(end);
65
-
66
- printf("処理時間 %4.2f sec.\n",(double)ct/CLOCKS_PER_SEC);
67
-
68
- return 0;
69
- }
70
-
71
-
72
- void print_list(struct node *start)
73
- {
74
- struct node *p;
75
-
76
- p=start;
77
- while(p!=NULL)
78
- {
79
- printf("%d ",p->data);
80
- p=p->next;
81
- }
82
- printf("\n");
83
- }
84
-
85
- void print_list_reverse(struct node *end)
86
- {
87
- struct node *p;
88
-
89
- p=end;
90
- while(p!=NULL)
91
- {
92
- printf("%d ",p->data);
93
- p=p->prev;
94
- }
95
- printf("\n");
96
- }
97
-
98
- #include<stdio.h>
99
- #include<stdlib.h>
100
- #include "ex.h"
101
- void swap(struct node **left, struct node **right);
102
- void trade(struct node **l, struct node **r,struct node **s , struct node **e);
103
-
104
- void sort(struct node **arg_s,struct node**arg_e)
105
- {
106
- struct node *start,*end,*left,*right,*s1,*s2,*e1,*e2;
107
- int pivot;
108
-
109
- start = *arg_s;
110
- end =*arg_e;
111
- left =start;
112
- right =end;
113
-
114
- pivot=left->data;
115
-
116
- while(left!=right&&left->prev!=right)
117
- {
118
- while(left->data <pivot&&left!=right)
119
- {
120
- left=left->next;
121
- }
122
-
123
- while(right->data >=pivot&&right!=left)
124
- {
125
- right=right->prev;
126
- }
127
-
128
- if(left!=right)
129
- {
130
- trade(&left,&right,&start,&end);
131
-
132
- left=left->next;
133
- right=right->prev;
134
- }
135
- }
136
-
137
-
138
- s1=start;
139
- s2=right->next;
140
- e1=right;
141
- e1->next=NULL;
142
- e2=end;
143
- e2->next=NULL;
144
-
145
- if(s1!=e1)
146
- {
147
- sort(&s1,&e1);
148
- }
149
- if(s2!=e2)
150
- {
151
- sort(&s2,&e2);
152
- }
153
-
154
- e1->next=s2;
155
- s2->prev=e1;
156
-
157
- *arg_s=s1;
158
- *arg_e=e2;
159
- }
160
-
161
-
162
- void trade(struct node **l, struct node **r,struct node **s , struct node **e)
163
- {
164
- struct node *start,*end,*left,*right;
165
-
166
- start = *s;
167
- end =*e;
168
- left =*l;
169
- right =*r;
170
-
171
- if(left == start)
172
- {
173
- start = right;
174
- }
175
- else
176
- {
177
- left->prev->next = right;
178
- }
179
-
180
- if(right == end)
181
- {
182
- end = left;
183
- }
184
- else
185
- {
186
- right->next->prev = left;
187
- }
188
-
189
- left->next->prev = right;
190
- swap(&left->next, &right->next);
191
- right->prev->next = left;
192
- swap(&left->prev, &right->prev);
193
- swap(&left, &right);
194
-
195
- *l=left;
196
- *r=right;
197
- *s=start;
198
- *e=end;
199
- }
200
-
201
- void swap(struct node **left, struct node **right)
202
- {
203
- struct node *tmp;
204
-
205
- tmp = *left;
206
- *left = *right;
207
- *right = tmp;
208
- }
209
- ```

7

2020/12/03 03:28

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -12,7 +12,7 @@
12
12
 
13
13
  void print_list(struct node *start);
14
14
  void print_list_reverse(struct node *end);
15
- void sort_list(struct node **arg_s, struct node **arg_e);
15
+ void sort(struct node **arg_s, struct node **arg_e);
16
16
 
17
17
  #include<stdio.h>
18
18
  #include<stdlib.h>

6

2020/12/03 03:10

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -49,11 +49,8 @@
49
49
  }
50
50
  }
51
51
 
52
- //ソート前のリストを出力する
52
+
53
- printf("ソート前:\n");
54
53
  print_list(start);
55
- printf("---------------------------------------\n");
56
-
57
54
 
58
55
  clock();
59
56
  sort(&start, &end);
@@ -62,7 +59,6 @@
62
59
 
63
60
  printf("ソート後:\n");
64
61
  print_list(start);
65
- printf("---------------------------------------\n");
66
62
 
67
63
  printf("ソート後(逆順):\n");
68
64
  print_list_reverse(end);

5

2020/12/02 15:24

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -56,7 +56,7 @@
56
56
 
57
57
 
58
58
  clock();
59
- sort_list(&start, &end);
59
+ sort(&start, &end);
60
60
  ct = clock();
61
61
 
62
62
 

4

2020/12/02 15:20

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -2,9 +2,106 @@
2
2
  だいたいはソートできるのですが
3
3
  (0 0 3 1 1 2 2 10)みたいになってしまいます。どこがいけないのでしょうか？
4
4
  ```c言語
5
+ ex.h
6
+ struct node
7
+ {
8
+ int data;
9
+ struct node *prev;
10
+ struct node *next;
11
+ };
12
+
13
+ void print_list(struct node *start);
14
+ void print_list_reverse(struct node *end);
15
+ void sort_list(struct node **arg_s, struct node **arg_e);
16
+
5
17
  #include<stdio.h>
6
18
  #include<stdlib.h>
19
+ #include<time.h>
7
20
  #include "ex.h"
21
+
22
+ #define MAX 10000
23
+ int main(void)
24
+ {
25
+ struct node *start, *end, *new;
26
+ int i;
27
+ clock_t ct;
28
+
29
+ srand((unsigned int)time(NULL));
30
+
31
+
32
+ start =end =NULL;
33
+ for(i=0;i<MAX*5;i++)
34
+ {
35
+
36
+ new = malloc(sizeof(struct node));
37
+ new->data =rand()% MAX ;
38
+ new->prev =new->next=NULL;
39
+
40
+ if(start ==NULL)
41
+ {
42
+ start =end =new;
43
+ }
44
+ else
45
+ {
46
+ end->next = new;
47
+ new->prev =end;
48
+ end = end->next;
49
+ }
50
+ }
51
+
52
+ //ソート前のリストを出力する
53
+ printf("ソート前:\n");
54
+ print_list(start);
55
+ printf("---------------------------------------\n");
56
+
57
+
58
+ clock();
59
+ sort_list(&start, &end);
60
+ ct = clock();
61
+
62
+
63
+ printf("ソート後:\n");
64
+ print_list(start);
65
+ printf("---------------------------------------\n");
66
+
67
+ printf("ソート後(逆順):\n");
68
+ print_list_reverse(end);
69
+
70
+ printf("処理時間 %4.2f sec.\n",(double)ct/CLOCKS_PER_SEC);
71
+
72
+ return 0;
73
+ }
74
+
75
+
76
+ void print_list(struct node *start)
77
+ {
78
+ struct node *p;
79
+
80
+ p=start;
81
+ while(p!=NULL)
82
+ {
83
+ printf("%d ",p->data);
84
+ p=p->next;
85
+ }
86
+ printf("\n");
87
+ }
88
+
89
+ void print_list_reverse(struct node *end)
90
+ {
91
+ struct node *p;
92
+
93
+ p=end;
94
+ while(p!=NULL)
95
+ {
96
+ printf("%d ",p->data);
97
+ p=p->prev;
98
+ }
99
+ printf("\n");
100
+ }
101
+
102
+ #include<stdio.h>
103
+ #include<stdlib.h>
104
+ #include "ex.h"
8
105
  void swap(struct node **left, struct node **right);
9
106
  void trade(struct node **l, struct node **r,struct node **s , struct node **e);
10
107
 

3

2020/12/02 15:19

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -4,7 +4,7 @@
4
4
  ```c言語
5
5
  #include<stdio.h>
6
6
  #include<stdlib.h>
7
- #include "ex4.h"
7
+ #include "ex.h"
8
8
  void swap(struct node **left, struct node **right);
9
9
  void trade(struct node **l, struct node **r,struct node **s , struct node **e);
10
10
 

2

2020/12/02 15:01

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -22,24 +22,24 @@
22
22
 
23
23
  while(left!=right&&left->prev!=right)
24
24
  {
25
- while(left->data <pivot&&left!=right)
25
+ while(left->data <pivot&&left!=right)
26
- {
26
+ {
27
- left=left->next;
27
+ left=left->next;
28
- }
28
+ }
29
29
 
30
- while(right->data >=pivot&&right!=left)
30
+ while(right->data >=pivot&&right!=left)
31
- {
31
+ {
32
- right=right->prev;
32
+ right=right->prev;
33
- }
33
+ }
34
34
 
35
- if(left!=right)
35
+ if(left!=right)
36
- {
36
+ {
37
- trade(&left,&right,&start,&end);
37
+ trade(&left,&right,&start,&end);
38
38
 
39
- left=left->next;
39
+ left=left->next;
40
- right=right->prev;
40
+ right=right->prev;
41
+ }
41
42
  }
42
- }
43
43
 
44
44
 
45
45
  s1=start;
@@ -81,16 +81,16 @@
81
81
  }
82
82
  else
83
83
  {
84
- left->prev->next = right;
84
+ left->prev->next = right;
85
85
  }
86
86
 
87
87
  if(right == end)
88
88
  {
89
- end = left;
89
+ end = left;
90
90
  }
91
91
  else
92
92
  {
93
- right->next->prev = left;
93
+ right->next->prev = left;
94
94
  }
95
95
 
96
96
  left->next->prev = right;
@@ -107,10 +107,10 @@
107
107
 
108
108
  void swap(struct node **left, struct node **right)
109
109
  {
110
- struct node *tmp;
110
+ struct node *tmp;
111
111
 
112
- tmp = *left;
112
+ tmp = *left;
113
- *left = *right;
113
+ *left = *right;
114
- *right = tmp;
114
+ *right = tmp;
115
115
  }
116
116
  ```

1

2020/12/02 14:43

投稿

natsu158
natsu158

スコア1

title CHANGED
File without changes
body CHANGED
@@ -1,8 +1,7 @@
1
- c言語について
2
1
  双方向リストのクイックソートで昇順をしたいのですが上手く行きません。
3
2
  だいたいはソートできるのですが
4
3
  (0 0 3 1 1 2 2 10)みたいになってしまいます。どこがいけないのでしょうか？
5
-
4
+ ```c言語
6
5
  #include<stdio.h>
7
6
  #include<stdlib.h>
8
7
  #include "ex4.h"
@@ -113,4 +112,5 @@
113
112
  tmp = *left;
114
113
  *left = *right;
115
114
  *right = tmp;
116
- }
115
+ }
116
+ ```