import java.util.*;

class InsertionSort{
	
	// insertion sort for ArrayList
	public ArrayList insertSort(ArrayList source){
		
		int index = 1;
		
		while (index < source.size()){
			insertSorted((String)(source.get(index)), source, index);
			index = index + 1;
		}
		return source;
	}	
	
	// insert the given (City) object into the given list
	// assuming elements 0 through index - 1 are sorted
	// use comp for comparison
    public ArrayList insertSorted(String s, ArrayList source, int index){
    		int loc = index - 1;
    		while ((loc >= 0) &&
    			  // c is smaller that the next highest element	
    			  (s.compareTo(source.get(loc)) <= 0)){
    			// move element to the right
    			source.set(loc + 1, source.get(loc));
    			loc = loc - 1;
    		}
    		source.set(loc+1, s);
    		return source;
    }
    
    // test insertSorted
    public void testInsertSorted(){
    	
     	Examples e = new Examples();
     	
     	ArrayList alist = new ArrayList();
      	alist.add("Hello");
     	alist.add("Goodbye");
     	alist.add("Ciao");
     	alist.add("Servus");
     
     	ArrayList slist = new ArrayList();
     	slist.add("Ciao");
     	slist.add("Hello");
     	slist.add("Goodbye");
     	slist.add("Servus");
     	
   
     	// verifying the sorting
     	alist = insertSort(alist);
     	Iterator it2 = alist.iterator();
     	
     	while (it2.hasNext()){
     		System.out.println(it2.next());
     	}	
      }
      
      public static void main(String[] argv){
      	InsertionSort ss = new InsertionSort();
      	ss.testInsertSorted();
      }

}