データ構造-バブルソートアルゴリズム
バブルソートは単純なソートアルゴリズムです。このソートアルゴリズムは比較ベースのアルゴリズムであり、隣接する要素の各ペアが比較され、要素が順番になっていない場合は要素が交換されます。このアルゴリズムは、平均および最悪の場合の複雑さがΟ（n 2）であるため、大規模なデータセットには適していません。n アイテムの数です。
バブルソートはどのように機能しますか？
例として、ソートされていない配列を取り上げます。バブルソートにはΟ（n 2）時間がかかるため、短く正確にしています。
バブルソートは最初の2つの要素から始まり、それらを比較してどちらが大きいかを確認します。
この場合、値33は14より大きいため、すでにソートされた場所にあります。次に、33と27を比較します。
27は33よりも小さいため、これら2つの値を交換する必要があります。
新しい配列は次のようになります-
次に、33と35を比較します。両方ともすでにソートされた位置にあることがわかります。
次に、次の2つの値、35と10に移動します。
その場合、10は35よりも小さいことがわかります。したがって、それらはソートされません。
これらの値を交換します。配列の最後に到達したことがわかります。1回の反復後、配列は次のようになります。
正確には、各反復後に配列がどのように見えるかを示しています。2回目の反復後は、次のようになります。
各反復の後、少なくとも1つの値が最後に移動することに注意してください。
そして、スワップが必要ない場合、バブルソートは配列が完全にソートされていることを学習します。
ここで、バブルソートのいくつかの実用的な側面を調べる必要があります。
アルゴリズム
私たちは仮定します list の配列です n要素。さらに、swap 関数は、指定された配列要素の値を交換します。
begin BubbleSort(list)
for all elements of list
if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort擬似コード
アルゴリズムでは、配列全体が完全に昇順でソートされていない限り、バブルソートが配列要素の各ペアを比較することがわかります。これにより、すべての要素がすでに昇順であるために配列をスワップする必要がなくなった場合など、いくつかの複雑な問題が発生する可能性があります。
問題を緩和するために、1つのフラグ変数を使用します swappedこれは、スワップが発生したかどうかを確認するのに役立ちます。スワップが発生しなかった場合、つまり配列をソートするためにそれ以上の処理が必要ない場合、配列はループから抜け出します。
BubbleSortアルゴリズムの擬似コードは次のように書くことができます-
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:
swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */
if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for
/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then
break
end if
end for
end procedure return list実装
元のアルゴリズムとその即興の擬似コードで対処しなかったもう1つの問題は、反復のたびに、最大値が配列の最後に落ち着くということです。したがって、次の反復には、すでにソートされている要素を含める必要はありません。この目的のために、実装では、すでにソートされた値を回避するために内部ループを制限します。
Cプログラミング言語でのバブルソートの実装については、ここをクリックしてください。