/* Linear search and Binary search */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void swap(int *a, int*b) {
  int temp;
  temp = *a;
  *a = *b;
  *b = temp;
}

void BubbleSort (int a[], int n) {
  int i, j;
  for (i = n - 1; i >= 1; --i) {
      /*  Invariant:  The values in locations to the right of a[i]
       *  are in their correct resting places:  that is, they are 
       *  the n - i - 1 largest elements, and they are correctly 
       *  ordered among themselves.
       */
    for (j = 0; j < i; ++j) {
      if (a[j] > a[j+1])
        swap(&a[j], &a[j+1]);
    }
  } 
}


int main(void) {
  double start, stop, t;
  int a[40000];
  int i;
  for (i=0; i <40000; i++) {
    a[i]= ((i % 55) + 9)*2 + (i/900);
  }
  start = clock();
  BubbleSort(a, 40000);
  stop = clock();
  t = (stop-start)/CLOCKS_PER_SEC;
  printf("Time spent was %lf seconds.\n", t);
  return EXIT_SUCCESS;
}
