質問編集履歴

11

数値の間隔の修正

2023/12/25 13:41

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test 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>

10

コード再表示

2023/12/25 13:29

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -1,3 +1,199 @@
1
- @@@@@@@@@@@@@@@@@@
1
+ 双方向リストのクイックソートにて
2
+ 並び替えが以下のように上手くいかないです。
3
+ > 0 1 2 3 35 5 6 6 6 6 67 7 7 8 7 7 8 9 10 9
2
4
 
5
+ ```C
6
+ #include<stdio.h>
7
+ #include<stdlib.h>
8
+
9
+ struct node {
10
+ int data;
3
- @@@@@@@@@@@@@@@@@@
11
+ struct node *prev;
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
+ ```

9

2020/12/05 12:17

投稿

natsu158
natsu158

スコア1

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

8

2020/12/05 12:17

投稿

natsu158
natsu158

スコア1

test CHANGED
@@ -1 +1 @@
1
- クイックソート双方向リスト
1
+ c言語 クイックソート
test CHANGED
@@ -1,417 +1,3 @@
1
- 双方向リストのクイックソートで昇順をしたいのですが上手く行きません。
1
+ @@@@@@@@@@@@@@@@@@
2
2
 
3
- だいたいはソートできるのですが
4
-
5
- (0 0 3 1 1 2 2 10)みたいになってしまいます。どこがいけないのでしょうか?
6
-
7
- ```c言語
8
-
9
- ex.h
10
-
11
- struct node
12
-
13
- {
14
-
15
- int data;
16
-
17
- struct node *prev;
3
+ @@@@@@@@@@@@@@@@@@
18
-
19
- struct node *next;
20
-
21
- };
22
-
23
-
24
-
25
- void print_list(struct node *start);
26
-
27
- void print_list_reverse(struct node *end);
28
-
29
- void sort(struct node **arg_s, struct node **arg_e);
30
-
31
-
32
-
33
- #include<stdio.h>
34
-
35
- #include<stdlib.h>
36
-
37
- #include<time.h>
38
-
39
- #include "ex.h"
40
-
41
-
42
-
43
- #define MAX 10000
44
-
45
- int main(void)
46
-
47
- {
48
-
49
- struct node *start, *end, *new;
50
-
51
- int i;
52
-
53
- clock_t ct;
54
-
55
-
56
-
57
- srand((unsigned int)time(NULL));
58
-
59
-
60
-
61
-
62
-
63
- start =end =NULL;
64
-
65
- for(i=0;i<MAX*5;i++)
66
-
67
- {
68
-
69
-
70
-
71
- new = malloc(sizeof(struct node));
72
-
73
- new->data =rand()% MAX ;
74
-
75
- new->prev =new->next=NULL;
76
-
77
-
78
-
79
- if(start ==NULL)
80
-
81
- {
82
-
83
- start =end =new;
84
-
85
- }
86
-
87
- else
88
-
89
- {
90
-
91
- end->next = new;
92
-
93
- new->prev =end;
94
-
95
- end = end->next;
96
-
97
- }
98
-
99
- }
100
-
101
-
102
-
103
-
104
-
105
- print_list(start);
106
-
107
-
108
-
109
- clock();
110
-
111
- sort(&start, &end);
112
-
113
- ct = clock();
114
-
115
-
116
-
117
-
118
-
119
- printf("ソート後:\n");
120
-
121
- print_list(start);
122
-
123
-
124
-
125
- printf("ソート後(逆順):\n");
126
-
127
- print_list_reverse(end);
128
-
129
-
130
-
131
- printf("処理時間 %4.2f sec.\n",(double)ct/CLOCKS_PER_SEC);
132
-
133
-
134
-
135
- return 0;
136
-
137
- }
138
-
139
-
140
-
141
-
142
-
143
- void print_list(struct node *start)
144
-
145
- {
146
-
147
- struct node *p;
148
-
149
-
150
-
151
- p=start;
152
-
153
- while(p!=NULL)
154
-
155
- {
156
-
157
- printf("%d ",p->data);
158
-
159
- p=p->next;
160
-
161
- }
162
-
163
- printf("\n");
164
-
165
- }
166
-
167
-
168
-
169
- void print_list_reverse(struct node *end)
170
-
171
- {
172
-
173
- struct node *p;
174
-
175
-
176
-
177
- p=end;
178
-
179
- while(p!=NULL)
180
-
181
- {
182
-
183
- printf("%d ",p->data);
184
-
185
- p=p->prev;
186
-
187
- }
188
-
189
- printf("\n");
190
-
191
- }
192
-
193
-
194
-
195
- #include<stdio.h>
196
-
197
- #include<stdlib.h>
198
-
199
- #include "ex.h"
200
-
201
- void swap(struct node **left, struct node **right);
202
-
203
- void trade(struct node **l, struct node **r,struct node **s , struct node **e);
204
-
205
-
206
-
207
- void sort(struct node **arg_s,struct node**arg_e)
208
-
209
- {
210
-
211
- struct node *start,*end,*left,*right,*s1,*s2,*e1,*e2;
212
-
213
- int pivot;
214
-
215
-
216
-
217
- start = *arg_s;
218
-
219
- end =*arg_e;
220
-
221
- left =start;
222
-
223
- right =end;
224
-
225
-
226
-
227
- pivot=left->data;
228
-
229
-
230
-
231
- while(left!=right&&left->prev!=right)
232
-
233
- {
234
-
235
- while(left->data <pivot&&left!=right)
236
-
237
- {
238
-
239
- left=left->next;
240
-
241
- }
242
-
243
-
244
-
245
- while(right->data >=pivot&&right!=left)
246
-
247
- {
248
-
249
- right=right->prev;
250
-
251
- }
252
-
253
-
254
-
255
- if(left!=right)
256
-
257
- {
258
-
259
- trade(&left,&right,&start,&end);
260
-
261
-
262
-
263
- left=left->next;
264
-
265
- right=right->prev;
266
-
267
- }
268
-
269
- }
270
-
271
-
272
-
273
-
274
-
275
- s1=start;
276
-
277
- s2=right->next;
278
-
279
- e1=right;
280
-
281
- e1->next=NULL;
282
-
283
- e2=end;
284
-
285
- e2->next=NULL;
286
-
287
-
288
-
289
- if(s1!=e1)
290
-
291
- {
292
-
293
- sort(&s1,&e1);
294
-
295
- }
296
-
297
- if(s2!=e2)
298
-
299
- {
300
-
301
- sort(&s2,&e2);
302
-
303
- }
304
-
305
-
306
-
307
- e1->next=s2;
308
-
309
- s2->prev=e1;
310
-
311
-
312
-
313
- *arg_s=s1;
314
-
315
- *arg_e=e2;
316
-
317
- }
318
-
319
-
320
-
321
-
322
-
323
- void trade(struct node **l, struct node **r,struct node **s , struct node **e)
324
-
325
- {
326
-
327
- struct node *start,*end,*left,*right;
328
-
329
-
330
-
331
- start = *s;
332
-
333
- end =*e;
334
-
335
- left =*l;
336
-
337
- right =*r;
338
-
339
-
340
-
341
- if(left == start)
342
-
343
- {
344
-
345
- start = right;
346
-
347
- }
348
-
349
- else
350
-
351
- {
352
-
353
- left->prev->next = right;
354
-
355
- }
356
-
357
-
358
-
359
- if(right == end)
360
-
361
- {
362
-
363
- end = left;
364
-
365
- }
366
-
367
- else
368
-
369
- {
370
-
371
- right->next->prev = left;
372
-
373
- }
374
-
375
-
376
-
377
- left->next->prev = right;
378
-
379
- swap(&left->next, &right->next);
380
-
381
- right->prev->next = left;
382
-
383
- swap(&left->prev, &right->prev);
384
-
385
- swap(&left, &right);
386
-
387
-
388
-
389
- *l=left;
390
-
391
- *r=right;
392
-
393
- *s=start;
394
-
395
- *e=end;
396
-
397
- }
398
-
399
-
400
-
401
- void swap(struct node **left, struct node **right)
402
-
403
- {
404
-
405
- struct node *tmp;
406
-
407
-
408
-
409
- tmp = *left;
410
-
411
- *left = *right;
412
-
413
- *right = tmp;
414
-
415
- }
416
-
417
- ```

7

2020/12/03 03:28

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -26,7 +26,7 @@
26
26
 
27
27
  void print_list_reverse(struct node *end);
28
28
 
29
- void sort_list(struct node **arg_s, struct node **arg_e);
29
+ void sort(struct node **arg_s, struct node **arg_e);
30
30
 
31
31
 
32
32
 

6

2020/12/03 03:10

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -100,16 +100,10 @@
100
100
 
101
101
 
102
102
 
103
- //ソート前のリストを出力する
103
+
104
-
105
- printf("ソート前:\n");
106
104
 
107
105
  print_list(start);
108
106
 
109
- printf("---------------------------------------\n");
110
-
111
-
112
-
113
107
 
114
108
 
115
109
  clock();
@@ -126,8 +120,6 @@
126
120
 
127
121
  print_list(start);
128
122
 
129
- printf("---------------------------------------\n");
130
-
131
123
 
132
124
 
133
125
  printf("ソート後(逆順):\n");

5

2020/12/02 15:24

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -114,7 +114,7 @@
114
114
 
115
115
  clock();
116
116
 
117
- sort_list(&start, &end);
117
+ sort(&start, &end);
118
118
 
119
119
  ct = clock();
120
120
 

4

2020/12/02 15:20

投稿

natsu158
natsu158

スコア1

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

3

2020/12/02 15:19

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -10,7 +10,7 @@
10
10
 
11
11
  #include<stdlib.h>
12
12
 
13
- #include "ex4.h"
13
+ #include "ex.h"
14
14
 
15
15
  void swap(struct node **left, struct node **right);
16
16
 

2

2020/12/02 15:01

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -46,39 +46,39 @@
46
46
 
47
47
  {
48
48
 
49
- while(left->data <pivot&&left!=right)
49
+ while(left->data <pivot&&left!=right)
50
-
50
+
51
- {
51
+ {
52
-
52
+
53
- left=left->next;
53
+ left=left->next;
54
-
54
+
55
- }
55
+ }
56
-
57
-
58
-
56
+
57
+
58
+
59
- while(right->data >=pivot&&right!=left)
59
+ while(right->data >=pivot&&right!=left)
60
-
60
+
61
- {
61
+ {
62
-
62
+
63
- right=right->prev;
63
+ right=right->prev;
64
-
64
+
65
- }
65
+ }
66
-
67
-
68
-
66
+
67
+
68
+
69
- if(left!=right)
69
+ if(left!=right)
70
-
70
+
71
- {
71
+ {
72
-
72
+
73
- trade(&left,&right,&start,&end);
73
+ trade(&left,&right,&start,&end);
74
-
75
-
76
-
74
+
75
+
76
+
77
- left=left->next;
77
+ left=left->next;
78
-
78
+
79
- right=right->prev;
79
+ right=right->prev;
80
-
80
+
81
- }
81
+ }
82
82
 
83
83
  }
84
84
 
@@ -164,7 +164,7 @@
164
164
 
165
165
  {
166
166
 
167
- left->prev->next = right;
167
+ left->prev->next = right;
168
168
 
169
169
  }
170
170
 
@@ -174,7 +174,7 @@
174
174
 
175
175
  {
176
176
 
177
- end = left;
177
+ end = left;
178
178
 
179
179
  }
180
180
 
@@ -182,7 +182,7 @@
182
182
 
183
183
  {
184
184
 
185
- right->next->prev = left;
185
+ right->next->prev = left;
186
186
 
187
187
  }
188
188
 
@@ -216,15 +216,15 @@
216
216
 
217
217
  {
218
218
 
219
- struct node *tmp;
219
+ struct node *tmp;
220
-
221
-
222
-
220
+
221
+
222
+
223
- tmp = *left;
223
+ tmp = *left;
224
-
224
+
225
- *left = *right;
225
+ *left = *right;
226
-
226
+
227
- *right = tmp;
227
+ *right = tmp;
228
228
 
229
229
  }
230
230
 

1

2020/12/02 14:43

投稿

natsu158
natsu158

スコア1

test CHANGED
File without changes
test CHANGED
@@ -1,12 +1,10 @@
1
- c言語について
2
-
3
1
  双方向リストのクイックソートで昇順をしたいのですが上手く行きません。
4
2
 
5
3
  だいたいはソートできるのですが
6
4
 
7
5
  (0 0 3 1 1 2 2 10)みたいになってしまいます。どこがいけないのでしょうか?
8
6
 
9
-
7
+ ```c言語
10
8
 
11
9
  #include<stdio.h>
12
10
 
@@ -229,3 +227,5 @@
229
227
  *right = tmp;
230
228
 
231
229
  }
230
+
231
+ ```