Solved

# Insertion Sort by Top-down recursive function

Posted on 2006-03-26
Medium Priority
291 Views
I am tryin to write a program where a recursive function (which calls itself each time) would sort the values contained in an array.

I had a go at it, but widout success. The code (not workin) is as follows

#include <stdio.h>
void sort(int m, int a[]);
void main (void)
{
int m;
int a[] = {3, 1, 9, 7, 8, 11, 7};
printf("Type the number of values requied to be sorted ");
scanf("%i", &m);

//      sort(int m, int a[]);
}

void sort(int m, int a[])

{
//       if(m>0){

//       {

printf("%i",  a[m]);

}

Thanks
0
Question by:khawaib
• 4
• 2

LVL 16

Expert Comment

ID: 16293965
Hi khawaib,

What are you actually trying to do?

One method is to use the fact that a one-entry array is by definition sorted and a two-entry array can be sorted by comparing the two entries and swapping them. Any other array can be sorted as two arrays of smaller size.

Try implementing that! Sorry but your code isnt sufficient for us to suggest changes as there isnt really anything there.

Paul
0

LVL 16

Expert Comment

ID: 16293988
Hi khawaib,

Hint:

to sort a part of an array starting at n of length m, use

sort(m, &a[n]);

Paul
0

Author Comment

ID: 16294137
The recursive function should sort the numbers in array "a". The function would take each integer and will see whether its smaller than the previous and place it in front of an integer which is bigger than itself i.e. 3 before 1 (1, 3) etc.

However I,m having difficulty to know how the function would call itself, so it repeates the process with all the integers in the array till it reaches m value (number of integers which need to be sorted).  Any thoughts?

#include <stdio.h>
void sort(int a[], int m);
void main (void)
{
int m;
int a[] = {3, 1, 9, 7, 8, 11, 7, 5};
printf("Type the number of values requied to be sorted ");
scanf("%i", &m);

printf("The sorted numbers are ");
sort(a[m], m);

//      sort(int m, int a[]);
}

void sort(int a[], int m)

{
int i,j,tmp;
for ( i=m-2; i>=0; i-- )
{
tmp = a[i];
for ( j=i+1; j<m && tmp>a[j]; j++ )
a[j-1] = a[j];
a[j-1] = tmp;

sort(&a[m],m);
}
return;

}
0

LVL 16

Accepted Solution

PaulCaswell earned 800 total points
ID: 16294193
Hi khawaib,

To sort, say, the last three elements of the array, you need to point to the start of that section of the array and pass the correct length of the remaining items:

sort(&a[m-3],3);

Sorry I have to be sort of cryptic. We help with homework questions gladly but we have to be careful about doing it for you.

Paul
0

Author Comment

ID: 16294316
Hi Paul,

Now It doesn't like 2nd parameter because its int and function void i guess

error C2664: 'printf' : cannot convert parameter 2 from 'void' to '...'

void sort(int a[], int m);

printf("The sorted numbers are ");
printf("%i", sort(&a[m],m));
sort(&a[m], m);

Thanks
0

LVL 16

Expert Comment

ID: 16294641
Hi khawaib,

You will have to print out the array in a loop after you sort it.

Paul
0

LVL 2

Expert Comment

ID: 16298018
You can use QuickSort, it's faster.

.....

void QuickSort(int l,int r)
{
int i,j,x,w;
i=l;
j=r;
x=a[round((l+r)/2)];
do
{      while(a[i]<x)i++;
while(a[j]>x)j--;
if(i<=j)
{
w=a[i];
a[i]=a[j];
a[j]=w;
i++;
j--;
}
}
while(i<=j)
if(l<j)QuickSort(l,j);
if(r>i)QuickSort(i,r);
}

......

void main(){
int a[];
......
//a will be filled with values
......
QuickSort(0,<length of a>);
......
}
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address.Ā This address might be address of another variable/address of devices/address of fuā¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soā¦
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.
###### Suggested Courses
Course of the Month13 days, 12 hours left to enroll