// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

// Bubble Sort implementation and timing test driver

#include <iostream>
using namespace std;

#include "book.h"

// Include comparator functions
#include "compare.h"

// Bubble sort implementation
template <class Elem, class Comp>
void bubsort(Elem A[], int n) { // Bubble Sort
  for (int i=0; i<n-1; i++)     // Bubble up i'th record
    for (int j=n-1; j>i; j--)
      if (Comp::lt(A[j], A[j-1]))
        swap(A, j, j-1);
}

template <class Elem, class Comp>
void sort(Elem* array, int n) {
  bubsort<Elem, Comp>(array, n);
}

#include "sortmain.cpp"