**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:

The implementation of the selection sort algorithm in C, together with a driver program is shown in Figure 10.6.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

Sample Session:

- Original array:
- 63 75 90 12 27
- Sorted array:
- 12 27 63 75 90

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; } }

`
`

Sat Sep 3 06:58:41 HST 1994