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

挿入ソートは、インプレース比較に基づく並べ替えアルゴリズムです。

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

アルゴリズム

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

ステップ 2 .1 - 位置 i の要素、array[i] を選択します。

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

例を通してアルゴリズムを理解しましょう

Array = [34, 7, 12, 90, 51]

i = 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]

i = 4、arr[4] = 51 の場合、サブ配列 arr[0] ～ arr[4] 内の正しい位置に配置します。

[7, 12, 34, 54, 90]

ここでは、再帰的挿入ソートがどのように機能するかを見ていきます。これは逆の方法で動作します。つまり、 recursiveInsertionSort() 関数を再帰的に呼び出して、現在の反復と比較して n-1 個の要素の配列を並べ替えます。次に、関数によって返された並べ替えられた配列内で、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("</p><p>Sorted 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

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