バブルソート、選択ソート、挿入ソート、およびCコードの例

ツールバーの

1.バブルソート

1.1バブルソートの概念

1.2アルゴリズムステップ

1.3コード例

2.選択ソート

2.1選択ソートの概念

2.2アルゴリズムステップ

2.3コード例

3.挿入ソート

3.1挿入ソートの概念

3.2アルゴリズムステップ

3.3コード例

1.泡立ちソート
1.1発泡ソートの概念
バブルソート(Bubble Sort)も単純で直感的なソートアルゴリズムである.ソートする数列を繰り返し訪問し、2つの要素を一度に比較し、順序が間違っている場合は交換します.数列を訪問する作業は、交換が必要になるまで繰り返し、すなわち、その数列がソートされるまで行われる.このアルゴリズムの名前の由来は,小さな要素ほど交換を介して徐々に数列の先端に「浮かぶ」からである.
バブルソートにはもう1つの最適化アルゴリズムがあり、flagを立て、1つのシーケンス遍歴で要素が交換されていない場合、シーケンスが秩序化されていることを証明する.しかし、この改善はパフォーマンスの向上にあまり役に立たない.
1.2アルゴリズムステップ

隣接する要素を比較します.1つ目が2つ目より大きい場合は、2つを交換します.

は、各隣接要素のペアについて、最初のペアから最後のペアまで同様に動作する.このステップが終わると、最後の要素が最大の数になります.

は、最後のステップを除いて、すべての要素について以上のステップを繰り返す.

は、比較を必要とする数字のペアがなくなるまで、より少ない要素に対して上記の手順を繰り返します.

1.3コード例

#include 

void bubble_sort(int arr[], int len) 
{
      int          i, j, temp;
      for (i = 0; i < len - 1; i++)
           for (j = 0; j < len - 1 - i; j++)
                if (arr[j] > arr[j + 1]) 
                {
                     temp = arr[j];
                     arr[j] = arr[j + 1]；
                     arr[j + 1] = temp;
                 }
}
int main() 
{

        int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };

        int len = (int) sizeof(arr) / sizeof(*arr);

        bubble_sort(arr, len);

        int i;

        for (i = 0; i < len; i++)
        printf("%d ", arr[i]);

        return 0;

}

2.ソートの選択
2.1ソートの概念の選択
選択ソートは単純で直感的なソートアルゴリズムであり,どんなデータが入ってもO(n²) の時間的複雑さを表します.そのため、データの規模が小さいほど良いです.唯一のメリットは、余分なメモリ容量を消費しないことでしょう.
2.2アルゴリズムステップ

は、まず、ソートされていないシーケンスの中で最小(大きい)要素を見つけ、ソートされたシーケンスの開始位置に格納する.

は、残りの並べ替えられていない要素から最小(大きい)要素を探し続け、並べ替えられたシーケンスの最後に配置する.

すべての要素がソートされるまで、2番目のステップを繰り返します.

2.3コード例

void swap(int *a,int *b) //      

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

void selection_sort(int arr[], int len) 

{

    int i,j;



        for (i = 0 ; i < len - 1 ; i++) 

    {

                int min = i;

                for (j = i + 1; j < len; j++)     //        

                        if (arr[j] < arr[min])    //       

                                min = j;    //     

                swap(&arr[min], &arr[i]);    //   

        }

}

3.ソートの挿入
3.1ソートの概念を挿入する
挿入ソートのコード実装は、バブルソートや選択ソートほど簡単ではありませんが、トランプをしたことがある人は秒で理解できるはずです.挿入ソートは最も単純で直感的なソートアルゴリズムであり、秩序化されたシーケンスを構築することによって、ソートされていないデータに対して、ソートされたシーケンスの中で後方から前方にスキャンし、対応する位置を見つけて挿入することが原理です.
挿入ソートはバブルソートと同様に,分割挿入という最適化アルゴリズムもある.
3.2アルゴリズムステップ

は、ソートされるシーケンスの最初の要素を秩序化シーケンスと見なし、2番目の要素から最後の要素までを非ソートシーケンスと見なす.

は、順序付けされていないシーケンスを最初から最後まで順次スキャンし、スキャンされた各要素を順序付けられたシーケンスの適切な位置に挿入する.(挿入する要素が順序付きシーケンスの要素と等しい場合は、挿入する要素を等しい要素の後ろに挿入します.)

3.3コード例

void insertion_sort(int arr[], int len){

        int i,j,key;

        for (i=1;i<len;i++){

                key = arr[i];

                j=i-1;

                while((j>=0) && (arr[j]>key)) {

                        arr[j+1] = arr[j];

                        j--;

                }

                arr[j+1] = key;

        }

}

泡立ち,挿入,選択の3つの時間的複雑さはいずれもO(n^2)である.