|
|
 |
|
|
|
|
Sorting Arranging the components of a list into order (for instance, words into alphabetical order or numbers into ascending or descending order). |
|
|
|
|
|
|
|
|
If you were given a sheet of paper with a column of twenty numbers on it and were asked to write the numbers in ascending order, you would probably: |
|
|
|
|
|
|
|
|
1. Make a pass through the list, looking for the smallest number. |
|
|
|
|
|
|
|
|
2. Write it on the paper in a second column. |
|
|
|
|
|
|
|
|
3. Cross the number off the original list. |
|
|
|
|
|
|
|
|
4. Repeat the process, always looking for the smallest number remaining in the original list. |
|
|
|
|
|
|
|
|
5. Stop when all the numbers have been crossed off. |
|
|
|
|
|
|
|
|
We can implement this algorithm directly in C++, but we need two arrays-one for the original list and a second for the ordered list. If the list is large, we might not have enough memory for two copies of it. Also, it is difficult to ''cross off" an array component. We would have to simulate this with some dummy value like INT_MAX. We would set the value of the crossed-off variable to something that would not interfere with the processing of the rest of the components. A slight variation of this hand-done algorithm allows us to sort the components in place. This means that we do not have to use a second array; we can put a value into its proper place in the original list by having it swap places with the component that is there. |
|
|
|
|
|
|
|
|
If our array is called list and contains length values, we can state the algorithm as follows: |
|
|
|
|
|
|
|
|
FOR count going from 0 through length-2
Find minimum value in list[count.. length-1]
Swap minimum value with list[count] |
|
|
|
|
|
|
|
|
Figure 12-3 illustrates how this algorithm works. |
|
|
|
|
|
|
|
|
Observe that we make length-1 passes through the list, with count running from 0 through length-2. The loop does not need to be executed when count equals length-1 because the last value, list[length-1], is in its proper place after the preceding components have been sorted. |
|
|
|
|
|
|
|
|
This sort, known as straight selection, belongs to a class of sorts called selection sorts. There are many types of sorting algorithms. Selection sorts are characterized by swapping one component into its proper place on each pass through the list. Swapping the contents of two variables-two components in an array-requires a temporary variable so that no values are lost (see Figure 12-4). |
|
|
|
|
|