/* bubblesort.c: bubblesort program */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 100000

void swap(int a[], int i, int j);
void bubbleSort(int a[]);
void printArray(int a[]);

// swap: interchange inside array
void swap(int a[], int i, int j) {
   int t = a[i];
   a[i] = a[j];
   a[j] = t;
}

// bubbleSort: very short code, but ineffient
void bubbleSort(int a[]) {
   int sorted;
   int i;
   for (;;) {
      sorted = 1;
      for (i = 0; i < SIZE - 1; i++)
         if (a[i] > a[i+1]) {
            sorted = 0;
            swap(a, i, i + 1);
         }
      if (sorted) break;
   }
}

void printArray(int a[]) {
   int i;
   for (i = 0; i < SIZE; i++) {
      if (i%4 == 0) printf("\n");
         printf("%i\t", a[i]);
   }
   printf("\n");
}

int main() {
   int i;
   int r[SIZE];
   int starttime = time(NULL); /* clock time */
   printf("Bubblesort, size = %i", SIZE);
   srand((long)starttime);


   for (i = 0; i < SIZE; i++)
      r[i] = (int)((rand()/(double)RAND_MAX)*SIZE*10 + 1);
   
   bubbleSort(r);
   printf("Elapsed time: %ld seconds\n",
      time(NULL) - starttime);
   /* printArray(r); */
}