teratail
回答率
85.48%
質問するログイン新規登録
トップCに関する質問リスト構造を用いた挿入ソート

編集履歴

回答編集履歴

4

移動無し判定を前に移動

2019/05/16 07:55

投稿

jimbe
jimbe

スコア12648

test CHANGED
@@ -68,37 +68,35 @@
68
68
 
69
69
  while(t->next != NULL) {
70
70
 
71
+ //ソートした最大値と比較
72
+
73
+ if(t->element <= t->next->element) { //移動の必要無し
74
+
75
+ t = t->next;
76
+
77
+ continue;
78
+
79
+ }
80
+
71
- //tまで挿入位置を探す
81
+ //挿入位置を探す(必ずある)
72
82
 
73
83
  cell *p = L->head;
74
84
 
75
- for( ; p!=t; p=p->next) {
76
-
77
- if(t->next->element < p->next->element) break;
85
+ for(; t->next->element > p->next->element; p=p->next);
78
-
79
- }
80
86
 
81
87
 
82
88
 
83
- if(p != t) { //挿入位置発見
89
+ cell *next = t->next->next;
84
90
 
85
- cell *next = t->next->next;
91
+ //挿入
86
92
 
87
- //挿入
93
+ t->next->next = p->next;
88
94
 
89
- t->next->next = p->next;
95
+ p->next = t->next;
90
96
 
91
- p->next = t->next;
97
+ //移動させたcellに繋がっていた元のポインタを付け替え
92
98
 
93
- //移動させたcellに繋がっていた元のポインタを付け替え
94
-
95
- t->next = next;
99
+ t->next = next;
96
-
97
- } else { //移動無し
98
-
99
- t = t->next;
100
-
101
- }
102
100
 
103
101
  }
104
102
 

3

コメント修正

2019/05/16 07:55

投稿

jimbe
jimbe

スコア12648

test CHANGED
@@ -90,7 +90,7 @@
90
90
 
91
91
  p->next = t->next;
92
92
 
93
- //元のtに繋がるポインタを付け替え
93
+ //移動させたcellに繋がっていた元のポインタを付け替え
94
94
 
95
95
  t->next = next;
96
96
 

2

t を p と同じ動き(対象の一つ前を保持)をするようにしました

2019/05/15 16:15

投稿

jimbe
jimbe

スコア12648

test CHANGED
@@ -66,43 +66,37 @@
66
66
 
67
67
 
68
68
 
69
- cell *prev = t;
70
-
71
- t = t->next;
69
+ while(t->next != NULL) {
72
-
73
- for(cell *next=NULL; t!=NULL; t=next) {
74
-
75
- next = t->next; //次のcell位置を保存しておく
76
-
77
-
78
70
 
79
71
  //tまで挿入位置を探す
80
72
 
81
73
  cell *p = L->head;
82
74
 
83
- for( ; p->next!=t; p=p->next) {
75
+ for( ; p!=t; p=p->next) {
84
76
 
85
- if(t->element < p->next->element) break;
77
+ if(t->next->element < p->next->element) break;
86
78
 
87
79
  }
88
80
 
89
81
 
90
82
 
91
- if(p->next != t) { //挿入位置発見
83
+ if(p != t) { //挿入位置発見
84
+
85
+ cell *next = t->next->next;
92
86
 
93
87
  //挿入
94
88
 
95
- t->next = p->next;
89
+ t->next->next = p->next;
96
90
 
97
- p->next = t;
91
+ p->next = t->next;
98
92
 
99
93
  //元のtに繋がるポインタを付け替え
100
94
 
101
- prev->next = next;
95
+ t->next = next;
102
96
 
103
- } else { //t は現在位置でOK
97
+ } else { //移動無し
104
98
 
105
- prev = t;
99
+ t = t->next;
106
100
 
107
101
  }
108
102
 

1

付け替え時のループを無くしました

2019/05/15 16:08

投稿

jimbe
jimbe

スコア12648

test CHANGED
@@ -66,6 +66,8 @@
66
66
 
67
67
 
68
68
 
69
+ cell *prev = t;
70
+
69
71
  t = t->next;
70
72
 
71
73
  for(cell *next=NULL; t!=NULL; t=next) {
@@ -96,9 +98,11 @@
96
98
 
97
99
  //元のtに繋がるポインタを付け替え
98
100
 
99
- for(p=t; p->next!=t; p=p->next);
101
+ prev->next = next;
100
102
 
103
+ } else { //t は現在位置でOK
104
+
101
- p->next = next;
105
+ prev = t;
102
106
 
103
107
  }
104
108