Previous: 10.2 Improving Search - Sorting the Data
Up: 10.2 Improving Search - Sorting the Data
Next: 10.2.2 Bubble Sort
Previous Page: 10.2 Improving Search - Sorting the Data
Next Page: 10.2.2 Bubble Sort
Previous: 10.2 Improving Search - Sorting the Data
Up: 10.2 Improving Search - Sorting the Data
Next: 10.2.2 Bubble Sort
Previous Page: 10.2 Improving Search - Sorting the Data
Next Page: 10.2.2 Bubble Sort
The idea of selection sort is rather simple: we repeatedly find the next largest (or smallest) element in the array and move it to its final position in the sorted array. Assume that we wish to sort the array in increasing order, i.e. the smallest element at the beginning of the array and the largest element at the end. We begin by selecting the largest element and moving it to the highest index position. We can do this by swapping the element at the highest index and the largest element. We then reduce the effective size of the array by one element and repeat the process on the smaller (sub)array. The process stops when the effective size of the array becomes 1 (an array of 1 element is already sorted).
For example, consider the following array, shown with array elements in sequence separated by commas:
The leftmost element is at index zero, and the rightmost element is at the highest array index, in our case, 4 (the effective size of our array is 5). The largest element in this effective array (index 0-4) is at index 2. We have shown the largest element and the one at the highest index in bold. We then swap the element at index 2 with that at index 4. The result is:
We reduce the effective size of the array to 4, making the highest index in the effective array now 3. The largest element in this effective array (index 0-3) is at index 1, so we swap elements at index 1 and 3 (in bold):
The next two steps give us:
The last effective array has only one element and needs no sorting. The entire array is now sorted. The algorithm for an array, x, with lim elements is easy to write down:
for (eff_size = lim; eff_size > 1; eff_size--)
find maxpos, the location of the largest element in the effective
array: index 0 to eff_size - 1
swap elements of x at index maxpos and index eff_size - 1
The implementation of the selection sort algorithm in C,
together with a driver program is shown in
Figure 10.6.
Sample Session:
The driver prints the array, calls selection_sort() to sort the array, and prints the sorted array. The code for selection_sort() follows the algorithm exactly; it calls get_maxpos() to get the index of the largest element in an array of a specified size. Once maxpos is found, the element at that index is swapped with the element at index eff_size-1, using the temporary variable, tmp.
We may be concerned about the efficiency of our algorithm and its implementation as a program. The efficiency of an algorithm depends on the number of major computations involved in performing the algorithm. The efficiency of the program depends on that of the algorithm and the efficiency of the code implementing the algorithm. Notice we included the code for swapping array elements within the loop in selection_sort rather than calling a function to perform this operation. A function call requires added processing time in order to store argument values, transfer program control, and retrieve the returned value. When a function call is in a loop that may be executed many times, the extra processing time may become significant. Thus, if the array to be sorted is quite large, we can improve program efficiency by eliminating a function call to swap data elements. Similarly, we may include the code for get_maxpos() in selection_sort():
void selection_sort(int x[], int lim)
{ int i, eff_size, maxpos, tmp;
for (eff_size = lim; eff_size > 1; eff_size--) {
for (i = 0; i < eff_size; i++)
maxpos = x[i] > x[maxpos] ? i : maxpos;
tmp = x[maxpos];
x[maxpos] = x[eff_size - 1];
x[eff_size - 1] = tmp;
}
}