144 Chapter 8 Working with Functions
means rearranging the values in the array so that the elements progressively increase in
value from the smallest to the largest. By the end of such a sort, the minimum value is
contained in the first location of the array, whereas the maximum value is found in the
last location of the array, with values that progressively increase in between.
If you want to sort an array of nelements into ascending order, you can do so by per-
forming a successive comparison of each of the elements of the array.You can begin by
comparing the first element in the array against the second. If the first element is greater
in value than the second, you simply “swap” the two values in the array; that is, exchange
the values contained in these two locations.
Next, compare the first element in the array (which you now know is less than the
second) against the third element in the array. Once again, if the first value is greater
than the third, you exchange these two values. Otherwise, you leave them alone. Now,
you have the smallest of the first three elements contained in the first location of the
array.
If you repeat the previous process for the remaining elements in the array—compar-
ing the first element against each successive element and exchanging their values if the
former is larger than the latter—the smallest value of the entire array is contained in the
first location of the array by the end of the process.
If you now did the same thing with the second element of the array, that is, compare
it against the third element, then against the fourth, and so on; and if you exchange any
values that are out of order, you end up with the next smallest value contained in the
second location of the array when the process is complete.
It should now be clear how you can go about sorting the array by performing these
successive comparisons and exchanges as needed.The process stops after you have com-
pared the next-to-last element of the array against the last and have interchanged their
values if required. At that point, the entire array has been sorted into ascending order.
The following algorithm gives a more concise description of the preceding sorting
process.This algorithm assumes that you are sorting an array aof nelements.
Simple Exchange Sort Algorithm
Step 1: Set ito 0.
Step 2: Set jto i+ 1.
Step 3: If a[i]>a[j], exchange their values.
Step 4: Set j to j+ 1. If j< n, go to step 3.
Step 5: Set ito i+ 1. If i <n– 1, go to step 2.
Step 6: ais now sorted in ascending order.
Program 8.12 implements the preceding algorithm in a function called sort, which
takes two arguments: the array to be sorted and the number of elements in the array.