C言語のバブルソートアルゴリズムとコード

バブルソートは、明確なアイデアと簡潔なコードを備えたソートアルゴリズムの一種で、大学生向けのコンピューターコースでよく使用されます。

「バブル」という名前は、より大きな要素が交換を通じてシーケンスの先頭にゆっくりと「浮く」という事実に由来しており、そのためこの名前が付けられています。

これは、小さいものから大きいものへの並べ替えの例です。

基本的な考え方と例

バブル ソートの基本的な考え方は、2 つの隣接する数値を継続的に比較し、大きい要素が後へ戻り続けることです。 1 回の比較の後、最大の数値が選択され、2 回目の比較の後、2 番目に大きい数値が選択されます。

以下はバブルソート3・2・4・1の説明です。

1回目のソート処理
3 2 4 1 (最初)
2 3 4 2 (3と2を比較、交換)
2 3 4 1 (3と4を比較、交換なし)
2 3 1 4 (4を比較)と 1、交換)
最初のラウンドが終了し、最大の番号 4 がすでに終了しているため、2 回目の並べ替えラウンドでは最初の 3 つの数字を再度比較するだけで済みます。

2回目の選別処理
2 3 1 4 (1回目の選別結果)
2 3 1 4(2と3を比較、交換なし)
2 1 3 4(3と1を比較、交換
2回目終了) 、2 番目に大きい数値はすでに最後から 2 番目の位置にあるため、3 ラウンド目では最初の 2 つの要素を比較するだけで済みます

3 ラウンド目の並べ替えプロセス
2 1 3 4 (2 回目の並べ替え結果)
1 2 3 4 (2 と 1 を比較、交換)
この時点でソートは終了です

アルゴリズムの概要と実装

N 個の要素を持つ配列 R[n] について、最大 N-1 ラウンドの比較を実行します。 ;

最初のラウンドでは、(R[1]、R[2])、(R[2]、R[3])、(R[3]、R[4]) を 1 つずつ比較します。 (R[N-1], R[ N]); 最大の要素が R[N] に移動されます

2 番目のラウンドでは、(R[1], R[2])、(R[2]) を比較します。 ], R[3]), ( R[3], R[4]), … (R[N-2], R[N-1]); 1] .
配列全体が小さい順にソートされるまで続きます。

バブルソートの一般的な実装方法は、配列がソートされているかどうかに関係なく実行されます。 . N-1 ラウンドの比較。最適化された実装は、配列がソートされたときに比較を早期に終了し、アルゴリズムの時間の複雑さを軽減します。関連記事は、PHP 中国語 Web サイトにご注意ください