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

挿入ソートは、インプレース比較ベースのアルゴリズムであるソートアルゴリズムです。

アルゴリズムは、ソートされたサブ配列内の位置に要素を配置することによって機能します。つまり、ソートされたサブ配列である要素の前にあるサブ配列です。

アルゴリズム

ステップ1-1からn-1にループし、実行します-

ステップ2.1-位置i、array[i]で要素を選択します。

ステップ2.2-要素をソートされたサブ配列配列[0]のその位置に挿入してarr[i]にします。

アルゴリズムを理解するために例を見てみましょう

配列 =[34、7、12、90、51]

私のために =1、arr [1] =7、サブ配列arr [0]--arr[1]の位置に配置します。

[7, 34, 12, 90, 51]

i=2の場合 、arr [2] =12、サブ配列arr [0]--arr[2]の位置に配置します。

[7, 12, 34, 90, 51]

i=3の場合 、arr [3] =90、サブ配列arr [0]--arr[3]の位置に配置します。

[7, 12, 34, 90, 51]

私のために =4、arr [4] =51、サブ配列arr [0]--arr[4]の位置に配置します。

[7, 12, 34, 54, 90]

ここでは、再帰的な挿入ソートがどのように機能するかを見ていきます。これは逆に機能します。つまり、現在の反復と比較して、n-1個の要素配列を並べ替えるためにrecursiveInsertionSort（）関数を再帰的に呼び出します。次に、関数によって返されるこの並べ替えられた配列で、並べ替えられた配列の場合と同様に、その位置にn番目の要素を挿入します。

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

例

#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
   if (n <= 1)
      return;
   recursiveInsertionSort( arr, n-1 );
   int nth = arr[n-1];
   int j = n-2;
   while (j >= 0 && arr[j] > nth){
      arr[j+1] = arr[j];
      j--;
   }
   arr[j+1] = nth;
}
int main(){
   int array[] = {34, 7, 12, 90, 51};
   int n = sizeof(array)/sizeof(array[0]);
   printf("Unsorted Array:\t");
      for (int i=0; i < n; i++)
   printf("%d ",array[i]);
      recursiveInsertionSort(array, n);
   printf("\nSorted Array:\t");
   for (int i=0; i < n; i++)
      printf("%d ",array[i]);
   return 0;
}

出力

Unsorted Array: 34 7 12 90 51
Sorted Array: 7 12 34 51 90