재귀 삽입 정렬을 위한 C 프로그램

삽입 정렬은 내부 비교를 기반으로 하는 정렬 알고리즘입니다.

이 알고리즘은 정렬된 하위 배열의 한 위치에 요소를 배치하여 작동합니다. 즉, 요소 ​​앞의 하위 배열이 정렬된 하위 배열입니다.

Algorithm

Step1 - 1에서 n-1까지 반복하고 실행 -

Step2 .1 - 위치 i에 있는 요소, 배열[i]을 선택합니다.

Step2.2 - 정렬된 하위 배열 배열[0]의 arr[i] 위치에 요소를 삽입합니다.

예를 통해 알고리즘을 이해해 봅시다

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

For 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번째 요소를 정렬된 배열의 해당 위치에 삽입합니다.

재귀 삽입 정렬 프로그램은 다음과 같습니다.

Example

Demonstration

#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

위 내용은 재귀 삽입 정렬을 위한 C 프로그램의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!