[H-12]
Write a function that carries out selection sort on an array of integers. If
you have seen selection sort before, see how much you remember and try to put
together a function that does it. Otherwise, read on...
Our selection sort arranges the values of an array into ascending order (low to high). Say that the array starts out as:
8 6 7 5 9 4 2 6
First, find the smallest integer in the entire array and exchange it with the element in slot zero.
8 6 7 5 9 4 2 6
2 6 7 5 9 4 8 6
Slot 0 now correctly holds the smallest value in the array, and we do not need to bother with it again. Now find the value that will go into slot 1. This is the smallest integer in the array to the right of slot zero. Exchange that value with the element in slot one:
2 6 7 5 9 4 8 6
2 4 7 5 9 6 8 6
Now slots 0 and 1 are correct. For slot 2, find the smallest integer in the rest of the array and exchange it with the element in slot two:
2 4 7 5 9 6 8 6
2 4 5 7 9 6 8 6
The algorithm continues the idea of repeatedly finding the smallest remaining element and placing it to the right of those elements already in place:
2 4 5 7 9 6 8 6
2 4 5 6 9 7 8 6
2 4 5 6 9 7 8 6
2 4 5 6 6 7 8 9
2 4 5 6 6 7 8 9
2 4 5 6 6 7 8 9
2 4 5 6 6 7 8 9
Sometimes an element is already in place, so it is swapped with itself and does not move.
Here is sample output:
34 70 34 23 83 41 53 20 54 62 21 21 37 42 23 80 2 22 43 73 82 89 29 73 41 12 100 98 72 51 35 89 50 32 49 67 83 63 72 34 22 67 51 51 42 8 89 69 55 1 25 elements out of order. 1 2 8 12 20 21 21 22 22 23 23 29 32 34 34 34 35 37 41 41 42 42 43 49 50 51 51 51 53 54 55 62 63 67 67 69 70 72 72 73 73 80 82 83 83 89 89 89 98 100 All elements are in order.
Here is a framework:
/* Puzzle D49 -- selection sort
|
*/
int selectionSort( int size, int arr[] )
{
. . . .
}
int inOrder( int size, int arr[] )
{
int j, count=0 ;
for ( j=0; j<size-1; j++ )
{
if ( arr[j] > arr[j+1] ) count++ ;
}
return count;
}
void printArray( int size, int arr[] )
{
const int N = 10;
int j;
for ( j=0; j<size; j++ )
{
if ( j%N == N-1 )
printf("%4d\n", arr[j] );
else
printf("%4d ", arr[j] );
}
}
int randInt( int min, int max )
{
return (rand()*(max-min+1))/(RAND_MAX+1) + min ;
}
void fillArrayRandom( int size, int arr[], int low, int high )
{
int j;
for ( j=0; j<size; j++ )
arr[j] = randInt( low, high );
}
int main()
{
const int SIZE = 50;
int x[SIZE] ;
int num;
srand( time( NULL ) );
fillArrayRandom( SIZE, x, 0, 100 );
printArray( SIZE, x );
num = inOrder( SIZE, x );
if ( num>0 )
printf("%d elements out of order.\n", num ) ;
else
printf("All elements are in order.\n");
printf("\n\n");
selectionSort( SIZE, x );
printArray( SIZE, x );
num = inOrder( SIZE, x );
if ( num>0 )
printf("%d elements out of order.\n", num ) ;
else
printf("All elements are in order.\n");
printf("\n\n");
return 0;
}