삽입 정렬은 내부 비교 기반 알고리즘인 정렬 알고리즘입니다.
알고리즘은 정렬된 하위 배열, 즉 정렬된 하위 배열인 요소 앞의 하위 배열에서 해당 위치의 요소를 배치합니다.
알고리즘
1단계 - 1에서 n-1까지 반복하고 수행 -
Step2.1 - 위치 i, array[i]에서 요소를 선택합니다.
Step2.2 - 정렬된 하위 배열 array[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