[정렬 알고리즘] Recursive Insertion Sort(재귀 삽입 정렬)

§Revursive Insertion Sort

삽입 정렬을 재귀로 표현한 것

 

1. 만약 배열 사이즈가 1이거나 더 작을 경우 return 한다.
2. 재귀 함수에 n-1 배열 사이즈를 인수로 넘겨준다.
3. 부분 배열의 마지막 원소를 올바른 위치로 정렬한다.

 

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37

//////////////////////////////// //    Recursive Insertion Sort //    재귀 삽입 정렬 ////////////////////////////////   #include <stdio.h>   void insertSortRecursive(int *arr,int  n) {     if (n <= 1)return;     insertSortRecursive(arr, n - 1);       int last = arr[n - 1];     int j = n - 2;       while (j >= 0 && arr[j] > last) {         arr[j + 1] = arr[j];         j = j - 1;     }     arr[j+1] = last; }   void printArray(int arr[], int n) {     for (int i = 0; i < n; i++)         printf("%d ", arr[i]);     printf("\n"); }   int main() {     int arr[] = { 12,11,13,5,6 };     int n = sizeof(arr) / sizeof(arr[0]);       insertSortRecursive(arr, n);     printf("Sorted Array : ");     printArray(arr, n);       return 0; } Colored by Color Scripter

cs