Recursive C Insertion Sort
#include<stdio.h>
#define ARR_SIZE 6
void print_r(int *arr, size_t n);
void insertion_sort(int *arr, size_t n, size_t i);
int main(){
int nums[ARR_SIZE] = {2,8,9,0,0,2};
print_r(nums, ARR_SIZE);
printf("Sorting...\n");
insertion_sort(nums, ARR_SIZE, 0);
print_r(nums, ARR_SIZE);
return 0;
}
void print_r(int *arr, size_t n){
int i;
printf("Array\n(\n");
for(i=0; i<n; i++){
printf("\t[%d] => %d\n", i, arr[i]);
}
printf(")\n");
}
/*
* This insertion sort will be done in place as opposed to the PHP
* implementation.
*/
void insertion_sort(int *arr, size_t n, size_t i){
int el,j;
if(i == n-1){
// Nothing to do since we're looking at the last element.
}
else{
insertion_sort(arr, n, i+1);
el = arr[i];
// All elements to the right of index i are assumed to be sorted.
// Now we just have to figure out where el fits in the sorted array
for(j = i+1; j<n; j++){
if(el > arr[j]){
// el is bigger, swap so el moves to the right in the array.
arr[j-1] = arr[j];
arr[j] = el;
}
}
}
}