テクノロジ
バブルソートとは
英語名：Bubble Sort
ひとことで言うと：隣り合う要素を比較して順序が逆なら交換する操作を繰り返し、データを整列する方法。
意味をわかりやすく解説
昇順のバブルソートでは、隣接要素を左から比較し、大きい値を右へ移動させる処理を繰り返します。一巡すると未確定部分の最大値が右端へ移動します。
単純実装では比較回数がn²に比例しやすく、計算量はO(n²)です。理解しやすい一方、大規模データには効率が良くありません。
具体例
[5,2,4,1]を左から比較すると、最初の一巡で5は2、4、1と順に交換され、右端へ移動します。
似た用語との違い
選択ソート
バブルソートは隣接要素を交換します。選択ソートは未整列部分から最小値を選んで先頭へ置きます。
基本情報技術者試験の試験ポイント
隣接比較・交換と、一巡ごとに端の要素が確定する動きを追います。O(n²)も押さえます。
CHECK QUESTION
要素数が約2倍になったとき、単純なO(n²)のバブルソートの処理量はおよそ何倍になりますか。
答えを見る
約4倍です。処理量がn²に比例するためです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。