/*      Introduction to program:
        Program - inssort2.c.
        Sorts numerous reverse-ordered lists using the insertion sort algorithm.
        Francis O'Donovan 13-2-98. */

/*      Files to be #included. */

        #include <stdio.h>

/*      #definitions. */

/*      Function: main() */

        void main()
        {
                /*      Function definitions.   */
                        void inssort();

                /* Variable definitions. */

                /* Print introduction on screen. */

                        printf( "Program: inssort2.c.\n\n" );
                        printf( "Sorts a various lists using the insertion sort" );
                        printf( " algorithm.\n\n" );
                        printf( "Francis O'Donovan 13-2-98.\n\n" );

               /*       Call the insertion sort function for all the arrays      */
                        inssort( 10 );
                        inssort( 20 );
                        inssort( 30 );
                        inssort( 40 );
                        inssort( 50 );
                        inssort( 60 );
                        inssort( 70 );
                        inssort( 80 );
                        inssort( 90 );
                        inssort( 100 );
 
        }

/********************************************************/
/*      Function:       inssort().
        Purpose:        Declares an array of a certain size,
                initilizes it with reverse order elements,
                then sorts it using the insertion-sort algorithm.
        Arguements:     Int for size of array.
        Returns:        void.
*/
void inssort( size )
int size;
{
        /* Declare local variables. */
 
                int *int_array;           /* Pointer to first element of array. */
                int no_bytes;               /* Bytes required for array. */
                int h, i, j, k;                /* Counters. */
                int howlong = 0;            /* How long did it take to sort. */
                int key;                    /* key for Insertion sort algorithm. */

        /*      Assign memory for array.        */
 
                /* Calculate the number of bytes required by array for the numbers inputted. */

                        no_bytes = size * sizeof(int);

                /* Try to allocate memory, and return error if fail. */

                        int_array = malloc (no_bytes);

                        if ( int_array == NULL )
                                printf( "Cannot allocate memory for array!!!!\n" );
                        else
                        {

                /*      Initialize array.       */

                        i = size-1;

                        for( h=0; h<size; h++)
                        {
                                *(int_array + h ) = i;
                                i--;
                        }

                /*      Sort array using insertion sort algorithm.     */
 
                        for ( j = 1; j < size; j++ )  /* Goes through list*/
                        {
                                key = * (int_array + j);             /* Set the new key to A[j]. */
                                k = j - 1;              /* Go through list from right. */

                                while ( ( k >= 0) && ( *(int_array + k )  > key ) )
 
                        /* Do this until you reach the start of the list,
                        or you find the correct placement for key. */
 
                                {
                                        *(int_array + k + 1) = *(int_array + k);
                                        /* Move kth element to (k+1)th position. */
                                        k--;
                                        howlong++;      /* Increment howlong. */
                                }

                                *(int_array + k + 1) = key;
                                /* Put key in (k+1) position. */
                        }

                        /*      Print out how many times it took.       */
                                printf( "Size %d: %d.\n", size, howlong );

                         /*      Free memory.    */
                                free( int_array );
                 }
}

© Francis O'Donovan 1999.