データ処理の必須アルゴリズム、「ソート」の優劣を見極めろ

［3　基礎］ バブルソート

　二分探索はデータがソートされていることを前提としていました。それでは、ソートはどのようなアルゴリズムで実現するのでしょうか。

　ソートのアルゴリズムはたくさんあります。その中で「バブルソート」は、効率は悪いのですが、仕組みが簡単なので容易に実装できるというメリットを持つアルゴリズムです。

　バブルソートは、隣同士のデータの大小を比較し、小さい順（または大きい順）に並び替える（位置を交換する）作業を繰り返すと、最終的にソートが完了する、というものです。例えば、次のリストdataのソートを考えてみましょう。

　このdataをバブルソートでソートする過程を図解すると、図1のようになります。バブルソートは、データの比較と交換を、データの末尾から順に行います。その際、データの動きが水底から上がってくる泡（バブル）のようなので、バブルソートという名称なのです。