/*
 * Generates n random strings and then sorts them using bubble sort.
 * Compile with command: javac bsort.java
 * Execute with command: java bsort
 */
import java.util.Date;
import java.util.Random;
import java.util.List;
import java.util.ArrayList;

public class bsort {
	static int num = 1000;  // number of strings to sort
	static int ssize = 20;  // size of each string.
	static char[] chars = new char[] {
	  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
	  'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
	  'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
	  'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
	  'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'
	};

	static void bsort(List array){
	  int n = array.size();
	  for (int i = n - 1; i > 0; i--){
		for (int j = 0; j < i; j++){
		  if (((String)array.get(j)).compareTo(((String)array.get(j+1))) < 0){
			Object t = array.get(j);
			array.set(j, array.get(j+1));
			array.set(j+1, t);
		  }
		}
	  }
	}

	static void printa(List array){
	  for (int i = 0; i < array.size(); i++){
		System.out.println("[" + i + "] " + array.get(i));
	  }
	}

	static void populate(List array, int num){
	  Random ran = new java.util.Random();
	  for (int i = 0; i < num; i++){
		String s = "";
		for (int j = 0; j < ssize; j++){
		  int r = ran.nextInt(chars.length);
		  s += chars[r];
		}
		array.add(s);
	  }
	}

	public static void main(String[] args){
		List array = new ArrayList(); // Do not specify the size on purpose

		System.out.println("Populating the array with " + num + " Strings, each of " + ssize + " characters ...");
		long st = (new Date()).getTime();
		populate(array, num);
		long et = (new Date()).getTime();
		System.out.println(" ... done. Elapsed time: " + (et - st) + " millis.");

		//System.out.println("Original Array::"); printa(array);

		System.out.println("Sorting the array ...");
		st = (new Date()).getTime();
		bsort(array);
		//array.sort();
		et = (new Date()).getTime();
		System.out.println(" ... done. Elapsed time: " + (et - st) + " millis.");

		//System.out.println("Sorted Array::"); printa(array);
	}
}