public class Problem2 {
    public static void main(String[] args) {

	// Create an array of $SIZE$ Data objects with Strings of random length
	// between 1 and 25:
	final int SIZE=5, LMIN=1, LMAX=25;
	Data[] d = new Data[SIZE];
	for (int i = 0 ; i < SIZE ; i++)
	    d[i] = new Data( (int) (Math.random()*(LMAX-LMIN+1)+LMIN) );
	print("Unsorted:",d);

	// Select sort the array $d$:
	Data[] dss = d;
	sortData_ss(dss);
	print("Select Sort:",dss);

	// Insert sort the array $d$:
	Data[] dis = d;
	sortData_is(dis);
	print("Insert Sort:",dis);
    }

    // print an array:
    private static void print(String s, Data[] d) {
	System.out.println(s);
	for (int i = 0; i < d.length; i++) 
	    System.out.println(d[i]);
    } 

    // Use select sort (descending order):
    private static void sortData_ss(Data[] d) {
	int index, minIndex, scanIndex;
	Data tmp;
	
	// look at each element, start L->R
	for(index=0; index<d.length-1; index++) {
	    minIndex = index;
            
            // inner loop finds smallest value
            for(scanIndex = index+1; scanIndex < d.length; scanIndex++)
                if (d[scanIndex].getMaxCount() > d[minIndex].getMaxCount())
                    minIndex = scanIndex;
	    
            // swap values
            tmp = d[minIndex];
            d[minIndex] = d[index];
            d[index] = tmp;
	}
    } // Method sortData

    // Use insert sort (descending order):
    private static void sortData_is(Data[] d) {
	// First element d[0] is sorted
	
        // Scan through remaining elements
	for (int i=1; i<d.length; i++) {
            
            // Index $i$ gives current element $key$ to insert 
            // in sorted portion:
	    Data key=d[i]; // element to insert
	    int pos=i; // position of $key$ so far
            
            // Test $key$ with other elements.
            // Each time, move the tested element to the right
            // (causes a shift of sorted portion from left to right):
	    while(pos>0 && d[pos-1].getMaxCount()<key.getMaxCount()) { 
		d[pos]=d[pos-1];
		pos--;
	    }
            // Insert $key$:
	    d[pos]=key;
	}
	
    } // Method sortData_is
    
} // Class Problem2

class Data {
    private String s;     // random String set by setString
    private int max;      // count of most repeated character in $s$
    public Data(int n) { setString(n);  setMaxCount(); } // constructor
    public String getString() { return s; };
    public int getMaxCount() { return max; };
    public String toString() { return "String: "+s+"; Max count: "+max; } 
   
    // generate a String of n random characters between 'a' and 'z':
    public void setString(int n) {
        char[] tmp = new char[n];
        for(int i=0; i<n; i++) 
            tmp[i] = (char) (Math.random()*('z'-'a'+1)+'a');
        s = new String(tmp);
    }

    // find count of most repeated char in String

    public void setMaxCount() {
        max = 1; // max so far
        int i,j;
        for (i=0; i< s.length(); i++) {
            char tmpchar = s.charAt(i);
            int tmpsum = 1;
            for (j = i+1; j < s.length(); j++ )
                if (tmpchar == s.charAt(j))
                    tmpsum++;
            max = Math.max(tmpsum,max);
        }
    } // method setMaxCount    
    
} // Class Data