C++プログラムの再帰的挿入ソート

挿入ソートは、トランプのような要素を挿入することによってデータをソートするために使用されるソートアルゴリズムの1つです。すべての要素が左から右に配置され、最初の要素がすでに並べ替えられていると見なして、左側の並べ替えられたリストに残りを挿入します。各要素は、正しい位置に挿入されるまで、左側のリストの各要素と比較されます。

挿入ソートアルゴリズム

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

• int i、j;

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

  までトラバースします

• 各要素について、arr [j]は、arr [i] =arr [j]となる要素が見つかるまで、リストarr [0toi]の要素と比較します。

• リストにarr[j]を配置し、大きい要素をすべて1つ右に移動します。

• 終了

再帰的挿入ソート

• 配列の長さが1の場合は、戻ります。

• インデックス0の要素を配列サイズ-1に再帰的にsorします

• ソートされた配列の最後の要素を挿入します

例

入力 − arr [] ={5,7,2,3,1,4};長さ=6

出力 −ソートされた配列：1 2 3 4 5 7

説明 −

5 7 2 3 1 4 → 5 already sorted
5 7 2 3 1 4 → 7 at correct place
2 5 7 3 1 4 → 2 compared with 5,7 and inserted
2 3 5 7 1 4 → 3 compared with 5,7 and inserted
1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted
1 2 3 4 5 7 → 4 compared with 5,7 and inserted

入力 − arr [] ={1、2、3、3、2};

出力 −ソートされた配列：1 2 2 3 3

説明 −

1, 2, 3, 3, 2 → 1 already sorted
1, 2, 3, 3, 2 → 2 at correct place
1, 2, 3, 3, 2 → 3 at correct place
1, 2, 3, 3, 2 → 3 at correct place
1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted

以下のプログラムで使用されているアプローチは次のとおりです

バブルソートの再帰的アプローチでは、基本ケースは配列の長さ=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 <bits/stdc++.h>
using namespace std;
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);

   cout<<"Sorted array : ";
   for(int i=0;i<length;i++){
      cout<<Arr[i]<<" ";
   }

   return 0;
}

出力

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

Sorted array : 20 21 31 34 43 66 78