public class SearchAndSort
{
	//precondition: values is a non-empty array of integers
	//postcondition: return the index of the target, or -1 if target is not in the array
	public static int linearSearch(int[] values, int target)
	{
		for(int x = 0; x < values.length; x++)
		{
			if (values[x] == target)
				return x;
		}
		return -1;
	}

	//overloaded for String arrays
	public static int linearSearch(String[] values, String target)
	{
		for(int x = 0; x < values.length; x++)
		{
			if(values[x].equals(target))
				return x;
		}
		return -1;
	}

	//precondition: values is already sorted
	//postcondition: return the index of the target, or -1 if target is not in the array
	public static int binarySearch(int[] values, int target)
	{
		int f = 0;
		int l = values.length -1;
		while(f<=l)
		{
			int m = (f+l)/2;
			if(values[m] == target)

				return m;
			else if(values[m] > target)
				l = m-1;
			else if(values[m] < target)
				f = m+1;



		}
		return -1;
	}

	//String version
	public static int binarySearch(String[] values, String target)
	{
		int f = 0;
		int l = values.length -1;

		while(f<=l)
		{
			int m = (f+l)/2;
			if(values[m].compareTo(target) == 0)
				return m;
			else if(values[m].compareTo(target) > 0)
				l = m-1;
			else if(values[m].compareTo(target) < 0)
				f = m+1;
		}
		return -1;
	}

	//precondition: values is a non-empty array of integers
	//postcondition: returns a new array that is the sorted version of the input parameter
	public static int[] bubbleSort(int[] values)
	{
		for(int spot = 0; spot < values.length; spot++)
		{
			for(int x = 0; x < values.length-spot-1; x++)
			{
				int temp = 0;
				if(values[x] > values[x+1])
				{
					temp = values[x];
					values[x] = values[x+1];
					values[x+1] = temp;
				}
			}
		}
		return values;
	}

	//String version
	public static String[] bubbleSort(String[] values)
	{
		for(int spot = 0; spot < values.length; spot++)
		{
			for(int x = 0; x < values.length-spot-1; x++)
			{
				String temp = "";
				if(values[x].compareTo(values[x+1]) > 0)
				{
					temp = values[x];
					values[x] = values[x+1];
					values[x+1] = temp;
				}
			}
		}
		return values;
	}

	//precondition: values is a non-empty array of integers
	//postcondition: returns a new array that is the sorted version of the input parameter
	public static int[] selectionSort(int[] values)
	{
		for(int i = 0; i< values.length -1; i++)
		{
			int spot = i;
			for(int x = i+ 1; x< values.length; x++)
			{
				if(values[x] < values[spot])
					spot = x;
			}

			int temp = values[spot];
			values[spot] = values[i];
			values[i] = temp;
		}
        return values;
	}

	//String version
	public static String[] selectionSort(String[] values)
	{
		for(int i = 0; i< values.length -1; i++)
		{
			int spot = i;
			for(int x = i+ 1; x< values.length; x++)
			{
				if(values[x].compareTo(values[spot])<0)
					spot = x;
			}

			String temp = values[spot];
			values[spot] = values[i];
			values[i] = temp;
		}
        return values;
	}

	//precondition: values is a non-empty array of integers
	//postcondition: returns a new array that is the sorted version of the input parameter
	public static int[] insertionSort(int[] values)
	{
		   for (int i = 1; i < values.length; i++)
		   {
		       int key = values[i];
		       int j = i-1;

		       while (j >= 0 && values[j] > key)
		       {
		           values[j+1] = values[j];
		           j = j-1;
		       }
		       values[j+1] = key;
		   }
		 return values;
	}

	//String version
	public static String[] insertionSort(String[] values)
	{
		for (int i = 1; i < values.length; i++)
		   {
		       String key = values[i];
		       int j = i-1;

		       while (j >= 0 && values[j].compareTo(key) > 0)
		       {
		           values[j+1] = values[j];
		           j = j-1;
		       }
		       values[j+1] = key;
		   }
		 return values;
	}

	//Janssensort method
	public static int[] JanssenSort(int[] values)
	{
		//loop through the array to mark the starting point
		for(int spot = 0; spot < values.length; spot++)
		{
			//loop through each value of the array
			for(int x = 0; x < values.length-spot-1; x++)
			{
				//swap the values if one is less than the other
				int temp = 0;
				if(values[x] > values[x+1])
				{
					temp = values[x];
					values[x] = values[x+1];
					values[x+1] = temp;
				}
			}
		}
		//return the sorted array
		return values;
	}

	public static void main(String[] args)
	{
		int[] array = new int[]{12, 3, 25, -4, -13, 7, 5, 32, 19, -3, 0};
		JanssenSort(array);
		for(int x = 0; x < array.length; x++)
		{
			System.out.println(array[x]);
		}
	}
}