Design-and-analysis-of-algorithms-bubble-sort

DAA-バブルソート

バブルソートは基本的なソートアルゴリズムで、必要に応じて隣接する要素を繰り返し交換することで機能します。 交換が不要な場合、ファイルはソートされます。

これは、すべてのソートアルゴリズムの中で最も単純な手法です。

Algorithm: Sequential-Bubble-Sort (A)
fori← 1 to length [A] do
for j ← length [A] down-to i +1 do
   if A[A] < A[j - 1] then
      Exchange A[j] ↔ A[j-1]

実装

voidbubbleSort(int numbers[], intarray_size) {
   inti, j, temp;
   for (i = (array_size - 1); i >= 0; i--)
   for (j = 1; j <= i; j++)
      if (numbers[j - 1] > numbers[j]) {
         temp = numbers[j-1];
         numbers[j - 1] = numbers[j];
         numbers[j] = temp;
      }
}

分析

ここで、比較の数は

• 1 + 2 + 3 + …​ +（n-1）= n _（ n_-1）/2 = O（n ^ 2 ^）*

明らかに、グラフはバブルソートの _n ^ 2 ^ _ の性質を示しています。

このアルゴリズムでは、比較の数はデータセットに関係しません。 提供された入力要素がソート順か、逆順か、ランダムか。

メモリー要件

上記のアルゴリズムから、バブルソートが余分なメモリを必要としないことは明らかです。

例

Unsorted list:

|5 |2 |1 |4 |3 |7 |6

1 ^ st ^反復：

5 > 2 swap

|2 |5 |1 |4 |3 |7 |6

5 > 1 swap

|2 |1 |5 |4 |3 |7 |6

5 > 4 swap

|2 |1 |4 |5 |3 |7 |6

5 > 3 swap

|2 |1 |4 |3 |5 |7 |6

5 < 7 no swap

|2 |1 |4 |3 |5 |7 |6

7 > 6 swap

|2 |1 |4 |3 |5 |6 |7

2 ^ nd ^反復：

2 > 1 swap

|1 |2 |4 |3 |5 |6 |7

2 < 4 no swap

|1 |2 |4 |3 |5 |6 |7

4 > 3 swap

|1 |2 |3 |4 |5 |6 |7

4 < 5 no swap

|1 |2 |3 |4 |5 |6 |7

5 < 6 no swap

|1 |2 |3 |4 |5 |6 |7

3 ^ rd ^、4 ^ th ^、5 ^ th ^、および6 ^ th ^の繰り返しに変更はありません。

最後に、

the sorted list is

|1 |2 |3 |4 |5 |6 |7