import java.util.Random;
import java.util.Date;
 
/**
 * Sorts arrays using the bubble sort algorithm
 * 
 * @author David Nickles, Zach Tomaszewski
 * @version Mar 15, 2005
 */
public class BubbleSort {
 
  static Comparable[] c;
 
  /**
   * Sorts the given array using the Bubble Sort algorithm.
   * @param theArray  the array to sort
   * @param n  number of elements in the array
   */
  public static void sort( Comparable[] theArray, int n ) {
    boolean sorted = false;  //turn to false if we make a swap
    while (!sorted) {
      sorted = true;
      for (int i = 0; i < n - 1; i++) {
        if (theArray[i].compareTo(theArray[i + 1]) > 0 ){
          Comparable temp = theArray[i + 1];
          theArray[i + 1] = theArray[i];
          theArray[i] = temp;
          sorted = false;
        }
      }
      n--; //go through 1 fewer elements each time, since end now sorted
    } 
  }  // end sort
 
  public static void main ( String[] args ) {
 
    Random generator = new Random( );
    Date clock;
    int avg_time = 0;
    int times_to_repeat = 5;
    int max_size = 100000;
 
      for( int size = 10; size <= max_size; size *= 10 ) {
        avg_time = 0;
        c = new Comparable[ size ];
        System.out.println( "\n*** Beginning test of array of size: " + size );
            for(int j = 0; j < times_to_repeat; j++) {
            System.out.println( "Beginning trial " + (j+1) );
 
        for( int i = 0; i < size; i++ ) {
          c[i] = new Integer( generator.nextInt( size ));
          //System.out.print( c[i] + "  " );
        }
        //TEST: System.out.println(java.util.Arrays.asList(c));
        System.out.println( "Sorting..." );
        clock = new Date();
        long l1 = clock.getTime();
        sort( c, size );
 
        clock = new Date();
        long l2 = clock.getTime();
        long difference = l2 - l1;
        System.out.println( "Bubble sort for " + size + " items, "
                                             + difference + " milliseconds.");
        //TEST: System.out.println(java.util.Arrays.asList(c));
        avg_time += difference;
            } //ends for
        avg_time /= times_to_repeat;
        System.out.println( "Average bubble sort time for " + size + " items, "
                                               + avg_time + " milliseconds.");
    } //ends for
 
  } //ends main
 
} //ends class