データ構造--発泡体の並べ替え
泡の並べ替え
交換並べ替えの基本的な考え方は、2つの並べ替え記録のキーワードを比較し、2つの記録の順序が逆であることを発見した時に交換し、逆順序の記録がないまで.
交換並べ替えの基本的な考え方を適用した主な並べ替え方法は,発泡体秩序化と高速秩序化である.
泡の並べ替え
1、並べ替え方法
並べ替えられた記録配列R[1.n]を垂直に並べ、各記録R[i]を重量R[i].keyの気泡とみなす.軽い気泡は重い気泡の下ではいけないという原則に基づいて、下から上へ配列Rを走査します.この原則に反する軽い気泡をスキャンすると、それを上へ「浮遊」させます.このように繰り返して、最後の二つの気泡が上にあるまで、重いものは下にある.
(1)初期
R[1.n]は無秩序領域です.
(2)第一スキャン
無秩序領域の底から上に向かって隣接する二つの気泡の重さを順次比較し、軽者が下、重量者が上にいると発見されたら、両者の位置を交換する.すなわち、順番に(R[n],R[n-1]),(R[n-1],R[n-2],…,(R[2],R[1])を比較します.各バブル(R[j＋1],R[j])については、R[j＋1].key＜R[j].keyであれば、R[j＋1]およびR[j]の内容が交換される.
第1のスキャンが完了すると、「最も軽い」気泡はこの区間の上部に漂着し、即ちキーワードが最小の記録は最高位置R[1]に置かれる.
(3)第二のスキャン
R［2.2.n］をスキャンします.スキャンが完了すると、R[2]の位置に“次軽”の気泡が浮遊します.
最後に、n-1回のスキャンによって、秩序ゾーンR[1.n]が得られます.
注意:
i番目のスキャンの場合、R[1.i-1]とR[i.n]はそれぞれ現在の順序領域と無秩序領域となります.スキャンは無秩序エリアの底から上に進みます.スキャンが完了すると、このエリアの中で最も軽い気泡が上部位置R[i]に漂着し、結果としてR[1.i]が新たな秩序領域に変化します.
2、泡並べ替えプロセスの例
キーワードシーケンスが49 38 65,9776,27,49のファイルを発泡的に並べ替えるプロセス【動画ショーを参照】
3、並べ替えアルゴリズム
(1)分析
順序付けごとに気泡が秩序領域に増加したので、n−1の順序付け後、秩序領域にn−1の気泡があり、無秩序領域における気泡の重さは常に秩序領域における気泡の重さに等しいので、全体の発泡秩序化過程はn−1の順序付けが必要となることが多い.
ある順序で気泡位置の交換が見つからない場合、順序付けされている無秩序領域のすべての気泡が軽率者の上に満足していることを示し、重層が下にあるという原則から、発泡体順序付けプロセスはこの順序の後に終了することができる.このため、次のアルゴリズムでは、各並べ替えが開始される前に、まずFALSEにセットするブール量exchangeを導入する.順序付け中に交換が発生した場合、TRUEにセットする.各並べ替えが終わった時にexchangeを確認し、もし交換がなかったらアルゴリズムを終了し、次の並べ替えは行わない.
(2)具体的なアルゴリズム
void BubleSort(SeqList R)
{/R(l.n)は順序付けされているファイルで、下から上へスキャンして、Rに対して発泡的にソートします.
int i,j
Boolean exchange//トレードマーク
for(i=1;i＜n;i+){/最大n-1の並べ替えを行います.
exchange=FALSE//今回のソート開始前に、交換フラグは偽であるべきです.
for(j=n-1;j>=i;j--)/現在の無秩序領域R[i.n]は下から上へスキャンされます.
if(R[j＋1].key R[0]=R[j+1]、//R[0]は歩哨兵ではなく、一時預かりユニットを作るだけです.
R[j＋1]=R[j]
R[j]=R[0];
exchange＝TRUE;／交換が発生したので、交換フラグを真に設定する.
}
if(!exchange)//今回の順序は交換が発生していません.アルゴリズムを事前に終了します.
return;
}//endfor(外循環)
}//BbleSort
4、アルゴリズム分析
(1)アルゴリズムの最適時間複雑度
ファイルの初期状態が順であれば、1回のスキャンで並べ替えが完了します.必要なキーワードの比較回数Cと記録移動回数Mは最小値になります.
Cmin=n-1
Mmin=0です
泡の並べ替えに最適な時間複雑度はO(n)であった.
(2)アルゴリズムの最悪時間複雑度
初期ファイルが逆順であれば、n-1の並べ替えが必要です.並べ替えごとにn-iのキーワードの比較(1≦i≦n-1)を行い、比較ごとに3回の記録を移動して交換記録位置に到達しなければなりません.この場合、比較と移動回数は最大値になります.
Cmax=n(n-1)/2=O(n 2)
Mmax=3 n(n-1)/2=O(n 2)
泡並べ替えの最悪時間複雑度はO(n 2)である.
(3)アルゴリズムの平均時間複雑度はO(n 2)である.
泡並べ替えは必ずしもn-1回とは限らないが、記録移動回数が多いため、平均時間性能は直接挿入ソートに比べてかなり劣っている.
(4)アルゴリズムの安定性
泡の並べ替えはその場で並べ替えられ、安定しています.
5、アルゴリズムの改善
上記の泡立ちランキングは以下のように改善することができます.
(1)最後の交換で発生した位置lastExchangeの発泡順位を覚えてください.
各スキャンにおいて、最後の交換が発生した位置lastExchangeを覚えてください.次の順序付けが開始されると、R[1.lastExchange-1]は順序ゾーンであり、R[lastExchange.n]は無秩序ゾーンです.このように、順序付けは現在の順序領域に複数の記録を拡張し、順序付けの回数を減らすことができます.【練習問題を参照】.
(2)スキャン方向の発泡体の並べ替えを変更する
①発泡秩序の非対称性
順序付けが一度にスキャンできた場合:
最も軽い気泡だけがR［n］の位置にあり、残りの気泡は全て秩序化されているので、一度の走査だけで並べ替えができます.
【例】初期キーワードシーケンス12、18、42、44、45、67、94、10は、1回のスキャンのみである.
順序付けを完了するためにn-1回のスキャンが必要です.
一番重い気泡だけがR［1］の位置にあり、残りの気泡は全て順序付けされている場合、依然としてn−1回の走査をしなければ並べ替えができない.
【例】初期キーワードシーケンス:94,10,12,18,42,44,45,67は7回のスキャンが必要です.
②非対称性の原因
各スキャンは最重の気泡を一つの位置だけ沈下させることができますので、先端にある最重の気泡を底部まで沈下させる場合は、n-1回のスキャンが必要です.
③非対称性を改善する方法
並べ替え中にスキャン方向を交互に変えて非対称性を改善します.
アルゴリズムプログラム
交換並べ替えの基本的な考え方は、2つの並べ替え記録のキーワードを比較し、2つの記録の順序が逆であることを発見した時に交換し、逆順序の記録がないまで.
交換並べ替えの基本的な考え方を適用した主な並べ替え方法は,発泡体秩序化と高速秩序化である.
泡の並べ替え
1、並べ替え方法
並べ替えられた記録配列R[1.n]を垂直に並べ、各記録R[i]を重量R[i].keyの気泡とみなす.軽い気泡は重い気泡の下ではいけないという原則に基づいて、下から上へ配列Rを走査します.この原則に反する軽い気泡をスキャンすると、それを上へ「浮遊」させます.このように繰り返して、最後の二つの気泡が上にあるまで、重いものは下にある.
(1)初期
R[1.n]は無秩序領域です.
(2)第一スキャン
無秩序領域の底から上に向かって隣接する二つの気泡の重さを順次比較し、軽者が下、重量者が上にいると発見されたら、両者の位置を交換する.すなわち、順番に(R[n],R[n-1]),(R[n-1],R[n-2],…,(R[2],R[1])を比較します.各バブル(R[j＋1],R[j])については、R[j＋1].key＜R[j].keyであれば、R[j＋1]およびR[j]の内容が交換される.
第1のスキャンが完了すると、「最も軽い」気泡はこの区間の上部に漂着し、即ちキーワードが最小の記録は最高位置R[1]に置かれる.
(3)第二のスキャン
R［2.2.n］をスキャンします.スキャンが完了すると、R[2]の位置に“次軽”の気泡が浮遊します.
最後に、n-1回のスキャンによって、秩序ゾーンR[1.n]が得られます.
注意:
i番目のスキャンの場合、R[1.i-1]とR[i.n]はそれぞれ現在の順序領域と無秩序領域となります.スキャンは無秩序エリアの底から上に進みます.スキャンが完了すると、このエリアの中で最も軽い気泡が上部位置R[i]に漂着し、結果としてR[1.i]が新たな秩序領域に変化します.
2、泡並べ替えプロセスの例
キーワードシーケンスが49 38 65,9776,27,49のファイルを発泡的に並べ替えるプロセス【動画ショーを参照】
3、並べ替えアルゴリズム
(1)分析
順序付けごとに気泡が秩序領域に増加したので、n−1の順序付け後、秩序領域にn−1の気泡があり、無秩序領域における気泡の重さは常に秩序領域における気泡の重さに等しいので、全体の発泡秩序化過程はn−1の順序付けが必要となることが多い.
ある順序で気泡位置の交換が見つからない場合、順序付けされている無秩序領域のすべての気泡が軽率者の上に満足していることを示し、重層が下にあるという原則から、発泡体順序付けプロセスはこの順序の後に終了することができる.このため、次のアルゴリズムでは、各並べ替えが開始される前に、まずFALSEにセットするブール量exchangeを導入する.順序付け中に交換が発生した場合、TRUEにセットする.各並べ替えが終わった時にexchangeを確認し、もし交換がなかったらアルゴリズムを終了し、次の並べ替えは行わない.
(2)具体的なアルゴリズム
void BubleSort(SeqList R)
{/R(l.n)は順序付けされているファイルで、下から上へスキャンして、Rに対して発泡的にソートします.
int i,j
Boolean exchange//トレードマーク
for(i=1;i＜n;i+){/最大n-1の並べ替えを行います.
exchange=FALSE//今回のソート開始前に、交換フラグは偽であるべきです.
for(j=n-1;j>=i;j--)/現在の無秩序領域R[i.n]は下から上へスキャンされます.
if(R[j＋1].key
R[j＋1]=R[j]
R[j]=R[0];
exchange＝TRUE;／交換が発生したので、交換フラグを真に設定する.
}
if(!exchange)//今回の順序は交換が発生していません.アルゴリズムを事前に終了します.
return;
}//endfor(外循環)
}//BbleSort
4、アルゴリズム分析
(1)アルゴリズムの最適時間複雑度
ファイルの初期状態が順であれば、1回のスキャンで並べ替えが完了します.必要なキーワードの比較回数Cと記録移動回数Mは最小値になります.
Cmin=n-1
Mmin=0です
泡の並べ替えに最適な時間複雑度はO(n)であった.
(2)アルゴリズムの最悪時間複雑度
初期ファイルが逆順であれば、n-1の並べ替えが必要です.並べ替えごとにn-iのキーワードの比較(1≦i≦n-1)を行い、比較ごとに3回の記録を移動して交換記録位置に到達しなければなりません.この場合、比較と移動回数は最大値になります.
Cmax=n(n-1)/2=O(n 2)
Mmax=3 n(n-1)/2=O(n 2)
泡並べ替えの最悪時間複雑度はO(n 2)である.
(3)アルゴリズムの平均時間複雑度はO(n 2)である.
泡並べ替えは必ずしもn-1回とは限らないが、記録移動回数が多いため、平均時間性能は直接挿入ソートに比べてかなり劣っている.
(4)アルゴリズムの安定性
泡の並べ替えはその場で並べ替えられ、安定しています.
5、アルゴリズムの改善
上記の泡立ちランキングは以下のように改善することができます.
(1)最後の交換で発生した位置lastExchangeの発泡順位を覚えてください.
各スキャンにおいて、最後の交換が発生した位置lastExchangeを覚えてください.次の順序付けが開始されると、R[1.lastExchange-1]は順序ゾーンであり、R[lastExchange.n]は無秩序ゾーンです.このように、順序付けは現在の順序領域に複数の記録を拡張し、順序付けの回数を減らすことができます.【練習問題を参照】.
(2)スキャン方向の発泡体の並べ替えを変更する
①発泡秩序の非対称性
順序付けが一度にスキャンできた場合:
最も軽い気泡だけがR［n］の位置にあり、残りの気泡は全て秩序化されているので、一度の走査だけで並べ替えができます.
【例】初期キーワードシーケンス12、18、42、44、45、67、94、10は、1回のスキャンのみである.
順序付けを完了するためにn-1回のスキャンが必要です.
一番重い気泡だけがR［1］の位置にあり、残りの気泡は全て順序付けされている場合、依然としてn−1回の走査をしなければ並べ替えができない.
【例】初期キーワードシーケンス:94,10,12,18,42,44,45,67は7回のスキャンが必要です.
②非対称性の原因
各スキャンは最重の気泡を一つの位置だけ沈下させることができますので、先端にある最重の気泡を底部まで沈下させる場合は、n-1回のスキャンが必要です.
③非対称性を改善する方法
並べ替え中にスキャン方向を交互に変えて非対称性を改善します.
アルゴリズムプログラム
void bubble(int n,int[])
// (n^2)
{
int i,j,tmp,flag;
for(i=0;i<n-1;i++)
{
flag=false;
for(j=n-1;j>i;j--)
{
if(a[j-1]>a[j])
{
tmp=a[j];
a[j]=a[j-1];
a[j-1]=tmp;
flag=true;
}
}
if(!flag)return;
}
}