teratail header banner
teratail header banner
質問するログイン新規登録

回答編集履歴

5

コメント修正

2020/11/12 08:36

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -71,13 +71,13 @@
71
71
  - }
72
72
  - }
73
73
 
74
- + i = 0;
74
+ + i = j = 0; // j は親、i は親子のうち小さいもの
75
75
  + while (2*j+1 < num) { // 子がヒープの範囲内
76
- + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
76
+ + if (h[2*j+1] < h[j]) i = 2*j+1; // 左の子が親より小さい
77
77
  + if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
78
- + // 右の子が親より小さい
78
+ + // 右の子が最も小さい
79
79
  + if (i == j) break; // 親が子より小さい
80
- + swap(&h[i], &h[j]); // 小さい子(両方なら右の子)を親と交換
80
+ + swap(&h[i], &h[j]); // 小さいほうの子を親と交換
81
81
  + j = i; // 子を新しい親とする
82
82
  + }
83
83
  ```

4

while の条件を修正

2020/11/12 08:36

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -72,7 +72,7 @@
72
72
  - }
73
73
 
74
74
  + i = 0;
75
- + while (2*(j+1) <= num) { // 子がヒープの範囲内
75
+ + while (2*j+1 < num) { // 子がヒープの範囲内
76
76
  + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
77
77
  + if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
78
78
  + // 右の子が親より小さい

3

コードの修正

2020/11/12 07:50

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -72,8 +72,7 @@
72
72
  - }
73
73
 
74
74
  + i = 0;
75
- + while (1) {
76
- + if (2*(j+1) > num) break; // 子がヒープの範囲
75
+ + while (2*(j+1) <= num) { // 子がヒープの範囲
77
76
  + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
78
77
  + if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
79
78
  + // 右の子が親より小さい

2

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

2020/11/12 07:42

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -40,4 +40,62 @@
40
40
 
41
41
  return 0;
42
42
  }
43
- ```
43
+ ```
44
+ **追記**
45
+ 元のコードの while だけを次のように修正すればよいでしょう。
46
+ ```diff
47
+ - while(i<num){
48
+ - //printf("j=%d i=%d\n",j,i);
49
+ - //printf("while中 \n");
50
+ - /*
51
+ - for(w=0;w<num;w++){
52
+ - printf("%d ",h[w]);
53
+ - }
54
+ - */
55
+ -
56
+ - if(h[j]>h[i]){ //親が子よりも大きい場合
57
+ - if(h[2*j+1]<h[2*(j+1)]){ //子の中で小さい方と交換すること
58
+ - //printf("h[2*j+1]=%d\n",h[2*j+1]);
59
+ - swap(&h[2*j+1],&h[j]);
60
+ - j=i;
61
+ - i=2*(j+1); //下の段へ
62
+ - }else{
63
+ - //printf("h[2*(j+1)]=%d\n",h[2*(j+1)]);
64
+ - swap(&h[2*(j+1)],&h[j]);
65
+ - j=i;
66
+ - i=2*(j+1);
67
+ - }
68
+ - }else{
69
+ - //printf("while出る\n");
70
+ - break;
71
+ - }
72
+ - }
73
+
74
+ + i = 0;
75
+ + while (1) {
76
+ + if (2*(j+1) > num) break; // 子がヒープの範囲外
77
+ + if (h[2*j+1] < h[i]) i = 2*j+1; // 左の子が親より小さい
78
+ + if (2*(j+1) < num && h[2*(j+1)] < h[i]) i = 2*(j+1);
79
+ + // 右の子が親より小さい
80
+ + if (i == j) break; // 親が子より小さい
81
+ + swap(&h[i], &h[j]); // 小さい子(両方なら右の子)を親と交換
82
+ + j = i; // 子を新しい親とする
83
+ + }
84
+ ```
85
+ heap_sort関数の中で、int h[n]; を宣言していますが、
86
+ これは可変長配列で、コンパイラによってはこの機能をサポートしていません。
87
+
88
+ 質問のコードでは、h[0] が最小値になるヒープを構成し、h[0] を a[0] にコピー。
89
+ h[0] に h[n-1] をコピーし、長さが 1小さくなったヒープを再構成し、
90
+ 新しい最小値 h[0] を a[1] にコピー。
91
+ これを繰り返して、ソート結果を配列 a に入れています。
92
+
93
+ 次のようにしてもソートはできます。
94
+
95
+ h[0] が「最大値」になるヒープを構成し、h[0] を a[n-1] にコピー。
96
+ h[0] に h[n-1] をコピーし、長さが 1小さくなったヒープを再構成し、
97
+ 新しい「最大値」 h[0] を a[n-2] にコピー。
98
+ これを繰り返して、ソート結果が配列 a に入る。
99
+
100
+ こうすると、ヒープが小さくなるたびに最大値を後ろに置くことができます。
101
+ すなわち、元の配列 a をそのままソートでき、配列 h は要らないということです。

1

コードの修正

2020/11/12 07:38

投稿

kazuma-s
kazuma-s

スコア8222

answer CHANGED
@@ -2,18 +2,18 @@
2
2
  ```C
3
3
  #include <stdio.h>
4
4
 
5
- #define swap(x, y) (t = x, x = y, y = t)
5
+ #define swap(x, y) (c = x, x = y, y = c)
6
6
 
7
7
  void heap_sort(int a[], int n)
8
8
  {
9
- int t, k = 0;
9
+ int c, i, j, k = 0;
10
10
  while (++k < n)
11
- for (int i, j = k; j > 0 && a[i = (j-1)/2] < a[j]; j = i)
11
+ for (j = k; j > 0 && a[i = (j-1)/2] < a[j]; j = i)
12
12
  swap(a[i], a[j]);
13
13
  while (--k > 0) {
14
14
  swap(a[0], a[k]);
15
- for (int i = 0, j = 0; ; j = i) {
15
+ for (i = j = 0; ; j = i) {
16
- int c = (j+1)*2; // c: right child of j
16
+ c = (j + 1) * 2; // c: right child of j
17
17
  if (c > k) break;
18
18
  if (a[c-1] > a[i]) i = c-1; // c-1: left child of j
19
19
  if (c < k && a[c] > a[i]) i = c;