単純交換法(バブルソート)について
単純交換法は、隣り合ったデータの大小を比較して交換するという作業を繰り返して行い、最終的にデータを昇順または降順に並べ替えるアルゴリズムです。
このアルゴリズムは、並べ替える様子が、水中から水面へ浮かび上がっていく泡のように見えることから、バブルソート(bubble sort)と呼ばれています。
バブルソートの説明を先頭の要素から順番に比較する方法で説明しているサイトや本がありますが、泡のイメージを出す為に水の底(末尾)から水面(先頭)に向かって順番に比較する方法で説明します。
小さい数字を上へ持ち上げていくイメージです。
どちらの方法も考え方は同じですが、末尾の要素から先頭の要素に向かって順番に比較していく方法を説明しているものが多いように思います。
単純交換法のイメージ
以下の図は単純交換法を使ってデータを小さい順(昇順)に並べ替える様子のイメージです。
[単純交換法のイメージ]
サンプルコード
単純交換法のアルゴリズムを以下のプログラミング言語で紹介します。
- Tcl
- Python
サンプルコードについて
各プログラミング言語の基本的な制御構造とデータ構造を使って記述しています。
必要であれば、for, foreach、リスト、配列などに書き換えたり、関数化を行って練習してください。
Tcl
[サンプル：bubble-sort.tcl]
#!/bin/sh
# the next line restarts using tclsh \
exec tclsh "$0" "$@"
# 単純交換法(bubble sort:バブルソート)
# arr : 数値リスト
# n : 要素数
# i : 要素のindex
# tmp : 交換用
# last: 確定した最小値を入れる位置
array set arr {0 40 1 10 2 30 3 50 4 20}
set n [array size arr]
set last 0
while {$last < $n - 1} {
set i [expr $n - 1]
while {$i > $last} {
# 隣り合ったデータの大小を比較して交換する。
if {$arr([expr $i -1]) > $arr($i)} {
set tmp $arr([expr $i -1])
set arr([expr $i -1]) $arr($i)
set arr($i) $tmp
}
incr i -1
}
incr last
}
parray arr
[実行例]
$ ./bubble-sort.tcl arr(0) = 10 arr(1) = 20 arr(2) = 30 arr(3) = 40 arr(4) = 50
Python
[サンプル：bubble-sort.py]
#!/usr/bin/env python3
# 単純交換法(bubble sort:バブルソート)
# arr : 数値リスト
# n : 要素数
# i : 要素のindex
# tmp : 交換用
# last: 確定した最小値を入れる位置
arr = [40, 10, 30, 50, 20]
n = len(arr)
print(arr)
last = 0
while last < n-1:
i = n-1
while i > last:
# 隣り合ったデータの大小を比較して交換する。
if arr[i-1] > arr[i]:
tmp = arr[i-1]
arr[i-1] = arr[i]
arr[i] = tmp
i -= 1
last += 1
print(arr)
[実行例]
$ ./bubble-sort.py [40, 10, 30, 50, 20] [10, 20, 30, 40, 50]
コメント