Program C untuk jenis sisipan rekursif

Isihan sisipan ialah algoritma pengisihan yang berdasarkan perbandingan di tempat.

Algoritma ini berfungsi dengan meletakkan elemen pada kedudukan dalam subarray yang diisih, iaitu subarray sebelum elemen adalah subarray yang diisih.

Algoritma

Langkah1 - Gelung dari 1 hingga n-1 dan laksanakan -

Langkah2 .1 - Pilih elemen pada kedudukan i, tatasusunan[i].

Langkah2.2 - Masukkan elemen ke dalam tatasusunan sub-tatasusunan[0] yang diisih pada kedudukannya arr[i].

Mari kita fahami algoritma melalui contoh

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

Untuk i = 1, arr[1] = 7, arr[1] = 7 0] - Kedudukan dalam arr[1].

[7, 34, 12, 90, 51]

Untuk i = 2, arr[2] = 12, letakkan kedudukan dalam subarray arr[0] - arr[2].

[7, 12, 34, 90, 51]

Untuk i = 3, arr[3] = 90, letakkannya pada kedudukan subarray arr[0] - arr[3].

[7, 12, 34, 90, 51]

Untuk i = 4, arr[4] = 51, letakkannya pada kedudukan yang betul dalam subarray arr[0] - arr[4].

[7, 12, 34, 54, 90]

Di sini kita akan melihat cara isihan sisipan rekursif berfungsi. Ia berfungsi dengan cara yang bertentangan, iaitu kita akan memanggil secara rekursif fungsi recursiveInsertionSort() untuk mengisih tatasusunan elemen n-1 berbanding dengan lelaran semasa. Kemudian dalam tatasusunan diisih yang dikembalikan oleh fungsi, kami memasukkan elemen ke-n ke dalam kedudukannya dalam tatasusunan yang diisih.

Program pengisihan sisipan rekursif adalah seperti berikut:

Contoh

Demonstrasi

#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;
}

Output

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

Atas ialah kandungan terperinci Program C untuk jenis sisipan rekursif. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!