import java.util.Arrays;
// This program demonstrates a few of the search and sort algorithms
public class ArrayDemo
{
  // Linear search
  public static int linearSearch( int[] a, int key ){
    for( int i=0; i<a.length; i++ )
      if ( a[i] == key )
        return i;
    return -1;
  }

  // Binary search (assume sorted array)
  public static int binarySearch( int[] a, int key ){
    return binarySearch(a, key, 0, a.length-1);
  }
  public static int binarySearch( int[] a,
		int key, int from, int to ){
    if(to < from)
      return -1;
    int middle = (from + to + 1)/2;
    if(key == a[middle])
      return middle;
    else if( key < a[middle] )
      return binarySearch( a, key, from, middle-1 );
    else
      return binarySearch( a, key, middle+1, to );
  }

  // Selection sort
  public static void selectionSort( int[] a ){
    for( int i=0; i < a.length-1; i++ ) {
			int smallest = i;
      for( int j=i+1; j < a.length; j++ )
        if( a[j] < a[smallest] ) smallest = j;
			swap(a,i,smallest);
    }
  }

  // Insertion sort
  public static void insertionSort( int[] a ){
    for( int i=0; i < a.length; i++ ) {
      int k=i;
      for(int j=i-1; j>=0; j--)
        if( a[j] > a[k] ){ swap(a,j,k); k=j; }
    } // end of outer for-loop
  }

  public static void printArray(int[] a){
    System.out.print("The array is: ");
    for(int n:a)
      System.out.print(n+" ");
    System.out.println();
  }

  private static void swap( int[] a, int first, int second ){
    int temp = a[first];
    a[first] = a[second];
    a[second] = temp;
  }

  public static void main( String args[] ){

    int[] array = {2,3,1,8,5,1,13,11};
    int key = 3;
    int pos;

    printArray(array);

    // Searching using linear search
    pos = linearSearch( array, key );
    System.out.println("Linear search finds " + key + " at position " + pos);

    // Sorting using selection sort or insertion sort
    //insertionSort(array);
    selectionSort(array);
    System.out.println("Sorting the array...");
    printArray(array);

    // Searching using binary search
    pos = binarySearch( array, key );
    System.out.println("Binary search finds " + key + " at position " + pos);

  }
}