Page 1 of 1

INSERTION SORT C SORT TUTORIAL PART 3 Rate Topic: ***** 1 Votes

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 101
  • View blog
  • Posts: 453
  • Joined: 02-May 09

Posted 21 July 2010 - 10:20 AM

INSERTION SORT
C SORT TUTORIAL
PART 3

CONTENTS
• I. INTRODUCTION
• II. INSERTION SORT
• III. EXAMPLE PROGRAM ANALYSIS
• IV. EXAMPLE PROGRAM
• V. REFERENCES


I. INTRODUCTION

Hello; nice to meet you. Welcome to “Insertion Sort - C Sort Tutorial Part 3.”

II. INSERTION SORT

Sorting a deck of playing cards is an insertion sort. You shuffle the deck, place the deck on top of a table, and pick up the first card. The insertion sort splits the set of cards into two sub-sets. The first card picked up becomes the sorted sub-set. You perform the insertion sort each time you pick up an additional card and insert it into its correct position in your hand, the sorted sub-set. The cards remaining on the table is the unsorted sub-set. An insertion sort program only passes through the unsorted sub-set one time.

III. EXAMPLE PROGRAM ANALYSIS

Given the following two-dimensional array a[4][2]:

66 45
33 18
12 84
22 44

The array a[4][2] would be stored in computer memory linearly as follows:

66 45 33 18 12 84 22 44
..0..1...2..3...4..5...6..7 <= Insertion Selection

The example insertion sort program is preceeded by a conversion of the two-dimensional array into a one-dimensional array. The conversion is not part of the insertion sort. However, the one-dimensional arrray closely mimics the way the two-dimensional array is stored in memory and will make it easier for me to describe the execution of the insertion sort program.

The example insertion sort program documentation explains the insertion sort process in detail.

For example, using the color red for the unsorted sub-set and blue for the sorted sub-set, the insertion sort works as follows:

Linear array after insertion 0: 66 45 33 18 12 84 22 44
Linear array after insertion 1: 45 66 33 18 12 84 22 44
Linear array after insertion 2: 33 45 66 18 12 84 22 44
Linear array after insertion 3: 18 33 45 66 12 84 22 44
Linear array after insertion 4: 12 18 33 45 66 84 22 44
Linear array after insertion 5: 12 18 33 45 66 84 22 44
Linear array after insertion 6: 12 18 22 33 45 66 84 44
Linear array after insertion 7: 12 18 22 33 44 45 66 84

As you can see, an insertion sort program only passes through the unsorted sub-set one time.


IV. EXAMPLE PROGRAM

/* ***************************
   INSERTION SORT
   C SORT TUTORIAL
   PART 3
   *************************** */
#include<ctype.h>     /*  Character Class Tests  */
#include<math.h>      /*  Math Header.           */
#include<stdio.h>     /*  Standard I/O.          */
#include<stdlib.h>    /*  Utility Functions.     */

#define HEADER \
    "\n\n  INSERTION SORT\n" \
	"  C SORT TUTORIAL\n" \
	"  PART 3\n\n" \

#define SIZE 8

/*  Converting two-dimensional array to one-dimensional array.  */
void arrayToArray( int bb[][2], int rr, int cc, int a[8] );

/*  Insertion Sort.  */
void insertionSort(int a[] );  

/*  Converting one-dimensional array to two-dimensional array.  */
void arrayConversion( int aa[][2], int rr, int cc, int a[8] );  

int main( int argc, char* argv[] )
{
	char nxt;
	int  c    = 2;  /*  Columns.  */
	int  i    = 0;
	int  j    = 0;
	int  k    = 0;
	int  r    = 4;  /*  Rows.     */
		
	/*  Declaration of array aa[ 4 ][ 2 ].  */
	int aa[][2] = { { 66, 45 },
				    { 33, 18 },
				    { 12, 84 },
				    { 22, 44 } };

	/*  Declaration of array a[8].  */
	int a[8];

	printf( HEADER );
	
	/*  Converting two-dimensional array to one-dimensional array.  */
	arrayToArray( aa, r, c, a );     
				
	/*  Insertion Sort.  */
	insertionSort( a ); 
	
	printf("\n\n");

	printf("\n  ********************************\n\n");
	printf( "  Press any key to continue:  ");
	nxt = getchar();
	printf("\n\n");
	
	/*  Display sorted ONE-DIMENSIONAL ARRAY.  */
	printf("\n  SORTED LINEAR ONE-DIMENSIONAL ARRAY:\n\n  ");
    for(k = 0; k < SIZE; k++) printf("%d  ", a[k]);

	printf("\n\n");
	printf( "  Press any key to continue:  ");
				
	nxt = getchar();
	printf("\n\n");

	arrayConversion( aa, r, c, a );

	printf("\n\n");
	printf( "  Press any key to EXIT:  ");
				
	nxt = getchar();

	return 0;
}

/*  Converting two-dimensional array to one-dimensional array.  
    rr rows, cc columns  */
void arrayToArray( int bb[][2], int rr, int cc, int a[8] )   
{
	int i = 0;
	int j = 0;
	int k = 0;
	int l = 0;
	int m = 0;

	printf( "\n\n  UNSORTED TWO-DIMENSIONAL ARRAY:.\n\n" );
	for( i=0; i<rr; i++ )
	{
		printf( "     %5d  %5d \n", bb[i][0], bb[i][1] );
	}

	for (j = 0; j < rr; j++)
	{
		for (k = 0; k < cc; k++)
		{
		a[l] = bb[j][k];
		l++;
		}
	}

	/*  Display unsorted array.  */
	printf("\n\n  UNSORTED LINEAR ONE-DIMENSIONAL ARRAY:\n\n  ");
	for(m = 0; m < SIZE; m++) printf("%d  ", a[m]);
	printf("\n   0   1   2   3   4   5   6   7 <= Insertion Selection\n");
	printf("\n\n  ********************************\n");

	return;
}

/*  Converting one-dimensional array to two-dimensional array.
    rr rows, cc columns  */
void arrayConversion( int aa[][2], int rr, int cc, int a[8] )   
{
	int i = 0;
	int j = 0;
	int k = 0;
	int l = 0;
	
	for (j = 0; j < rr; j++)
	{
		for (k = 0; k < cc; k++)
		{
		aa[j][k] = a[l];
		l++;
		}
	}

	/*  Display sorted array.  */
	printf("\n\n  SORTED TWO-DIMENSIONAL ARRAY:\n\n");
	for( i=0; i<rr; i++ )
	{
		printf( "     %5d  %5d \n", aa[i][0], aa[i][1] );
	}
	printf("\n\n  ********************************\n\n");

	return;
}

/*  Insertion Sort.  */
void insertionSort(int a[] )  
{  
	int i;
	int j;
	int k;
	int l;

	for(i = 0; i <= SIZE-1; i++)  
	{  
		j = i;  
		l = a[i];  
		while((a[j-1] > l) && (j > 0))  
		{  
			a[j] = a[j-1];  
			j = j-1;  
		}  
		a[j] = l;  
		printf("\n\n  Linear array after insertion %d: ", i);  
		for(k = 0; k <= SIZE-1; k++)
		{
			printf("%4d", a[k]);  
		}
	}
} 



V. REFERENCES

The C Programming Language by Brian Kernighan and Dennis Ritchie (Englewood Cliffs, N.J.: Prentice-Hall, 1978).

The C Programming Language Second Edition by Brian Kernighan and Dennis Ritchie (Upper Saddle River, N.J.: Prentice-Hall PTR, 1988).


Is This A Good Question/Topic? 1
  • +

Page 1 of 1