// bubsort2.C
#include "bubsort2.h"
#include "swap.h"

//  Algorithm: an improved bubble sort

void Sort( int vec[], int vSize )
{
  int bot;	    // False bot
  int lastSwapIndx; // last swapped
  int i;
  
  bot = vSize - 1;
  // INV: 0 <= bot < vSize
  // && vec[0..size-1] contains the
  // same values as vec[0..size-1]<entry>
  // && vec[bot..size-1] is sorted
  while (bot > 0) {
    lastSwapIndx = 0;
    // INV: 0 <= lastSwapIndx <= i <= bot
    // && no pair in vec[lastSwapIndx..i]
    // is out of order
    for (i = 0; i < bot; i++)
      if (vec[i] > vec[i+1]) {
	swap(vec[i], vec[i+1]);
	lastSwapIndx = i;
      }
    // ASSERT: i == bot && 
    // vec[lastSwapIndx..size-1]
    // is sorted
    bot = lastSwapIndx;
  }
}