Selection Sort Using Pass-by-Reference
In this section, we define a sorting program to demonstrate passing arrays and individual array elements by reference. We use the selection sort algorithm, which is an easy-to-program, but unfortunately inefficient, sorting algorithm. The first iteration of the algorithm selects the smallest element in the array and swaps it with the first element. The second iteration selects the second-smallest element (which is the smallest element of the remaining elements) and swaps it with the second element. The algorithm continues until the last iteration selects the second-largest element and swaps it with the second-to-last index, leaving the largest element in the last index. After the ith iteration, the smallest i items of the array will be sorted into increasing order in the first i elements of the array.
As an example, consider the array
34 56 4 10 77 51 93 30 5 52
A program that implements selection sort first determines the smallest element (4) of this array, which is contained in element 2. The program swaps the 4 with the element 0 (34), resulting in
4 56 34 10 77 51 93 30 5 52
[Note: We use bold to highlight the values that were swapped.] The program then determines the smallest value of the remaining elements (all elements except 4), which is 5, contained in element 8. The program swaps the 5 with the element 1 (56), resulting in
4 5 34 10 77 51 93 30 56 52
On the third iteration, the program determines the next smallest value (10) and swaps it with the element 2 (34).
4 5 10 34 77 51 93 30 56 52
The process continues until the array is fully sorted.
4 5 10 30 34 51 52 56 77 93
Note that after the first iteration, the smallest element is in the first position. After the second iteration, the two smallest elements are in order in the first two positions. After the third iteration, the three smallest elements are in order in the first three positions.
Figure 8.15 implements selection sort using two functionsselectionSort and swap. Function selectionSort (lines 3653) sorts the array. Line 38 declares the variable smallest, which will store the index of the smallest element in the remaining array. Lines 4152 loop size - 1 times. Line 43 sets the index of the smallest element to the current index. Lines 4649 loop over the remaining elements in the array. For each of these elements, line 48 compares its value to the value of the smallest element. If the current element is smaller than the smallest element, line 49 assigns the current element's index to smallest. When this loop finishes, smallest will contain the index of the smallest element in the remaining array. Line 51 calls function swap (lines 5762) to place the smallest remaining element in the next spot in the array (i.e., exchange the array elements array[ i ] and array[ smallest ]).
Figure 8.15. Selection sort with pass-by-reference.
(This item is displayed on pages 419 - 420 in the print version)
|
1 // Fig. 8.15: fig08_15.cpp 2 // This program puts values into an array, sorts the values into 3 // ascending order and prints the resulting array. 4 #include 5 using std::cout; 6 using std::endl; 7 8 #include 9 using std::setw; 10 11 void selectionSort( int * const, const int ); // prototype 12 void swap( int * const, int * const ); // prototype 13 14 int main() 15 { 16 const int arraySize = 10; 17 int a[ arraySize ] = { 2, 6, 4, 8, 10, 12, 89, 68, 45, 37 }; 18 19 cout << "Data items in original order "; 20 21 for ( int i = 0; i < arraySize; i++ ) 22 cout << setw( 4 ) << a[ i ]; 23 24 selectionSort( a, arraySize ); // sort the array 25 26 cout << " Data items in ascending order "; 27 28 for ( int j = 0; j < arraySize; j++ ) 29 cout << setw( 4 ) << a[ j ]; 30 31 cout << endl; 32 return 0; // indicates successful termination 33 } // end main 34 35 // function to sort an array 36 void selectionSort( int * const array, const int size ) 37 { 38 int smallest; // index of smallest element 39 40 // loop over size - 1 elements 41 for ( int i = 0; i < size - 1; i++ ) 42 { 43 smallest = i; // first index of remaining array 44 45 // loop to find index of smallest element 46 for ( int index = i + 1; index < size; index++ ) 47 48 if ( array[ index ] < array[ smallest ] ) 49 smallest = index; 50 51 swap( &array[ i ], &array[ smallest ] ); 52 } // end if 53 } // end function selectionSort 54 55 // swap values at memory locations to which 56 // element1Ptr and element2Ptr point 57 void swap( int * const element1Ptr, int * const element2Ptr ) 58 { 59 int hold = *element1Ptr; 60 *element1Ptr = *element2Ptr; 61 *element2Ptr = hold; 62 } // end function swap
|
Let us now look more closely at function swap. Remember that C++ enforces information hiding between functions, so swap does not have access to individual array elements in selectionSort. Because selectionSort wants swap to have access to the array elements to be swapped, selectionSort passes each of these elements to swap by referencethe address of each array element is passed explicitly. Although entire arrays are passed by reference, individual array elements are scalars and are ordinarily passed by value. Therefore, selectionSort uses the address operator (&) on each array element in the swap call (line 51) to effect pass-by-reference. Function swap (lines 5762) receives &array[ i ] in pointer variable element1Ptr. Information hiding prevents swap from "knowing" the name array[ i ], but swap can use *element1Ptr as a synonym for array[ i ]. Thus, when swap references *element1Ptr, it is actually referencing array[ i ] in selectionSort. Similarly, when swap references *element2Ptr, it is actually referencing array[ smallest ] in selectionSort.
Even though swap is not allowed to use the statements
hold = array[ i ]; array[ i ] = array[ smallest ]; array[ smallest ] = hold;
precisely the same effect is achieved by
int hold = *element1Ptr; *element1Ptr = *element2Ptr; *element2Ptr = hold;
in the swap function of Fig. 8.15.
Several features of function selectionSort should be noted. The function header (line 36) declares array as int * const array, rather than int array[], to indicate that function selectionSort receives a one-dimensional array as an argument. Both parameter array's pointer and parameter size are declared const to enforce the principle of least privilege. Although parameter size receives a copy of a value in main and modifying the copy cannot change the value in main, selectionSort does not need to alter size to accomplish its taskthe array size remains fixed during the execution of selectionSort. Therefore, size is declared const to ensure that it is not modified. If the size of the array were to be modified during the sorting process, the sorting algorithm would not run correctly.
Note that function selectionSort receives the size of the array as a parameter, because the function must have that information to sort the array. When a pointer-based array is passed to a function, only the memory address of the first element of the array is received by the function; the array size must be passed separately to the function.
By defining function selectionSort to receive the array size as a parameter, we enable the function to be used by any program that sorts one-dimensional int arrays of arbitrary size. The size of the array could have been programmed directly into the function, but this would restrict the function to processing an array of a specific size and reduce the function's reusabilityonly programs processing one-dimensional int arrays of the specific size "hard coded" into the function could use the function.
Software Engineering Observation 8.4
|
When passing an array to a function, also pass the size of the array (rather than building into the function knowledge of the array size). This makes the function more reusable. |