/*	Test driver for sorting. 
	
	Written by: G & F
	Date:       2/98
	
    Brooks/Cole Publishing Company
	An International Thomson Publishing Company
	Copyright 1998. All Rights Reserved
*/
#include <stdio.h>
#define MAX_ARY_SIZE 15

/*	Prototype Declarations */
void	insertionSort (int list[ ], int last );
	
int main ( void ) 
{
	
/*	Local Declarations */
	int i;
	int	ary[ MAX_ARY_SIZE ] = { 89, 72, 3,  15, 21, 
							    57, 61, 44, 19, 98, 
							    5,  77, 39, 59, 61 };

/*	Statements */
	printf( "Unsorted array: " );
	for ( i = 0; i < MAX_ARY_SIZE; i++ )
		printf( "%3d", ary[ i ] );
		
	insertionSort ( ary, MAX_ARY_SIZE - 1);

	printf( "\nSorted array:   " );
	for ( i = 0; i < MAX_ARY_SIZE; i++ )
		printf( "%3d", ary[ i ] );
	printf( "\n" );
	return 0;
}	/* main */

/*	==================== Sort Algorithm ==================== */

/*	Sort list using Insertion Sort. The list is divided into 
	sorted and unsorted list. With each pass, first element 
	in unsorted list is inserted into sorted list.
	Pre   list must contain at least one element.
	      last contains index to last element in the list
	Post  list has been rearranged.
*/
void insertionSort (int list[ ], 
                    int last ) 
{
/*	Local Declarations */
	int current;
	int hold;
	int walker;

/*	Statements */
	for ( current = 1; current <= last; current++ )
	   {
	    hold = list[current];
	    for (walker = current - 1; 
	         walker >= 0 && hold < list[walker]; 
	        )
	       {
	        list[walker + 1] = list[walker];
	        walker--;
	       } /* for walker */
	
	    list [walker + 1] = hold;
	   } /* for current */

	return;
}	/* insertionSort */


/*
Results:
	Unsorted array:  89 72  3 15 21 57 61 44 19 98  5 77 39 59 61
	Sorted array:     3  5 15 19 21 39 44 57 59 61 61 72 77 89 98
*/