?
Solved

Insertion Sort by Top-down recursive function

Posted on 2006-03-26
9
Medium Priority
?
291 Views
Last Modified: 2010-04-15
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[])

 {
//int answer=0;
//       if(m>0){
      //       answer = sort(m, a[answer]);
             
//       {
      
printf("%i",  a[m]);

       }

Thanks
0
Comment
Question by:khawaib
  • 4
  • 2
7 Comments
 
LVL 16

Expert Comment

by:PaulCaswell
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

by:PaulCaswell
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

by:khawaib
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 16

Accepted Solution

by:
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

by:khawaib
ID: 16294316
Hi Paul,

Thanks for your help

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

by:PaulCaswell
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

by:Razor2k5
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

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

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…
Video by: Grant
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

755 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question