次の配列があるとします。| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
上記の配列を、右側がすべて 1、左側が 0 になるように並べ替える必要があります。
私は C++ で 2 つのアルゴリズムを考え出しました。
1つ目:
for(i = 0; i < n; i++) {
if(a[i] == 1 && i != n - 1) {
for(j = i + 1; j < n; j++) {
if(a[j] == 0) {
temp = a[j];
a[i] = a[j];
a[j] = temp;
break;
}
}
}
}
2つ目:
int x = 0;
for(i = 0; i < n; i++) {
if(a[i] == 1) {
for(j = n-x-1; j >= 0; j--) {
if(a[j] == 0) {
temp = a[j];
a[i] = a[j];
a[j] = temp;
x++;
break;
}
}
if(x > n / 2)
break;
}
両方の時間計算量を教えてください。また、どちらがより優れたパフォーマンスを発揮するかについても、説明付きのより優れたアルゴリズムを提案してくれます。ありがとう。