回答編集履歴
3
追記
answer
CHANGED
|
@@ -106,4 +106,122 @@
|
|
|
106
106
|
３要素の配列でためしていますが、ご自身で、もっと要素数が多いときに常にソート結果は同じなのか、計算量の差はどのくらい異なるのかなどを調べてみることをお勧めします。
|
|
107
107
|
|
|
108
108
|
[100, 99, ... 1] の配列をソートして比較すると、きっと驚くだろうと予想してます。(私は驚きました)
|
|
109
|
-
もし実際に比較してみていただけたなら結果をコメントにでも書いてもらえれば幸いです。
|
|
109
|
+
もし実際に比較してみていただけたなら結果をコメントにでも書いてもらえれば幸いです。
|
|
110
|
+
|
|
111
|
+
追記
|
|
112
|
+
上のコードの quickB は質問文のものと違ってました。
|
|
113
|
+
修正したコードと実行結果を示します。
|
|
114
|
+
```c
|
|
115
|
+
#include <stdio.h>
|
|
116
|
+
|
|
117
|
+
#define swap(type, x, y) do { type t = x; x = y; y = t; swap_count++;} while (0)
|
|
118
|
+
|
|
119
|
+
int swap_count;
|
|
120
|
+
int call_count;
|
|
121
|
+
|
|
122
|
+
/*--- クイックソート ---*/
|
|
123
|
+
void quickA(int a[], int left, int right)
|
|
124
|
+
{
|
|
125
|
+
int pl = left; /* 左カーソル */
|
|
126
|
+
int pr = right; /* 右カーソル */
|
|
127
|
+
int x = a[(pl + pr) / 2]; /* 枢軸は中央の要素 */
|
|
128
|
+
|
|
129
|
+
call_count++;
|
|
130
|
+
do {
|
|
131
|
+
while (a[pl] < x) pl++;
|
|
132
|
+
while (a[pr] > x) pr--;
|
|
133
|
+
if (pl <= pr) {
|
|
134
|
+
swap(int, a[pl], a[pr]);
|
|
135
|
+
pl++;
|
|
136
|
+
pr--;
|
|
137
|
+
}
|
|
138
|
+
} while (pl <= pr);
|
|
139
|
+
|
|
140
|
+
if (left < pr) quickA(a, left, pr);
|
|
141
|
+
if (pl < right) quickA(a, pl, right);
|
|
142
|
+
}
|
|
143
|
+
|
|
144
|
+
void quickB(int a[], int left, int right)
|
|
145
|
+
{
|
|
146
|
+
int pl = left; /* 左カーソル */
|
|
147
|
+
int pr = right; /* 右カーソル */
|
|
148
|
+
int x = a[(pl + pr) / 2]; /* 枢軸は中央の要素 */
|
|
149
|
+
|
|
150
|
+
call_count++;
|
|
151
|
+
while (pl <= pr) {
|
|
152
|
+
while (a[pl] < x) pl++;
|
|
153
|
+
while (a[pr] > x) pr--;
|
|
154
|
+
if (pl <= pr) {
|
|
155
|
+
swap(int, a[pl], a[pr]);
|
|
156
|
+
pl++;
|
|
157
|
+
pr--;
|
|
158
|
+
};
|
|
159
|
+
}
|
|
160
|
+
if (left < pr) quickB(a, left, pr);
|
|
161
|
+
if (pl < right) quickB(a, pl, right);
|
|
162
|
+
}
|
|
163
|
+
|
|
164
|
+
void copy_to_a(int src[], int a[], int size) {
|
|
165
|
+
for (int i = 0; i < size; i++) {
|
|
166
|
+
a[i] = src[i];
|
|
167
|
+
}
|
|
168
|
+
}
|
|
169
|
+
|
|
170
|
+
void show_a(int a[], int size) {
|
|
171
|
+
for (int i = 0; i < size; i++) {
|
|
172
|
+
printf("%d ", a[i]);
|
|
173
|
+
}
|
|
174
|
+
printf(" swap_count(%d), call_count(%d)\n", swap_count, call_count);
|
|
175
|
+
}
|
|
176
|
+
|
|
177
|
+
int main(void) {
|
|
178
|
+
|
|
179
|
+
int test [][3] = {
|
|
180
|
+
{1, 2, 3},
|
|
181
|
+
{1, 3, 2},
|
|
182
|
+
{2, 1, 3},
|
|
183
|
+
{2, 3, 1},
|
|
184
|
+
{3, 1, 2},
|
|
185
|
+
{3, 2, 1}
|
|
186
|
+
};
|
|
187
|
+
|
|
188
|
+
for (int i = 0; i < 6; i++) {
|
|
189
|
+
int a[3];
|
|
190
|
+
|
|
191
|
+
printf("----------\n");
|
|
192
|
+
swap_count = call_count = 0;
|
|
193
|
+
show_a(test[i], 3);
|
|
194
|
+
|
|
195
|
+
copy_to_a(test[i], a, 3);
|
|
196
|
+
swap_count = call_count = 0;
|
|
197
|
+
quickA(a, 0, 2);
|
|
198
|
+
show_a(a, 3);
|
|
199
|
+
|
|
200
|
+
copy_to_a(test[i], a, 3);
|
|
201
|
+
swap_count = call_count = 0;
|
|
202
|
+
quickB(a, 0, 2);
|
|
203
|
+
show_a(a, 3);
|
|
204
|
+
}
|
|
205
|
+
|
|
206
|
+
int aa[100];
|
|
207
|
+
for (int i = 0; i < 100; i++) {
|
|
208
|
+
aa[i] = 100 - i;
|
|
209
|
+
}
|
|
210
|
+
swap_count = call_count = 0;
|
|
211
|
+
quickB(aa, 0, 99);
|
|
212
|
+
show_a(aa, 100);
|
|
213
|
+
|
|
214
|
+
for (int i = 0; i < 100; i++) {
|
|
215
|
+
aa[i] = 100 - i;
|
|
216
|
+
}
|
|
217
|
+
swap_count = call_count = 0;
|
|
218
|
+
quickA(aa, 0, 99);
|
|
219
|
+
show_a(aa, 100);
|
|
220
|
+
|
|
221
|
+
|
|
222
|
+
return 0;
|
|
223
|
+
}
|
|
224
|
+
```
|
|
225
|
+
|
|
226
|
+
実行例
|
|
227
|
+
|
2
追記
answer
CHANGED
|
@@ -103,4 +103,7 @@
|
|
|
103
103
|
|
|
104
104
|
[3, 2, 1] をソートしたときに、ソート結果は同じですが、メソッドの呼び出し回数、swap の実行回数に差異があります。
|
|
105
105
|
|
|
106
|
-
３要素の配列でためしていますが、ご自身で、もっと要素数が多いときに常にソート結果は同じなのか、計算量の差はどのくらい異なるのかなどを調べてみることをお勧めします。
|
|
106
|
+
３要素の配列でためしていますが、ご自身で、もっと要素数が多いときに常にソート結果は同じなのか、計算量の差はどのくらい異なるのかなどを調べてみることをお勧めします。
|
|
107
|
+
|
|
108
|
+
[100, 99, ... 1] の配列をソートして比較すると、きっと驚くだろうと予想してます。(私は驚きました)
|
|
109
|
+
もし実際に比較してみていただけたなら結果をコメントにでも書いてもらえれば幸いです。
|
1
追記
answer
CHANGED
|
@@ -101,4 +101,6 @@
|
|
|
101
101
|
実行例
|
|
102
102
|
|
|
103
103
|
|
|
104
|
-
[3, 2, 1] をソートしたときに、ソート結果は同じですが、メソッドの呼び出し回数、swap の実行回数に差異があります。
|
|
104
|
+
[3, 2, 1] をソートしたときに、ソート結果は同じですが、メソッドの呼び出し回数、swap の実行回数に差異があります。
|
|
105
|
+
|
|
106
|
+
３要素の配列でためしていますが、ご自身で、もっと要素数が多いときに常にソート結果は同じなのか、計算量の差はどのくらい異なるのかなどを調べてみることをお勧めします。
|