【応用情報技術者試験】バブルソートとクイックソートの違いをわかりやすく解説

バブルソートは隣接要素の比較・交換、クイックソートはピボットを基準とする分割で整列します。クイックソートが常に速いと覚えず、平均と最悪の計算量を区別しましょう。

並べ方の違い

方法	操作	考え方
バブル	隣同士を比較し、逆順なら交換	走査を繰り返して端から位置を確定
クイック	ピボットを基準に分割し、各部分で同じ処理	分割統治

［6, 3, 8, 2］を左から昇順に比較します。6と3を交換して［3, 6, 8, 2］、6と8はそのまま、8と2を交換して［3, 6, 2, 8］です。最大の8は右端に移りましたが、まだ全体の整列は終わっていません。残りの範囲で繰り返します。

同じ配列で6をピボットにすると、小さい側［3, 2］・基準6・大きい側［8］と分けて考えられます。［3, 2］も整列することで［2, 3, 6, 8］になります。ここでは概念を示しており、分割直後の配列の順番は実装によって異なります。同じ値の扱いも実装の規則に従います。

方法	平均	最悪	最良の注意点
バブル	O(n²)	O(n²)	交換なしで終了する実装なら整列済みでO(n)
クイック	O(n log n)	O(n²)	基本的な方式では均等な分割でO(n log n)

クイックの平均は、入力やピボット選択について平均的な条件を考えた値です。毎回ほぼ1個と残りに分かれるような偏りが続くと、最悪O(n²)になります。整列済み入力が悪くなるかどうかも、ピボットの選び方などに依存します。