Data-structures-algorithms-bubble-sort-algorithm
データ構造-バブルソートアルゴリズム
バブルソートは、単純なソートアルゴリズムです。 このソートアルゴリズムは比較ベースのアルゴリズムであり、隣接する要素の各ペアが比較され、要素が順序どおりでない場合は要素が交換されます。 このアルゴリズムは、平均および最悪の場合の複雑さがare（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プログラミング言語でのバブルソートの実装については、リンク：/data_structures_algorithms/bubble_sort_program_in_c [ここをクリック]をご覧ください。
