bubblesort.cpp

Data Abstraction & Problem Solving with C++源码

// Must define DataType before compilation

typedef type-of-array-item DataType;

void bubbleSort(DataType theArray[], int n)
// ---------------------------------------------------
// Sorts the items in an array into ascending order.
// Precondition: theArray is an array of n items.
// Postcondition: theArray is sorted into ascending
// order; n is unchanged.
// Calls: swap.
// ---------------------------------------------------
{
   bool sorted = false;  // false when swaps occur

   for (int pass = 1; (pass < n) && !sorted; ++pass)
   {  // Invariant: theArray[n+1-pass..n-1] is sorted
      //            and > theArray[0..n-pass]
      sorted = true;  // assume sorted
      for (int index = 0; index < n-pass; ++index)
      {  // Invariant: theArray[0..index-1] <= 
         // theArray[index]
         int nextIndex = index + 1;
         if (theArray[index] > theArray[nextIndex])
         {  // exchange items
            swap(theArray[index], theArray[nextIndex]);
            sorted = false;  // signal exchange
         }  // end if
      }  // end for

      // Assertion: theArray[0..n-pass-1] < 
      // theArray[n-pass]
   }  // end for
}  // end bubbleSort

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