/* Bubblesort for strings - version2, char* array, space for
 * strings allocated via malloc */

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


void BubbleSort (char *a[], int n) {
  int i, j;
  char *temp;
  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 (strcmp(a[j],a[j+1]) > 0) {
	temp = a[j];
	a[j]=a[j+1];
	a[j+1]=temp;
      }
    }
  } 
}


int main(void) {
  double start, stop, t;
  char *a[40];
  int i;
  for (i=0; i <40; i++) {
    int j;
    /* set the string to several repetitions of a bizarrely chosen character */
    char c = ((i % 55) + 9)*2 + (i/20);
    c = 'a' + (c % 26);
    /* the length is 0 to 9 */
    int len = i % 10;
    a[i]= malloc(len+1); /* plus 1 for the terminating null */
    if (a[i] == NULL ) {
      perror("Error allocating string storage");
      exit(1);
    }
    for (j = 0; j < len; j++) a[i][j] = c;
    a[i][len] = '\0'; /* terminating null character */
  }
  printf("First 5 strings are %s, %s, %s, %s, %s, %s, %s, %s, %s, %s.\n", a[0],a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]); 
  start = clock();
  BubbleSort(a, 40);
  stop = clock();
  t = (stop-start)/CLOCKS_PER_SEC;
  printf("Time spent was %lf seconds.\n", t);
  printf("First 5 strings are %s, %s, %s, %s, %s, %s, %s, %s, %s, %s.\n", a[0],a[1], a[2], a[3], a[4], a[5], a[6], a[7], a[8], a[9]); 
  return EXIT_SUCCESS;
}
