Page 1 of 1

SELECTION SORT C SORT TUTORIAL PART 1 Rate Topic: -----

#1 Elcric  Icon User is offline

  • D.I.C Regular
  • member icon

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

Posted 15 July 2010 - 03:30 PM

SELECTION SORT
C SORT TUTORIAL
PART 1

CONTENTS
• I. INTRODUCTION
• II. ARRAY REVIEW
• III. SELECTION SORT
• IV. EXAMPLE PROGRAM ANALYSIS
• V. EXAMPLE PROGRAM
• VI. REFERENCES


I. INTRODUCTION

Hello; nice to meet you. Welcome to “Selection Sort - C Sort Tutorial Part 1.”

II. 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:

66, 45, 33, 18, 12, 84, 22, 44


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. 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.


IV. EXAMPLE PROGRAM ANALYSIS

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.

2. Total Swaps: 1

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.

4. Total Swaps: 3

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. EXAMPLE PROGRAM

/* ***************************
   SELECTION SORT
   C SORT TUTORIAL
   PART 1
   *************************** */
#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. 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