//File:  NumberList.java
import iostuff.*;
import java.io.*;
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;
  }
  
  

  //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);
  }
  
  
  // The next two methods implement a Shell sort
  
  private static void sortComb(int [] a, int g){ 

       // This method sorts the subset of the array a 
       // consisting of elements separated by the gap g 
         
              int i; 
              boolean inorder=false; 
              while (! inorder) { 
                    inorder=true; 
                    for (i = g; i < a.length; i += g) { 
                           if (a[i-g] > a[i] ) { 
                                  int temp; 

                                  // exchange the out-of-order elements 
                                  temp = a[i-g]; 
                                  a[i-g] = a[i]; 
                                  a[i] = temp; 
                                  inorder = false;
                           }
                    }
              }
       } 

       public static void ShellSort(int [] a ) { 

       // This method uses sortComb to progressively bring 
       // array a into order by sortsusing finer and finer combs 
       // ending with an ordinary bubble sort. 
         
              int gap = a.length/2; 
              while ( gap > 0 ) { 
                    sortComb(a, gap); 
                    gap /= 2;
              }
       }

       public static int readIn (String fileName, int [] list) {
        int count=0;
        try
        {
        //The FileReader converts byte stream to char stream
        FileReader fr = new FileReader (fileName);

        //The BufferedReader enables efficient buffering of stream
        BufferedReader inFile = new BufferedReader (fr);
        String line = inFile.readLine(); //readLine() is in 
                                         //BufferedReader class
            
        while (line != null)     //null is the pointer
                                 //that points nowhere -- 
                                 //when no more lines in 
                                 //file, line = null.
        {
        list [count] = Integer.parseInt (line);
        count++;
        line = inFile.readLine();
        }
            
                    inFile.close(); //not invoked if throws exception
        }
        catch (FileNotFoundException e)
        {
            System.out.println (
              "The file " + fileName + " was not found.");
        }
        catch (IOException e)
        {
        }
        
        return count;
    }



}