3-2. 交換法（バブルソート）
本記事では、交換法（バブルソート）について解説します。
交換法の考え方
交換法（bubble sort ; バブルソート）とは、値が入っている配列について、片側の端から順番に隣り合う値を比較し、順番が逆になっていれば交換するという操作を、もう一方の端まで繰り返すという整列方法です。
配列の先頭を上、終わりを下というように考えてみると、小さい値が次第に上に上がっていくようにずれていきます。これが、水の入ったコップの中で、バブルが上に登っていく様子に似ているので、バブルソートと呼ばれます。
交換法の目的は、全ての要素を昇順に並べることです。この目的を達成するためには、1番目を最小値に並べ替えた後に、2～7番目の値を範囲として、同じ操作を繰り返します。すると、2番目の位置に、2～7番目の値中の最小値、つまり、全体で2番目に小さな値が入ることになります。それが終わったら、次は3～7番目を範囲とします。こうして、比較・交換する範囲を一つずつ狭めながら、最後は6番目と7番目の要素だけが範囲となるまで、同じことを繰り返していきます。そうすれば、最終的に歯全ての要素が正しい順番（昇順）に並ぶことになります。
交換法は、繰返しが二重になっているので、一般的に外側の繰返し回数を1周目、2周目と呼び、内側の繰り返し回数を1回目、2回目と区別します。
交換法は、隣同士の値を比較して、「整列したい順と大小関係が異なれば交換する」という単純な処理ですが、この単純な処理を繰り返すことによって、最終的にすべての値を昇順に並べることができます。
交換法（バブルソート）のアルゴリズム
スキャン処理
範囲の最後から、7番目、6番目の値、6番目と5番目というように、先頭の要素まで比較・交換する処理をスキャン処理といいます。走査ともいいます。
繰り返す条件と終了する条件
7未満の時は繰返し（継続）、7になったら終了するのですから、継続条件は7未満、つまり、n＜7 と記述できます。n ≦ 6 でも同じ結果になります。
※n=1 は先頭の要素
擬似言語でアルゴリズムを記述
n ← 1
while (n ＜ 7)
[n 番目から7番目の要素に対する「スキャン処理」を行う]
n ← n + 1
endwhile
スキャン処理のアルゴリズム
i 番目の値と比較・交換するのは、その隣の値ですから i - 1 番目です。
iの初期値を7として、iの値を1ずつ減少させながら、i番目とi-1番目の比較・交換を繰り返すということになります。そして、n番目の要素が範囲の左端ですから、この要素に対する比較・交換まで行われた時点で、スキャン処理は終了です。
つまり、n + 1 番目とn番目の比較・交換が行われたら終了ということになります。
スキャン処理をi番目とi-1番目の比較・交換を繰り返すと考えてきましたから、i = n+1 の比較・交換が行われた時点で終了となります。iの値は繰返しのたびに1ずつ減っていきますから、i = n + 1 の比較・交換が行われた後、 i=n となります。これが実際の終了条件です。
整列したい値が配列Ani入っているとすると、i番目の要素はA[i] となります。この条件で「スキャン処理」のアルゴリズムを擬似言語で表現します。
i ← 7
while (i ＞ n ) // n+1 番目とn番目の比較・交換を行ったら終わり
if (A[i - 1 ] ＞ A[i] // 大小順が逆か
[A[i-1] とA[i] を交換する]
endif
i ← i - 1 // 比較・交換を行う要素を一つ左へ
endwhile
上記アルゴリズムには問題があります。A[i -1] とA[i]の交換は、A[i-1] をA[i] に入れる操作で、データが上書きされてしまうという問題です。
これではデータの交換になりませんので、一工夫追加します。w という変数を使います。
① w ← A[i] // A[ i ] の値を、wに退避する
② A[i] ← A[i-1] // A[i - 1] の値を、A[i] に入れる
③ A[i-1] ← w (元のA[i] の値）をA[i-1] に入れる
工夫した後のアルゴリズムの操作
（A[i-1] とA[i]の初期値）
w ← A[i]
A[i] ← A[i-1]
A[i-1] ← w
※値の交換を行うときは、変数の一時退避用の変数が必要になります。
i ← 7
while (i ＞ n ) // n+1 番目とn番目の比較・交換を行ったら終わり
if (A[i - 1 ] ＞ A[i] // 大小順が逆か
w ← A[i]
A[i] ← A[i-1]
A[i-1] ← w
endif
i ← i - 1 // 比較・交換を行う要素を一つ左へ
endwhile
上記は、スキャン処理のアルゴリズムの完成形です。
バブルソートのアルゴリズムの仕上げ
n ← 1
while (n ＜ 7) // 7 は、例題におけるデータ数
i ← 7 // 7 は、例題におけるデータ数
while (i ＞n)
if (A[i -1] ＞ A[i])
w ← A[i]
A[i] ← A[i -1 ]
A[i-1] ← w
endif
i ← i - 1
endwhile
n ← n + 1
endwhile
※問題が変われば、7の値が変わります。
補足1
Java とPython で交換法（バブルソート）をコーディング
Java の実装
import java.util.Arrays;
public class BubbleSort {
public static void bubbleSort(int[] A) {
int n = 1;
int size = A.length;
while (n < size) {
int i = size - 1;
while (i >= n) {
if (A[i - 1] > A[i]) {
int temp = A[i];
A[i] = A[i - 1];
A[i - 1] = temp;
}
i--;
}
n++;
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
System.out.println("Before sorting: " + Arrays.toString(array));
bubbleSort(array);
System.out.println("After sorting: " + Arrays.toString(array));
}
}
Python の実装
def bubble_sort(A):
n = 1
size = len(A)
while n < size:
i = size - 1
while i >= n:
if A[i - 1] > A[i]:
A[i], A[i - 1] = A[i - 1], A[i] # Swap
i -= 1
n += 1
if __name__ == "__main__":
array = [64, 34, 25, 12, 22, 11, 90]
print("Before sorting:", array)
bubble_sort(array)
print("After sorting:", array)
補足2
交換法（Swap Method）とは？
交換法（スワップ法）とは、アルゴリズムの中で 二つの要素の値を入れ替える 操作のことを指します。特に、ソートアルゴリズム（バブルソートや選択ソートなど）でよく使用されます。
1. 基本的な交換の仕組み
交換（Swap）は、通常 一時変数（temporary variable）を使う方法 と Pythonなどで使われる一時変数なしの方法 があります。
（1）一時変数を使う方法
最も基本的な交換方法で、値を一時変数 temp に保存しながら入れ替えます。
Java の例
int a = 5, b = 10;
int temp = a;
a = b;
b = temp;
System.out.println("a: " + a + ", b: " + b); // a: 10, b: 5
Python の例
a, b = 5, 10
temp = a
a = b
b = temp
print("a:", a, "b:", b) # a: 10, b: 5
（2）一時変数を使わない方法
言語によっては、一時変数を使わずに交換する方法もあります。
Python のタプルアンパッキング
Python では a, b = b, a という構文を使って簡単に交換できます。
a, b = 5, 10
a, b = b, a
print("a:", a, "b:", b) # a: 10, b: 5
数値演算を使った交換方法（非推奨）
加減算や XOR を使うことで、一時変数なしで交換することも可能ですが、可読性やオーバーフローの問題があるため通常は使いません。
加算・減算を使う方法
int a = 5, b = 10;
a = a + b;
b = a - b;
a = a - b;
System.out.println("a: " + a + ", b: " + b); // a: 10, b: 5
XOR を使う方法
int a = 5, b = 10;
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println("a: " + a + ", b: " + b); // a: 10, b: 5
しかし、この方法は可読性が低いため、通常の 一時変数を使う方法 や Pythonのタプルアンパッキング を推奨します。
2. 交換法を使ったソートアルゴリズム
交換法は、ソートアルゴリズムの中でよく使われます。例えば バブルソート（Bubble Sort） や 選択ソート（Selection Sort） では、要素を順番に比較しながら交換することでソートを行います。
（1）バブルソートでの交換法
バブルソートでは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返します。
Java のバブルソート
public class BubbleSort {
public static void bubbleSort(int[] A) {
int n = A.length;
for (int pass = 1; pass < n; pass++) {
for (int i = 0; i < n - pass; i++) {
if (A[i] > A[i + 1]) {
// 交換
int temp = A[i];
A[i] = A[i + 1];
A[i + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] array = {64, 34, 25, 12, 22, 11, 90};
bubbleSort(array);
System.out.println(java.util.Arrays.toString(array));
}
}
Python のバブルソート
def bubble_sort(A):
size = len(A)
for pass_num in range(size - 1):
for i in range(size - 1 - pass_num):
if A[i] > A[i + 1]:
A[i], A[i + 1] = A[i + 1], A[i] # 交換
array = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(array)
print(array)
（2）選択ソートでの交換法
選択ソートでは、最小（または最大）の要素を見つけて交換します。
Java の選択ソート
public class SelectionSort {
public static void selectionSort(int[] A) {
int n = A.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (A[j] < A[minIndex]) {
minIndex = j;
}
}
// 交換
int temp = A[i];
A[i] = A[minIndex];
A[minIndex] = temp;
}
}
public static void main(String[] args) {
int[] array = {64, 25, 12, 22, 11};
selectionSort(array);
System.out.println(java.util.Arrays.toString(array));
}
}
Python の選択ソート
def selection_sort(A):
size = len(A)
for i in range(size - 1):
min_index = i
for j in range(i + 1, size):
if A[j] < A[min_index]:
min_index = j
# 交換
A[i], A[min_index] = A[min_index], A[i]
array = [64, 25, 12, 22, 11]
selection_sort(array)
print(array)
3. 交換法を使うメリットとデメリット
（1）メリット
✅ シンプルで直感的
交換は基本的な演算なので理解しやすく、コードの見た目もわかりやすい。
✅ 比較的汎用的
バブルソート、選択ソート、クイックソートなど、さまざまなアルゴリズムで使われる。
（2）デメリット
❌ 不要な交換が増える可能性がある
バブルソートでは無駄な交換が多くなりやすく、処理時間が増える。
❌ スワップ回数が多いと処理コストがかかる
メモリアクセス（特にキャッシュ）や CPU 負荷が増えるため、大規模データには向かない場合がある。
まとめ
交換法（スワップ法） は、要素の値を入れ替える基本的な方法。
一時変数を使う方法 が最も一般的で、Python ではタプルアンパッキングが便利。
バブルソート・選択ソート などのソートアルゴリズムで頻繁に使用される。
メリットはシンプルさ、デメリットは交換回数の増加によるパフォーマンス低下。
以上です。