REVISED: Sunday, March 15, 2015
CONTENTS:
• I. C SELECTION SORT INTRODUCTION
• II. C ARRAY REVIEW
• III. C SELECTION SORT
• IV. C SELECTION SORT EXAMPLE PROGRAM ANALYSIS
• V. C SELECTION SORT EXAMPLE PROGRAM SOURCE CODE
• VI. C SELECTION SORT REFERENCES
YOU WILL LEARN:
1. The C array.
2. How to write a C selection sort program.
I. C SELECTION SORT INTRODUCTION
Welcome to the “C Selection Sort Tutorial.”
II. C ARRAY REVIEW
A. Array Declaration
A two dimensional array with 4 rows and 2 columns is declared as a[4][2] or a[][2].
int a[][2] = { {66,45},
{33,18},
{12,84},
{22,44} };
B. Array Base Address
The name of the array, in this case a, is a pointer to array a[][2]. a points to a[0][0], row 0 column 0, the base address of array a.
C. Computer Memory
All arrays, one-dimensional, two-dimensional, three-dimensional, etc., are stored linearly in computer memory.
Therefore, array a is treated as four one dimensional arrays with the elements stored in a linear contiguous fasion in an unbroken sequence of addresses in computer memory as shown below:
D. Pointers
1. a[0] is a pointer to the first row first element, base address of array a.
2. a[0] is equivalent to *(a), they both point to the first row first element, base address of array a.
3. a[i] is equivalent to *(a+i), they both point to the ith row of array a.
E. Pointers and Two-Dimensional Arrays
1. All things being equal, a program written with pointer arithmetic will normally run faster than the same program with array indexing.
2. A two-dimensional array can be reduced to a pointer to an array of one-dimensional arrays.
3. In general for any two-dimensional array a[j][k] is equivalent to *((base-type *)a+(j*row length)+k).
For example, given int a[4][2]; a[1][1] is equivlalent to *((int*)a+(1*sizeof(int))+1).
4. a[i]+j points to the [i,j]th element of array a.
5. *(*(a+i)+j) is equivalent to *(a[i]+j), both are the [i,j]th element of array a.
6. Array a is a two dimensional array; therefore, we need an array of pointers to point to a.
The array of pointers to array a[4][2] is declared as:
int (*row)[2]
row is now an array of pointers.
Declaring
row =a;
will make row point to the base address of a. This means that row is pointing to the first row first element of array a.
By pointing another pointer int *column to row:
int *column;
column=(int*)row;
we can now read off the elements in the two columns of a row as *(column) and *(column+1).
Notice we had to use a type cast (int*) to point a pointer to another pointer.
When we increment row by one with statement
row++
we point to the next row of array a.
Keep in mind row is the array of pointers, int *row[2], and column is the pointer, int *column.
III. C SELECTION SORT
Sorting, is arranging the elements of an array in ascending or descending order.
To selection sort an array in ascending order, from smallest to largest, find the smallest element in the unsorted set of array elements and move it to its final position in the sorted set of array elements. Each time we do this we are reducing the size of the unsorted set of array elements by one element. The process stops when the size of the unsorted set of array elements becomes 1. The process stops because an unsorted set of array elements of 1 element is already sorted.
The example program has two options. Option zero screen prints the selection sorted array. Option one screen prints the audit trail of the selection sort. Once you understand how to read the audit trail you will see it is a very detailed explanation of how the selection sort program works.
I will walk you through a couple of swaps to help you understand how to read the audit trail documentation.
1. Total Swaps: 0
The array before sorting starts.
It is easier to understand selection sorting if you think of the total array as having two sets of array elements; i.e., a sorted set of array elements and an unsorted set of array elements.
Think of the array as being from left to right a linear unsorted set of array elements; for example:
66 45 33 18 12 84 22 44
0 1 2 3 4 5 6 7 <= Linear one-dimensional array i and j index subscript.
45 is less than 66; therefore, 45 and 66 swap places. In other words, 45 is removed from the unsorted set of array elements and placed in the sorted set of array elements as the smallest element.
45 66 33 18 12 84 22 44
0 1 2 3 4 5 6 7 <= i outter loop and j inner loop array index.
Notice element 45 came from array index 1.
Now we are only concerned with the unsorted set of array elements.
However, we still do not know if 45 is the smallest number in the array. Therefore, we continue with the selection sort, starting from index 1, and compare 66 to 33 to see which is smaller. We discover 33 is smaller than 66; therefore, we compare 33 to 45 to see which is smaller.
3. Total Swaps: 2
We discover 33 is smaller than 45; therefore, 33 and 45 swap places. In other words, 33 is removed from the unsorted set of array elements and placed in the sorted set of array elements as the smallest element, and 45 is back in the unsorted set of array elements.
Notice element 33 came from array index 2.
33 66 45 18 12 84 22 44
0 1 2 3 4 5 6 7 <= Array index.
Now we are only concerned with the unsorted set of array elements.
However, we still do not know if 33 is the smallest number in the array. Therefore, we continue with the selection sort, starting from index 2, and compare 45 to 18 to see which is smaller. We discover 18 is smaller than 45; therefore, we compare 18 to 33 to see which is smaller.
We discover 18 is smaller than 33; therefore, 18 and 33 swap places. In other words, 18 is removed from the unsorted set of array elements and placed in the sorted set of array elements as the smallest element, and 33 is back in the unsorted set of array elements.
Notice element 18 came from array index 3.
18 66 45 33 12 84 22 44
0 1 2 3 4 5 6 7 <= Array index.
Now we are only concerned with the unsorted set of array elements.
However, we still do not know if 18 is the smallest number in the array. Therefore, we continue with the selection sort, starting from index 3, and compare 33 to 12 to see which is smaller. We discover 12 is smaller than 33; therefore, we compare 12 to 18 to see which is smaller.
5. Total Swaps: 4
We discover 12 is smaller than 18; therefore, 12 and 18 swap places. In other words, 12 is removed from the unsorted set of array elements and placed in the sorted set of array elements as the smallest element, and 18 is back in the unsorted set of array elements.
Notice element 12 came from array index 4.
12 66 45 33 18 84 22 44
0 1 2 3 4 5 6 7 <= Array index.
Now we are only concerned with the unsorted set of array elements.
However, we still do not know if 12 is the smallest number in the array. Therefore, we continue with the selection sort, starting from index 4, and compare 18 to 84 to see which is smaller. We discover 18 is smaller than 84; therefore, we compare 18 to 12 to see which is smaller.
6. Total Swaps: 5
We discover 12 is smaller than 18.
We compare 18 to 84 to see which is smaller. We discover 18 is smaller than 84. We compare 18 to 22 to see which is smaller. We discover 18 is smaller than 22. We compare 18 to 44 to see which is smaller. We discover 18 is smaller than 44.
Now we are only concerned with the unsorted set of array elements. Therefore, we continue with the selection sort, starting from index 1, and compare 66 to 45 to see which is smaller. We discover 45 is smaller than 66; therefore, 45 and 66 swap places. In other words, 45 is removed from the unsorted set of array elements and placed in its proper place in the sorted set of array elements.
Notice element 45 came from array index 2.
12 45 66 33 18 84 22 44
0 1 2 3 4 5 6 7 <= Array index.
Now we are only concerned with the unsorted set of array elements.
However, we still do not know if 45 is the next smallest number in the array. Therefore, we continue with the selection sort, starting from index 2, and compare 66 to 33 to see which is smaller. We discover 33 is smaller than 66; therefore, we compare 33 to 45 to see which is smaller.
I think these are enough examples and you should be able to follow the documentation in the audit trail. Please post any questions you have in the comments section and I will post replies.
V. C SELECTION SORT EXAMPLE PROGRAM SOURCE CODE
/****************************
C SELECTION 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 SELECTION SORT\n" \
" C SORT TUTORIAL\n" \
" PART 1\n\n" \
" 0 Execute function zero, SELECTION SORT.\n\n" \
" 1 Execute function one, SELECTION SORT with audit trail.\n\n" \
" Type number 0, or 1 and then press Enter.\n\n"\
" EXIT by typing 2 and then pressing Enter. "
#define RULER \
" Column Column\n"\
" Zero One\n\n"\
" Row Zero 66 45\n"\
" Row One 33 18\n"\
" Row Two 12 84\n"\
" Row Three 22 44\n\n"\
" In computer memory an array is stored linearly\n"\
" as follows:\n\n"\
" 66 45 33 18 12 84 22 44\n\n"\
" 00 01 02 03 04 05 06 07 <= Linear array row column index.\n"\
" 00 01 10 11 20 21 30 31 <= Two-dimensional array index. \n\n"\
" 0 1 2 3 4 5 6 7 <= Outter Loop i array index.\n"\
" 0 1 2 3 4 5 6 7 <= Inner Loop j array index.\n\n"
#define ROW 4
/*
Max array rows.
*/
char nxt;
/*
FUNCTION PROTOTYPES
*/
int getInteger( int *maybe );
void zero( int );
void one ( int );
/*
Passing an array to a two dimensional pointer array.
*/
void arrayToTwoDimPtrArray( int ( *b )[ 4 ][ 2 ], int *swap );
/*
SELECTION SORT
*/
void selectionSort( int a[][2], int rXc, int *swap );
/*
SELECTION SORT with audit trail.
*/
void selectionSortAudit( int a[][2], int rXc, int *swap );
int main( int argc, char* argv[] )
{
/*
Initialize array of two pointers to functions which take an int argument and return void.
*/
void( *ptr2Fcn[ 2 ])( int )= { zero, one };
/*
Screen print menu.
*/
printf( HEADER );
/*
User types menu selection.
*/
int menuSelection;
do
{
fflush( stdout );
} while ( !getInteger( &menuSelection ) );
while(( menuSelection >= 0 ) && ( menuSelection < 2 ))
{
/*
Invoke the function at location menuSelection in the array ptr2Fcn and pass menuSelection as an argument.
*/
( *ptr2Fcn[ menuSelection ]) ( menuSelection );
printf( HEADER );
do
{
fflush( stdout );
} while ( !getInteger( &menuSelection ) );
}
return 0;
}
/*
FUNCTION DEFINITIONS
*/
int getInteger( int *maybe )
{
char alpha, buff [ 80 ];
return fgets(buff, sizeof buff, stdin) && !isspace( *buff ) &&
sscanf( buff, "%d%c", maybe, &alpha ) == 2 && ( alpha == '\n' || alpha == '\0' );
}
/*
Passing an array to a two dimensional pointer array.
*/
void arrayToTwoDimPtrArray( int ( *b )[ 4 ][ 2 ], int *swap )
{
int i;
printf( "\n\n" );
for( i=0; i<ROW; i++ )
{
printf( " %5d %5d \n", ( *b )[i][0], ( *b )[i][1] );
}
printf( "\n\n Total Swaps: %d\n", *swap );
printf( " *********************\n\n\n");
return;
}
void zero( int x )
{
printf ( "\n\n You entered %d; therefore, function zero, the SELECTION SORT was called.\n\n", x );
/*
Declaration of array a[ 4 ][ 2 ].
*/
int a[][2] = { { 66, 45 },
{ 33, 18 },
{ 12, 84 },
{ 22, 44 } };
int swap = 0;
int rXc = 8;
/*
Passing an array to a two dimensional pointer array.
*/
arrayToTwoDimPtrArray( &a, &swap );
/*
Selection Sort of a two dimensional pointer array of 4 rows and 2 columns.
*/
selectionSort( a, rXc, &swap );
/*
Passing an array to a two dimensional pointer array.
*/
arrayToTwoDimPtrArray( &a, &swap );
}
/*
selectionSort
*/
void selectionSort( int a[][2], int rXc, int *swap )
{
int *pArray;
pArray = (int*)a;
int i;
int j;
int temp;
for(i=0; i < (rXc-1); i++)
{
for(j = i + 1; j < rXc; j++)
{
if(*(pArray + i) > *(pArray + j))
{
temp = *(pArray+i);
*(pArray + i) = *(pArray + j);
*(pArray + j) = temp;
(*swap)++;
}
}
}
}
void one( int y )
{
printf ( "\n\n You entered %d; therefore, function one, the SELECTION SORT with\n", y );
printf ( " audit trail was called.\n\n");
/*
Declaration of array a[ 4 ][ 2 ].
*/
int a[][2] = { { 66, 45 },
{ 33, 18 },
{ 12, 84 },
{ 22, 44 } };
/*
Column Column
Zero One
Row Zero 66 45
Row One 33 18
Row Two 12 84
Row Three 22 44
In computer memory an array is stored linearly
as follows:
66 45 33 18 12 84 22 44
00 01 02 03 04 05 06 07 <= Linear array row column index.
00 01 10 11 20 21 30 31 <= Two-dimensional array index.
0 1 2 3 4 5 6 7 <= Outter Loop i array index.
0 1 2 3 4 5 6 7 <= Inner Loop j array index.
*/
int swap = 0;
int rXc = 8;
/*
Passing an array to a two dimensional pointer array.
*/
arrayToTwoDimPtrArray( &a, &swap );
/*
Screen print menu.
*/
printf( RULER );
/*
Selection Sort of a two dimensional pointer array of 4 rows and 2 columns.
*/
selectionSortAudit( a, rXc, &swap );
/*
Passing an array to a two dimensional pointer array.
*/
arrayToTwoDimPtrArray( &a, &swap );
}
/*
Selection Sort Audit Trail
*/
void selectionSortAudit( int a[][2], int rXc, int *swap )
{
int *pArray;
pArray = (int*)a;
int i = 0;
int j = 0;
int temp = 0;
for(i = 0; i < (rXc - 1); i++)
{
printf( "\n\n Outter loop i = %d\n", i );
printf( " Inner loop j = %d\n\n", j );
for(j = i + 1; j < rXc; j++)
{
printf( "\n\n Outter loop i = %d\n", i );
printf( " Inner loop j = %d\n\n", j );
printf( "\n\n Compare %d (i = %d) and %d (j = %d).\n\n", *(pArray+i), i, *(pArray+j), j );
if(*(pArray + i) > *(pArray + j))
{
printf( "\n\n If %d ((i = %d) > %d (j = %d)) then swap.\n\n", *(pArray+i), i, *(pArray+j), j );
temp = *(pArray + i);
*(pArray + i) = *(pArray + j);
*(pArray + j) = temp;
(*swap)++;
int k;
printf( "\n\n" );
for( k = 0; k < ROW; k++ )
{
printf( " %5d %5d \n", a[k][0], a[k][1] );
}
printf( "\n\n Total Swaps: %d\n", *swap );
printf( " *********************\n\n\n");
printf( " Press any key to continue:\n\n\n ");
nxt = getchar();
}
}
}
}
VI. C SELECTION 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. The C array.
2. How to write a C selection sort 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