class searching
{
	static String[] list;
		
	public static void sorting()
	{
		boolean swaped = true;
		
		while (swaped)
		{
			swaped = false;
			for (int pos = 0; pos < list.length - 1; pos++)
			{
				if(list[pos].compareTo(list[pos+1]) > 0)
				{
					String tmp = list[pos];
					list[pos]= list[pos+1];
					list[pos+1] = tmp;
					swaped = true;
				}		
			}
		}
	}
	
	public static void quick_sorting(int l,int r)
	{
		int y = r;
		int x = l;
		int middle = (x + y)/2;
		
		while (list[x].compareTo(list[middle]) < 0)
			x++;
			
		while (list[y].compareTo(list[middle]) > 0)
			y--;
		
		if (x <= y)
		{
			String tmp= list[y];
			list[y]= list[x];
			list[x]= tmp;	
		}
		
		if (l < y) quick_sorting(y, l);
		
		if (x < r) quick_sorting(y, r);
		/* a b d c e f */
		
	}
	
	public static int binary_search(String search_string)
	{	
		int pos = 0;
		int max = list.length - 1;
		int min = 0; 
		int comparison = 1;
		boolean found_end = false;
		
		while((comparison != 0))
		{
			pos = (max + min) / 2;
			comparison = search_string.compareTo(list[pos]);
			
			if (comparison > 0)
			{
				min = pos + 1;	
			}
			else if (comparison < 0)
			{
				max = pos - 1;	
			}
		}
		
		while(comparison == 0)
		{
			pos = (max + min) / 2;
			comparison = search_string.compareTo(list[pos]);
				
			min = pos- 1;
		}
		
		return pos;
		
	}
	
	
	public static void main(String[] args)
	{
 		list = new String[12]; 
		list[0] = "Richard";	
		list[1] = "Thomas";
		list[2] = "Peter";
		list[3] = "John";
		list[4] = "Mat";
		list[5] = "Thomas";
		list[6] = "Richard";
		list[7] = "Thomas";
		list[8] = "John";
		list[9] = "John";
		list[10]= "John";
		list[11]= "John";
		/*list[0] = "f";
		list[1] = "e";
		list[2] = "d";
		list[3] = "c";
		list[4] = "b";
		list[5] = "a";*/
		
		/*quick_sorting(0, list.length - 1);*/
		sorting();
		
	 	int position = binary_search("John");
		
		for (int pos = 0; pos < list.length; pos++)
		{
			System.out.println(list[pos]);	
		}
		
		System.out.println(position);
		
	}
	
}