バブルソートアルゴリズム

交換ソートの基本的な考え方は、ソート対象のレコードのキーワードをペアごとに比較し、2 つのレコードの順序が逆であることが判明した場合、レコード内にレコードがなくなるまで交換を実行します。逆の順序。

エクスチェンジソートの基本的な考え方を適用した主なソート方法は、バブルソートとクイックソートです。

バブルソート

1. ソート方法
ソートされたレコード配列 R[1..n] を縦に並べ、各レコード R[i] を R[i].key の重みを持つバブルとみなします。軽い泡は重い泡の下には存在できないという原則に従って、配列 R は下から上に走査されます。この原則に違反する軽い泡は上に「浮く」ことになります。最後の 2 つの泡が上部の軽い泡と下部の重い泡になるまで、これが繰り返されます。
(1)初期
R[1..n]は順序付けされていない領域です。

(2) 最初のスキャン
乱れた領域の下から上に向けて、隣接する 2 つの気泡の重さを比較し、軽い方が下にあり、重い方が上にあることが判明した場合は、位置を交換します。つまり、(R[n], R[n-1])、(R[n-1]、R[n-2])、...、(R[2]、R[1]) を比較します。シーケンス; 各ペア Bubble (R[j+1], R[j]) について、R[j+1].key 最初のスキャンが完了すると、「最も軽い」バブルが間隔の先頭に浮かび上がります。つまり、最小のキーワードを持つレコードが最も高い位置 R[1] に配置されます。

(3) 2回目のスキャン
R[2..n]をスキャンします。スキャンが完了すると、「2 番目に軽い」バブルが R[2] の位置に浮かび上がります...
最後に、n-1 回のスキャンの後、順序付けされた領域 R[1..n] を取得できます
注:
i 番目のスキャンのとき、R[1..i-1] と R[i..n] はそれぞれ現在の順序付けされた領域と順序付けされていない領域です。スキャンは依然として、乱れた領域の下部から領域の上部まで行われます。スキャンが完了すると、エリア内の最も明るいバブルが最上位の位置 R[i] に浮上し、その結果、R[1..i] が新しい順序付けされたエリアになります。

2. バブルソート処理の例
キーワード配列 49 38 65 97 76 13 27 49

3. ソートアルゴリズム
(1) 分析
各ソート処理にはバブルが追加されているためn-1 個のソートの後、順序付けされた領域には n-1 個のバブルが存在し、無秩序領域内のバブルの重量は常に順序付けられた領域内のバブルの重量以上になります。バブル ソート プロセス全体では、最大でも n-1 個のソート パスが必要です。
特定のソートパスでバブルの位置の交換が見つからない場合、ソートされる未順序領域内のすべてのバブルが上部の軽いバブルと下部の重いバブルの原則を満たしていることを意味します。ソートプロセスはこのパスでソートでき、その後終了します。このため、以下に示すアルゴリズムではブール交換が導入され、各並べ替えが開始される前に FALSE に設定されます。並べ替え中に交換が発生した場合は TRUE に設定します。交換は各ソート パスの最後にチェックされます。交換が発生しない場合、アルゴリズムは終了し、次のソート パスは実行されません。

(2) 特定のアルゴリズム
void BubbleSort(SeqList R)
{ //R (l..n) は、ボトムアップ スキャンを使用して、R
int i, j に対してバブル ソートを実行します。 Boolean Exchange; //交換フラグ
for(i=1;i Exchange=FALSE; //この並べ替えの前に交換フラグは false である必要があります。 starting
for (J = n-1; j & gt; = i; j---) // 現在の順序付けされていない領域をスキャン R [i..n]

🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜 🎜?{//Ex変更記録🎜 🎜 //交換が発生したため、交換フラグが true に設定されます 🎜 } . D} // endfor (外側のサイクル)}} // バブルソート🎜🎜。 🎜🎜🎜🎜🎜🎜🎜 その他のバブルソートアルゴリズム関連記事については、PHP を参照してください。中国語のサイトです！ 🎜