バブルソート

概要

バブルソートは、すべてのデータを一つずつチェックしながら、(昇順の場合)最も大きいデータを後ろに押し出していく。

たとえば以下のような初期データ列があるとする。

3, 4, 1, 2, 0

最初のループでは、全データの中で最大のものが一番最後に来るようにする。

3, 4, 1, 2, 0
3, 4, 1, 2, 0 → 3, 1, 4, 2, 0
3, 1, 4, 2, 0 → 3, 1, 2, 4, 0
3, 1, 2, 4, 0 → 3, 1, 2, 0, 4

3, 1, 2, 0, 4 → 1, 3, 2, 0, 4
1, 3, 2, 0, 4 → 1, 2, 3, 0, 4
1, 2, 3, 0, 4 → 1, 2, 0, 3, 4

1, 2, 0, 3, 4
1, 2, 0, 3, 4 → 1, 0, 2, 3, 4

1, 0, 2, 3, 4 → 0, 1, 2, 3, 4

ループ回数は(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}

コード

Pythonによるバブルソートのコード例。

安定ソート

バブルソートは安定ソートである。すなわち、同じソートキーのデータについて、ソート後も元の順序が保持される。

 

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です