バブルソートについて ーアルゴリズム概要ー

 バブルソートとは

プログラムのソート（整列）アルゴリズムの中で、もっともシンプルでわかりやすい

ものの一つです。ソート（整列）とは、たとえば、「4，6，1，９，２，３３」といった数列の

を小さい順（昇順）や大きい順（降順）に並び替える操作のことを言います。バブルソートの概要（昇順の場合）を説明しますと、まず数列の全要素に対して隣り合う２項を比較し、順序が逆ならばそれらを入れ替えます。この操作を右から順に行っていくと、最も小さい要素が一番左すなわち１番目に来ます。この要素は確定です。

次は、この左端を除いた部分に対して同様の操作を行っていくと２番目が決定されます。全要素が整列するまでこの操作を続けていきます。

イメージ図

                     

バブルソートに関して私の興味がわいたこととしては、「長さNの自然数列に対し上記２項交換回数の平均（期待値）はいくつか」という問題です。次記事でそれを考えてみたいと思います。