再帰的バブルソート用の C プログラム

# バブル ソートは、隣接する要素を比較することによってデータを並べ替えるのに使用される最も単純な並べ替えアルゴリズムの 1 つです。すべての要素は段階的に比較されます。最初のステージでは最大値が最後に配置され、第 2 ステージでは 2 番目に大きい要素が最後から 2 番目の位置に配置され、完全なリストがソートされるまで同様に繰り返されます。

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

• ##int arr[5]= { 5,4,2,1,3 };

• int i, j ;

• インデックス i=0 から i
  • インデックス j=0 から配列サイズまでのトラバース - i - 1

  • If arr[i]>arr[j] arr[i] と arr[j]

• End

再帰バブルソート

• 配列の長さが 1 の場合、戻り値

• 配列を 1 回走査し、最後にある最大の要素を修正します

  ​​p>

• #配列の残りの部分は、最後の要素を除いてステップ 2 を再帰的に実行します

#例

入力

- Arr[] = { 5,7,2,3, 1,4}; length=6

出力

-ソートされた配列: 1 2 3 4 5 7

説明

−

First Pass
5 7 2 3 1 4 → swap → 5 2 7 3 1 4
5 2 7 3 1 4 → swap → 5 2 3 7 1 4
5 2 3 7 1 4 → swap → 5 2 3 1 7 4
5 2 3 1 7 4 → swap → 5 2 3 1 4 7
Second Pass
5 2 3 1 4 7 → swap → 2 5 3 1 4 7
2 5 3 1 4 7 → swap → 2 3 5 1 4 7
2 3 5 1 4 7 → swap → 2 3 1 5 4 7
2 3 1 5 4 7 → swap → 2 3 1 4 5 7
Third Pass
2 3 1 4 5 7 → swap → 2 1 3 4 5 7
2 1 3 4 5 7 no swap
Fourth Pass
2 1 3 4 5 7 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 no swap in further iterations

Input

- Arr[] = { 1, 2, 3, 3 , 2 };

出力

− ソートされた配列: 1 2 2 3 3

説明

-

First Pass
1 2 3 3 2 → swap → 1 2 3 2 3
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 no swap in further iterations
Second Pass
1 2 2 3 3 no swap in further iterations

次のプログラムで使用される方法は次のとおりです。

バブル ソートの再帰的方法では、基本的な状況は配列の長さ = 1 です。それ以外の場合は、単一の for ループを使用して配列を反復処理し、それに応じて要素を交換します。

入力配列 Arr[] を受け取り、長さをその要素の数として受け取ります。
関数 recurbublSort(int arr[], int len) は、配列とその長さを取得し、バブル ソートを使用して配列を再帰的に並べ替えます。

• #変数 temp を取得します。

• 配列の長さが 1 の場合、void が返されます。
それ以外の場合は、単一の for ループを使用して配列を反復処理し、要素 arr[i]>arr[i 1] ごとに要素を交換します。

• temp=arr[i]、arr[i]=arr[i 1]、および arr[i 1]=temp を設定します。

• 前のループでは最大の要素が最後の位置に配置されていたため、長さを 1 減らします。

• recurbublSort(arr,len) を再帰的に呼び出します。

• すべての呼び出しが終了し、len が 1 になると、再帰を終了し、配列をソートします。

• #ソートされた配列を main に出力します。

• 例

  #include <stdio.h>
  void recurbublSort(int arr[], int len){
     int temp;
  
     if (len == 1){
        return;
     }
     for (int i=0; i<len-1; i++){
        if (arr[i] > arr[i+1]){
           temp=arr[i];
           arr[i]=arr[i+1];
           arr[i+1]=temp;
        }
     }
     len=len-1;
     recurbublSort(arr, len);
  }
  int main(){
     int Arr[] = {21, 34, 20, 31, 78, 43, 66};
     int length = sizeof(Arr)/sizeof(Arr[0]);
  
     recurbublSort(Arr, length);
  
     printf("Sorted array : ");
     for(int i=0;i<length;i++){
        printf("%d ",Arr[i]);
     }
  
     return 0;
  }

出力

上記のコードを実行すると、次の出力が生成されます

Sorted array: 20 21 31 34 43 66 78

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