REVISED: Sunday, March 15, 2015
CONTENTS:
• I. C INSERTION SORT INTRODUCTION
• II. C INSERTION SORT
• III. C INSERTION SORT EXAMPLE PROGRAM ANALYSIS
• IV. C INSERTION SORT EXAMPLE PROGRAM SOURCE CODE
• V. C INSERTION SORT REFERENCES
YOU WILL LEARN:
1. C insertion sort.
2. How to write a C insertion program.
I. C INSERTION SORT INTRODUCTION
Welcome to the “C Insertion Sort Tutorial.”
II. C 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.
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. C INSERTION SORT EXAMPLE PROGRAM SOURCE CODE
/****************************
C INSERTION SORT
****************************/
#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" \
" \n" \
" \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. C INSERTION SORT 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).
YOU HAVE LEARNED:
1. C insertion sort.
2. How to write a C insertion program.
Elcric Otto Circle
-->
-->
How to Link to My Home Page
It will appear on your website as:"Link to ELCRIC OTTO CIRCLE's Home Page"
No comments:
Post a Comment