第９話 グループ分けしない場合の並び換え
今回は、
6 8 3 4 8 2
をグループに分けないで、並び換えてみましょう。
１巡目
6 8 3 4 8 2 ①
6 8 3 4 8 2
6 8 3 4 8 2 ②
6 3 8 4 8 2 ③
6 3 8 4 8 2 ④
6 3 4 8 8 2 ⑤
6 3 4 8 8 2 ⑥
6 3 4 8 8 2
6 3 8 4 8 2 ⑦
6 3 8 4 2 8 ⑧
２巡目
6 3 8 4 2 8 ⑨
3 6 8 4 2 8 ⑩
3 6 8 4 2 8 ⑪
3 6 8 4 2 8
3 6 8 4 2 8 ⑫
3 6 4 8 2 8 ⑬
3 6 4 8 2 8 ⑭
3 6 4 2 8 8 ⑮
3 6 4 2 8 8 ⑯
３巡目
3 6 4 2 8 8 ⑰
3 6 4 2 8 8
3 6 4 2 8 8 ⑱
3 4 6 2 8 8 ⑲
3 4 6 2 8 8 ⑳
3 4 2 6 8 8 ㉑
3 4 2 6 8 8
3 4 2 6 8 8 ㉒
3 4 2 6 8 8
４巡目
3 4 2 6 8 8 ㉓
3 4 2 6 8 8
3 4 2 6 8 8 ㉔
3 2 4 6 8 8 ㉕
3 2 4 6 8 8 ㉖
3 2 4 6 8 8
3 2 4 6 8 8 ㉗
3 2 4 6 8 8
3 2 4 6 8 8 ㉘
3 2 4 6 8 8
５巡目
3 2 4 6 8 8 ㉙
2 3 4 6 8 8 ㉚
2 3 4 6 8 8 ㉛
2 3 4 6 8 8
2 3 4 6 8 8 ㉜
2 3 4 6 8 8
2 3 4 6 8 8 ㉝
2 3 4 6 8 8
2 3 4 6 8 8 ㉞
2 3 4 6 8 8
６巡目
2 3 4 6 8 8 ㉟
2 3 4 6 8 8
2 3 4 6 8 8 ㊱
2 3 4 6 8 8
2 3 4 6 8 8 ㊲
2 3 4 6 8 8
2 3 4 6 8 8 ㊳
2 3 4 6 8 8
2 3 4 6 8 8 ㊴
2 3 4 6 8 8
１回も交換が発生せず、並び換え終了。
今回のステップ数は３９回でした。
２グループに分けた場合が３２回でしたから、
グループに分けた方がステップ数が少ないことになります。
さらに、交換になる場合、
void g(int* x){
int i,cn;
while(1){
cn=0;
for(i=0;i<9999;i++){
if(x[i]>x[i+1]){
int w;
w=x[i];
x[i]=x[i+1];
x[i+1]=w;
cn++;
}
}
if(cn==0)break;
}
}
実際には３つのステップを踏んでいますから、
交換の場合は３とカウントすべきです。
交換になった回数は、２グループの場合に６回であり、
グループに分けない場合に９回です。
ですから、正確にはステップ数は、
２グループのとき、
３２－６＋６×２＝３６
グループに分けないとき、
３９－９＋９×２＝４８
です。
並び換える個数が多いと、
思考実験も煩雑になり、行数も増えてしまいますから、
記述しませんが、
個数が多いほど、ステップ数が減ることが予想されます。
さらに、マルチスレッドの講ですでに学習しましたように、
物理CPUが４個、論理CPUが８個の場合には、
６スレッド当たりでCPU使用率が１００％になりますから、
６グループに分けるのが最も効率的です。
６グループに分けて、
それぞれのグループ内の並び換えは各タスク（スレッド）に担当させれば、
並び換えのかなりの高速化が期待できます。
では、皆さんマルチスレッド化に挑戦してみて下さい。
