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

バブルソート思想:隣接する2つの数を順次比較し、小さい数を前に、大きい数を後ろに置く(気泡上昇に相当するため、バブルソートと呼ばれる)
バブルソートのアルゴリズムは安定で,時間複雑度はO(n)^2であった.
バブルソートの図解:

 // 23    12    34    22    9
    // i      j                    array[j - 1] > array[j]    
    // 12    23    34    22    9
    // i            j              array[j - 1] < array[j]     
    // 12    23    34    22    9
    // i                  j        array[j - 1] > array[j]    
    // 12    23    22    34    9
    // i                       j   array[j - 1] > array[j]    
    // 12    23    22    9     34                 34
    //          
    // 12    23    22    9     34
    //       ij                    array[j - 1] < array[j]     
    // 12    23    22    9     34
    //       i     j               array[j - 1] > array[j]    
    // 12    22    23    9     34
    //       i           j         array[j - 1] > array[j]    
    // 12    22    9     23    34              
    //          
    // 12    22    9     23    34
    //       j     i               array[j - 1] < array[j]     
    // 12    22    9     23    34
    //             ij              array[j - 1] > array[j]    
    // 12    9     22    23    34         
    //          
    // 12    9     22    23    34  
    //       j           i         array[j - 1] > array[j]    
    // 9     12    22    23    34         
    //       

バブルソートのコード:

void bubble_sort1(int *array, int length)   //    
{
    int i = 0;
    int j = 0;
    int temp = 0;

    for(i = 0; i < length -1; ++i){
        for(j = 1; j < length - i; ++j){
            if(array[j - 1] > array[j]){
                temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
            }
        }
    }
}

最適化された泡ソート:
各ラウンドの比較が終了した後に交換が発生したかどうかをマークするためのマークが与えられ、交換が発生していない場合はシーケンスが整列していることを示します.

void bubble_sort2(int *array, int length)   //       
{
    int i = 0;
    int temp = 0;
    Boolean flag = TRUE;   //  ， TRUE      ，      

    while(flag){    //           
        flag = FALSE;    //             
        for(j = 1; j < length; ++j){
            if(array[j - 1] > array[j]){
                temp = array[j - 1];
                array[j - 1] = array[j];
                array[j] = temp;
                flag = TRUE;
            }
        }
        length--;
    }
}