回答編集履歴

5

コメント修正

2020/11/12 08:36

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -144,19 +144,19 @@
144
144
 
145
145
 
146
146
 
147
- + i = 0;
147
+ + i = j = 0; // j は親、i は親子のうち小さいもの
148
148
 
149
149
  + while (2*j+1 < num) { // 子がヒープの範囲内
150
150
 
151
- + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
151
+ + if (h[2*j+1] < h[j]) i = 2*j+1; // 左の子が親より小さい
152
152
 
153
153
  + if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
154
154
 
155
- + // 右の子が親より小さい
155
+ + // 右の子が最も小さい
156
156
 
157
157
  + if (i == j) break; // 親が子より小さい
158
158
 
159
- + swap(&h[i], &h[j]); // 小さい子(両方なら右の子)を親と交換
159
+ + swap(&h[i], &h[j]); // 小さいほうの子を親と交換
160
160
 
161
161
  + j = i; // 子を新しい親とする
162
162
 

4

while の条件を修正

2020/11/12 08:36

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -146,7 +146,7 @@
146
146
 
147
147
  + i = 0;
148
148
 
149
- + while (2*(j+1) <= num) { // 子がヒープの範囲内
149
+ + while (2*j+1 < num) { // 子がヒープの範囲内
150
150
 
151
151
  + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
152
152
 

3

コードの修正

2020/11/12 07:50

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -146,9 +146,7 @@
146
146
 
147
147
  + i = 0;
148
148
 
149
- + while (1) {
150
-
151
- + if (2*(j+1) > num) break; // 子がヒープの範囲
149
+ + while (2*(j+1) <= num) { // 子がヒープの範囲
152
150
 
153
151
  + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
154
152
 

2

質問のコードの修正案を提示

2020/11/12 07:42

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -83,3 +83,119 @@
83
83
  }
84
84
 
85
85
  ```
86
+
87
+ **追記**
88
+
89
+ 元のコードの while だけを次のように修正すればよいでしょう。
90
+
91
+ ```diff
92
+
93
+ - while(i<num){
94
+
95
+ - //printf("j=%d i=%d\n",j,i);
96
+
97
+ - //printf("while中 \n");
98
+
99
+ - /*
100
+
101
+ - for(w=0;w<num;w++){
102
+
103
+ - printf("%d ",h[w]);
104
+
105
+ - }
106
+
107
+ - */
108
+
109
+ -
110
+
111
+ - if(h[j]>h[i]){ //親が子よりも大きい場合
112
+
113
+ - if(h[2*j+1]<h[2*(j+1)]){ //子の中で小さい方と交換すること
114
+
115
+ - //printf("h[2*j+1]=%d\n",h[2*j+1]);
116
+
117
+ - swap(&h[2*j+1],&h[j]);
118
+
119
+ - j=i;
120
+
121
+ - i=2*(j+1); //下の段へ
122
+
123
+ - }else{
124
+
125
+ - //printf("h[2*(j+1)]=%d\n",h[2*(j+1)]);
126
+
127
+ - swap(&h[2*(j+1)],&h[j]);
128
+
129
+ - j=i;
130
+
131
+ - i=2*(j+1);
132
+
133
+ - }
134
+
135
+ - }else{
136
+
137
+ - //printf("while出る\n");
138
+
139
+ - break;
140
+
141
+ - }
142
+
143
+ - }
144
+
145
+
146
+
147
+ + i = 0;
148
+
149
+ + while (1) {
150
+
151
+ + if (2*(j+1) > num) break; // 子がヒープの範囲外
152
+
153
+ + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
154
+
155
+ + if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
156
+
157
+ + // 右の子が親より小さい
158
+
159
+ + if (i == j) break; // 親が子より小さい
160
+
161
+ + swap(&h[i], &h[j]); // 小さい子(両方なら右の子)を親と交換
162
+
163
+ + j = i; // 子を新しい親とする
164
+
165
+ + }
166
+
167
+ ```
168
+
169
+ heap_sort関数の中で、int h[n]; を宣言していますが、
170
+
171
+ これは可変長配列で、コンパイラによってはこの機能をサポートしていません。
172
+
173
+
174
+
175
+ 質問のコードでは、h[0] が最小値になるヒープを構成し、h[0] を a[0] にコピー。
176
+
177
+ h[0] に h[n-1] をコピーし、長さが 1小さくなったヒープを再構成し、
178
+
179
+ 新しい最小値 h[0] を a[1] にコピー。
180
+
181
+ これを繰り返して、ソート結果を配列 a に入れています。
182
+
183
+
184
+
185
+ 次のようにしてもソートはできます。
186
+
187
+
188
+
189
+ h[0] が「最大値」になるヒープを構成し、h[0] を a[n-1] にコピー。
190
+
191
+ h[0] に h[n-1] をコピーし、長さが 1小さくなったヒープを再構成し、
192
+
193
+ 新しい「最大値」 h[0] を a[n-2] にコピー。
194
+
195
+ これを繰り返して、ソート結果が配列 a に入る。
196
+
197
+
198
+
199
+ こうすると、ヒープが小さくなるたびに最大値を後ろに置くことができます。
200
+
201
+ すなわち、元の配列 a をそのままソートでき、配列 h は要らないということです。

1

コードの修正

2020/11/12 07:38

投稿

kazuma-s
kazuma-s

スコア8224

test CHANGED
@@ -6,7 +6,7 @@
6
6
 
7
7
 
8
8
 
9
- #define swap(x, y) (t = x, x = y, y = t)
9
+ #define swap(x, y) (c = x, x = y, y = c)
10
10
 
11
11
 
12
12
 
@@ -14,11 +14,11 @@
14
14
 
15
15
  {
16
16
 
17
- int t, k = 0;
17
+ int c, i, j, k = 0;
18
18
 
19
19
  while (++k < n)
20
20
 
21
- for (int i, j = k; j > 0 && a[i = (j-1)/2] < a[j]; j = i)
21
+ for (j = k; j > 0 && a[i = (j-1)/2] < a[j]; j = i)
22
22
 
23
23
  swap(a[i], a[j]);
24
24
 
@@ -26,9 +26,9 @@
26
26
 
27
27
  swap(a[0], a[k]);
28
28
 
29
- for (int i = 0, j = 0; ; j = i) {
29
+ for (i = j = 0; ; j = i) {
30
30
 
31
- int c = (j+1)*2; // c: right child of j
31
+ c = (j + 1) * 2; // c: right child of j
32
32
 
33
33
  if (c > k) break;
34
34