[バブルソート bubble sort] は、隣接する要素を連続して比較して交換することでソートを実現します。このプロセスは、バブルが底から上に上昇するようなものです。
バブルソートのプロセスは、要素の交換操作を使用してシミュレートすることができます：配列の最も左端から右に向かって順番に、隣接する要素のサイズを比較し、"左の要素 > 右の要素" の場合はそれらを交換します。トラバースが完了すると、最大の要素は配列の最も右端に移動します。
バブルソートのアルゴリズムの流れ：
- 最初に、n 個の要素に対して "バブル" を実行し、配列の最大の要素を正しい位置に交換します。
- 次に、残りの n-1 個の要素に対して "バブル" を実行し、2 番目に大きな要素を正しい位置に交換します。
- これを繰り返し、n-1 回の "バブル" の後、最初の n-1 個の大きな要素が正しい位置に交換されます。
- 残りの要素は必ず最小の要素であり、ソートする必要はないため、配列のソートが完了します。
/* バブルソート */
void BubbleSort(int[] nums) {
// 外側のループ：未ソートの範囲は [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
// 内側のループ：未ソートの範囲 [0, i] の最大要素を範囲の最右端に交換する
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// nums[j] と nums[j + 1] を交換する
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
}
}
}
}
効率の最適化：もしあるラウンドの "バブル" で交換操作が行われなかった場合、配列は既にソートされていることを意味し、結果を直接返すことができます。そのため、このような状況を監視するためにフラグ flag を追加することができます。フラグが現れた場合、すぐに結果を返します。
/* バブルソート（フラグの最適化）*/
void BubbleSortWithFlag(int[] nums) {
// 外側のループ：未ソートの範囲は [0, i]
for (int i = nums.Length - 1; i > 0; i--) {
bool flag = false; // フラグの初期化
// 内側のループ：未ソートの範囲 [0, i] の最大要素を範囲の最右端に交換する
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
// nums[j] と nums[j + 1] を交換する
(nums[j + 1], nums[j]) = (nums[j], nums[j + 1]);
flag = true; // 交換された要素を記録する
}
}
if (!flag) break; // このラウンドのバブルで要素が交換されなかった場合、直ちに終了する
}
}