selectionsort.cpp

Data Abstraction & Problem Solving with C++源码

// Must define DataType before compilation

typedef type-of-array-item DataType;

void selectionSort(DataType theArray[], int n)
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: The array theArray is sorted into 
// ascending order; n is unchanged.
// Calls: indexOfLargest, swap.
// ---------------------------------------------------
{
   // last = index of the last item in the subarray of 
   //        items yet to be sorted,
   // largest = index of the largest item found

   for (int last = n-1; last >= 1; --last)
   {  // Invariant: theArray[last+1..n-1] is sorted and 
      // > theArray[0..last]

      // select largest item in theArray[0..last]
      int largest = indexOfLargest(theArray, last+1);

      // swap largest item theArray[largest] with 
      // theArray[last]
      swap(theArray[largest], theArray[last]);
   }  // end for
}  // end selectionSort

int indexOfLargest(const DataType theArray[], int size)
// ---------------------------------------------------
// Finds the largest item in an array.
// Precondition: theArray is an array of size items, 
// size >= 1.
// Postcondition: Returns the index of the largest 
// item in the array. The arguments are unchanged.
// ---------------------------------------------------
{
   int indexSoFar = 0;  // index of largest item 
                        // found so far
   for (int currentIndex = 1; currentIndex < size; 
                              ++currentIndex)
   {  // Invariant: theArray[indexSoFar] >= 
      //            theArray[0..currentIndex-1]
     if (theArray[currentIndex] > theArray[indexSoFar])
         indexSoFar = currentIndex;
   }  // end for

   return indexSoFar;  // index of largest item
}  // end indexOfLargest

void swap(DataType& x, DataType& y)
// ---------------------------------------------------
// Swaps two items.
// Precondition: x and y are the items to be swapped.
// Postcondition: Contents of actual locations that x 
// and y represent are swapped.
// ---------------------------------------------------
{
   DataType temp = x;
   x = y;
   y = temp;
}  // end swap