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

バブルソートは、隣接する要素を比較してデータをソートするために使用される最も単純なソートアルゴリズムの1つです。すべての要素が段階的に比較されます。最初のフェーズでは最大値が最後に配置され、2番目のフェーズでは2番目に大きい要素が最後から2番目の位置に配置され、以下同様に完全なリストが並べ替えられます。

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

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

• int i、j;

• インデックスi=0からi<配列サイズ

  までトラバースします

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

  • arr [i]>arr[j]がarr[i]をarr[j]

    と交換する場合

• 終了

再帰的なバブルソート

• 配列の長さが1の場合は、

  を返します。

• 配列を1回トラバースし、最後に最大の要素を修正します

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

例

入力 − arr [] ={5,7,2,3,1,4};長さ=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

入力 − 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）は、配列とその長さを取得し、バブルソートを使用して配列を再帰的にソートします。

• 可変温度を取ります。

• 配列の長さが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