-
Recursive Insertion Sort
I managed to write the following insertion sort program but I'm meant to do it recursively. Any ideas how to do it?
#include <stdio.h>
#define N 7
int InsertionSort(int array[N])
{
int j, p;
int temp;
for(p=1;p<N;p++)
{
temp = array[p];
for(j=p;j>0 && array[j-1]>temp;j--)
array[j] = array[j-1];
array[j] = temp;
}
printf("The list of sorted numbers is\n");
for(p=0;p<N;p++)
printf("%d ",array[p]);
printf("\n\n");
return 0;
}
void main()
{
int array[N] = {37,23,17,12,72,31,46};
InsertionSort(array);
return;
}
-
Loops can be turned into tail recursion really easy
Code:
#include <stdio.h>
#define N 7
void InsertionSort(int i, int array[], int size)
{
if (i < size)
{
int j;
int temp = array[i];
for (j = i; j > 0 && array[j-1] > temp; j--)
array[j] = array[j-1];
array[j] = temp;
InsertionSort(++i, array, size);
}
}
int main(void)
{
int p;
int array[N] = {37,23,17,12,72,31,46};
InsertionSort(0, array, N);
printf("The list of sorted numbers is\n");
for (p = 0; p < N; p++)
printf("%d ",array[p]);
printf("\n\n");
return 0;
}
And don't use void main, it's not valid C for a hosted implementation. In other words, if you use an operating system then main only returns an int, if you *are* the operating system, you can do what you want. :)