 |
The exchange sort is very similar to
its cousin, the bubble sort, in that it compares elements of the array and swaps those that are not in their proper positions.
(Some people refer to the "exchange sort" as a "bubble sort".) The difference between the two algorithms is the manner in which they compare the elements.
The exchange sort compares the first element with each following element of the array, making any necessary swaps.
|
|
It then takes the second element and compares it with each following element
of the array making necessary swaps, and so on until the array is ordered.
Let's examine our same table of elements again using an exchange sort for descending order.
Remember, a "pass" is defined as one full trip through the array
comparing and if necessary, swapping elements. |
| Array at beginning: |
84 |
69 |
76 |
86 |
94 |
91 |
| After Pass #1: |
94 |
69 |
76 |
84 |
86 |
91 |
| After Pass #2: |
94 |
91 |
69 |
76 |
84 |
86 |
| After Pass #3: |
94 |
91 |
86 |
69 |
76 |
84 |
| After Pass #4: |
94 |
91 |
86 |
84 |
69 |
76 |
| After Pass #5
(done): |
94 |
91 |
86 |
84 |
76 |
69 |
The exchange sort, in some situations, is slightly more efficient than the
bubble sort. It is not necessary for the exchange sort to make that
final complete pass needed by the bubble sort to determine that it is
finished.
//Exchange Sort Function for Descending Order
void exchange_sort(apvector <int> &array)
{
int i, j;
int temp;
// holding variable
int arrayLength = array.length( );
for (i=0; i< (arrayLength -1); i++)
// to represent element to be compared
{
for(j = (i+1); j < arrayLength; j++)
// to represent the rest of the elements
{
if (array[i] < array[j])
{
temp= array[i];
// swap
array[i] = array[j];
array[j] = temp;
}
}
}
return;
}
|
