C のバブルソート

並べ替えは、どのプログラミング言語でも学ぶ必要がある必須の概念です。ほとんどのソートは数値を含む配列に対して行われ、配列からデータを走査してアクセスする技術を習得するための足がかりとなります。
今日の記事で説明する並べ替えテクニックの種類は、バブル ソートです。

バブルソート

バブルソートは、順序が間違っている場合に隣接する要素を繰り返し交換することで機能するシンプルなソートアルゴリズムです。配列をソートするこの方法は、平均シナリオと最悪シナリオの時間計算量が非常に高いため、大規模なデータセットには適していません。

バブルソートのアルゴリズム：

1. バブルソートは、複数のパスで配列を並べ替えることによって配列を整理します。
2. 最初のパス: 最大の要素が最後の位置、つまり正しい場所に移動します。
3. 2 番目のパス: 2 番目に大きい要素が最後から 2 番目の位置に移動し、これが後続のパスでも続きます。
4. 各パスでは、配列のソートされていない部分のみが処理されます。
5. k 個のパスが経過すると、最大の k 要素が最後の k スロットの正しい位置に配置されます。
6. 各パス中:
   • 未並べ替えセクション内の隣接する要素を比較します。
   • 大きい要素が小さい要素の前に表示される場合は、要素を交換します。
   • パスの終わりまでに、ソートされていない最大の要素が正しい位置に移動します。 このプロセスは、配列全体がソートされるまで繰り返されます。

バブルソートはどのように機能しますか?

以下はバブルソートの実装です。内部ループでスワップが発生しなかった場合は、アルゴリズムを停止することで最適化できます。

// Easy implementation of Bubble sort
#include <stdio.h>
int main(){
    int i, j, size, temp, count=0, a[100];
    //Asking the user for size of array
    printf("Enter the size of array you want to enter = \t");
    scanf("%d", &size);
    //taking the input array through loop
    for (i=0;i<size;i++){
        printf("Enter the %dth element",i);
        scanf("%d",&a[i]);
    }
    //printing the unsorted list
    printf("The list you entered is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    //sorting the list
    for (i = 0; i < size - 1; i++) {
        count = 1;
        for (j = 0; j < size - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                //swapping elements
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
                count = 1;
            }
        }

        // If no two elements were swapped by inner loop,
        // then break
        if (count == 1)
            break;
    }
    // printing the sorted list
    printf("\nThe sorted list is : \n");
    for (i=0;i<size;i++){
        printf("%d,\t",a[i]);
    }
    return 0;

}

出力:

**

バブルソートの複雑さの分析:

時間計算量: O(n2)
補助スペース: O(1)

バブルソートの利点:

• バブルソートは理解と実装が簡単です。
• 追加のメモリ領域は必要ありません。
• これは安定した並べ替えアルゴリズムであり、同じキー値を持つ要素が並べ替えられた出力内で相対的な順序を維持することを意味します。

バブルソートの欠点:

• バブル ソートの時間計算量は O(n2) であるため、大規模なデータ セットの場合は非常に遅くなります。
• バブル ソートは比較ベースの並べ替えアルゴリズムです。つまり、入力データ セット内の要素の相対的な順序を決定するために比較演算子が必要です。場合によっては、アルゴリズムの効率が制限される可能性があります。

ご質問があればコメントしてください!!
そして、すべての議論を歓迎します:)

以上がC のバブルソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。