Recursive Insertion Sort

This is a discussion on Recursive Insertion Sort within the C Programming forums, part of the General Programming Boards category; I managed to write the following insertion sort program but I'm meant to do it recursively. Any ideas how to ...

  1. #1
    help me!
    Guest

    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;
    }

  2. #2
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 5
    Last Post: 08-02-2008, 06:23 AM
  2. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. recursive insertion sort.
    By Alien_Freak in forum C++ Programming
    Replies: 3
    Last Post: 03-23-2002, 12:31 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21