(Selection Sort) A selection sort searches an array looking for the smallest element. Then, the smallest element is swapped with the first element of the array. The process is repeated for the subarray beginning with the second element of the array. Each pass of the array results in one ele- ment being placed in its proper location. This sort performs comparably to the insertion sort—for an

Question

array of n elements, n – 1 passes must be made, and for each subarray, n – 1 comparisons must be made to find the smallest value. When the subarray being processed contains one element, the array is sorted. Write recursive function selectionSort to perform this algorithm.

What will be an ideal response?

Answer 1

```
#include
#include
#include
using namespace std;

void selectionSort( int [], int );

int main()
{
const int SIZE = 10;
const int MAXRANGE = 1000;
int sortThisArray[ SIZE ] = {};

srand( time( 0 ) );
// fill array with random numbers between 1-1000
for ( int i = 0; i < SIZE; i++ )
sortThisArray[ i ] = 1 + rand() % MAXRANGE;

cout << "\nUnsorted array is:\n";

// display unsorted array
for ( int j = 0; j < SIZE; j++ )
cout << ' ' << sortThisArray[ j ] << ' ';

selectionSort( sortThisArray, SIZE ); // sort the array

cout << "\n\nSorted array is:\n";

// display sorted array
for ( int k = 0; k < SIZE; k++ )
cout << ' ' << sortThisArray[ k ] << ' ';

cout << '\n' << endl;
} // end main

// function to sort an array
void selectionSort( int array[], int size )
{
int temp; // temporary variable used for swapping

// sort array until only one element is left
if ( size >= 1 )
{
// find smallest element and put it in first position
for ( int loop = 0; loop < size; loop++ )
{
if ( array[ loop ] < array[ 0 ] )
{
temp = array[ loop ];
array[ loop ] = array[ 0 ];
array[ 0 ] = temp;
} // end inner if
} // end for

// recursive call to selectionSort
selectionSort( &array[ 1 ], size - 1 );
} // end outer if
} // end method selectionSort
```
Unsorted array is:
618 367 758 178 797 635 792 552 703 749
Sorted array is:
178 367 552 618 635 703 749 758 792 797