//File:	NumberList.java
import iostuff.*;
public class NumberList
{
	public static int [] inputList ()
	{
		System.out.print ("How many items in your list? ");
		int n=Keyboard.readInt();
		System.out.println(n);
		
		//allocate n memory locations for array x
		int [] x = new int [n];
		
		//fill the array x with values from the user
		for (int k=0; k<n; k++)
		{
			System.out.print ("Next number please: ");
			x [k] = Keyboard.readInt();
			System.out.println(x[k]);
		}
		System.out.println();
		
		return x;	//return the filled array x
	}
	
	//The following method outputs to the screen an array of integers
	public static void display (int [] list)
	{
		for (int k=0; k<list.length; k++)
		{
			System.out.println (list[k]);
		}
		System.out.println();
	}
	
	//The following method outputs to the screen a list of n integers
	public static void display (int [] list, int n)
	{
		for (int k=0; k<n; k++)
		{
			System.out.println (list[k]);
		}
		System.out.println();
	}	
	


			//SORTING ALGORITHMS

	//NOTE:	In the following, length is an instance variable
	//	associated with an array object.  It carries the
	//	the size of the array, NOT necessarily the number
	//	of items input to the array.
		
	
	//The insertion sort resembles the process of placing cards
	//into a hand one at a time in order
	static void insertionSort (int [] list)
	{
		for (int i=1; i<list.length; i++)
		{
			//list[0], list[1], ..., list[i-1] are in order
			int currentItem = list[i];
			int j = i-1;
			while (j>=0 && list[j]>currentItem)	//stops when finds a smaller item
			{
				//looking for place to put list[i]
				//so moving elements to the right
				//to make room
				list[j+1] = list[j];	//jth item --> j+1 slot
				j--;
			}
			//list[i] goes into the j+1 slot immediately to right of smaller item
			list[j+1] = currentItem;
		}
	}

	static void swap (int [] list, int i, int j)
	{
		int temp = list[i];
		list[i] = list[j];
		list[j] = temp;
	}
		
	
	
	static void selectionSort (int [] list)
	{
		for (int k=0; k<list.length-1; k++)
		{
			int min = smallestIndex (list, k);
			swap (list, k, min);	//swaps list[k] with list[min]
		}
	}
	

	//The following method finds the INDEX of the smallest item from item n to the end
	public static int smallestIndex (int [] list, int n)
	{
		int smallIndex = n;
		for (int k=n+1; k<list.length; k++)
		{
			if (list[k] < list[smallIndex])
			{
				smallIndex = k;
			}
		}
		return smallIndex;
	}

	//The following method finds the smallest item in a list of integers
	public static int smallest (int [] list)
	{
		int smallestSoFar;
		
		//The following focuses on smallestSoFar,
		//a variable that is compared with each item
		//in the list in succession.  As smaller items
		//are encountered, they are assigned to the variable
		//smallestSoFar.
		smallestSoFar = list[0];
		for (int k=1; k<list.length; k++)
		{
			if (list[k] < smallestSoFar)
			{
				smallestSoFar = list[k];
			}
		}
		return smallestSoFar;
	}
	
	
	//HW #5
	public static void insertInOrder (int [] a, int p, int n)
	{
		//loop until find place for p
		//suppose p goes in slot k
		//move n-1 to n, n-2 to n-2, ...., k to k+1 (loop)
		//a[k] = p;
	}
	

	//The following two methods average an array of numbers
	
	//The following averages int's
	public static int average (int [] a)
	{
		int sum=0;
		for (int k=0; k<a.length; k++)
		{
			sum = sum + a [k];
		}
		return sum/a.length;
	}
	
	//the following averages double's
	public static double average (double [] a)
	{
		double sum=0;
		for (int k=0; k<a.length; k++)
		{
			sum = sum + a [k];
		}
		return sum/a.length;
	}
	
	
	//The following calculates the standard deviation of an array of int's
	public static int sd (int [] a, int average)
	{
		int sum=0;
		for (int k=0; k<a.length; k++)
		{
			sum = sum + (a[k]-average) * (a[k]-average);
		}
		return (int) Math.sqrt(sum/a.length);
	}	
}