/*Example in sorting:
- Linear sort: Compare the 1st number with the rest of the elements in the array (call it Num[]).
		If the number is largest, then move it to the end of the array. Otherwise swap it with
		the element that is less than or equal to the value of that number.
		Continue the process until all elements of the array are in sorting order.

- Insertion sort: Compare the elements of an array (call it Num[]), starting from the 1st element.
		As soon as the current element of the array is LESS than the previous element, then move
		the current element to the proper position.
		Continue the process until all elements are in sorting order.

- Selection sort: Algorithm is to find the smallest number in the array (call it NUM[]),
		then swap that number with the first element of the array Num[0].
		Next the algorithm finds the 2nd smallest number and swap it with the 2nd element
		of the array Num (Num[1]).
		Next the algorithm finds the 3rd smallest number and swap it with the 3rd element
		of the array Num (Num[2]), and so on.. until all elements of the array are in sorting
		order.

- Merge Sort: Merge sort is based on the idea of merging two sorted lists into one longer sorted
		list. This is easy to do simply by comparing the items at the head of each list and moving
		the smaller of those two items into the new list. (You need the extra array for the new
		list; there is no easy trick for avoiding this requirement, as there was for insertion
		sort.)
		Now, imagine starting with a large unsorted list of items. Pair off the items and sort
		each pair into increasing order. Each pair can be considered to be a sorted list of length
		two. The lists of length two can then be paired up, and each pair of lists can be merged
		into a sorted list of length four. Then lists of length four can be merged into lists of
		length eight, the lists of length eight into lists of length sixteen, and so on. At each
		stage, the length of the sorted lists doubles. Soon enough, all the items will be in one
		long, sorted list. (This requires just a little bit of fudging if the number of items is
		not a power of two, since in that case when you pair off the lists, you might have an extra
		list left over.)

- Quick sort: Probaly the fastest sorting algorithm known so far.
		The basic idea is as follows:
		- pick one element in the array, which will be the pivot.
		- make one pass through the array, called a partition step, re-arranging the entries
		so that:
			- the pivot is in its proper place.
			- entries smaller than the pivot are to the left of the pivot.
			- entries larger than the pivot are to its right.
			- recursively apply quicksort to the part of the array that is to the left of
			the pivot, and to the part on its right.

- Binary Search: search a sorted array for a specific value.
*/

public class SortNSearch{
	private int[] List = new int[11];
	private int[] List2 = new int[11];

public SortNSearch(){} //default constructor.

public SortNSearch(int[] arr){
	List = arr;
	}

/********************************************************/
/*					Linear Sort							*/
//////////////////////////////////////////////////////////
//The linear sort is very slow, but it's conceptually the simplest of the sorting
//algorithms and for that reason is a good beginning for our exploration of sorting
//techniques.
//  - The following is a linearSort method to sort either ascending or descending,
//depends on the boolean value passed into the method.
//  - If the boolean is false, then sort ascendingly, else sort descendingly.

public void linearSort(int[] MyArray, boolean tF){
 if(tF == false){
   for (int i = 1; i < MyArray.length; i++)
   {
     for (int j = 0; j < MyArray.length - 1; j++)
	 if (MyArray[j] > MyArray[j + 1])
	 {
	   int temp = MyArray[j];
	   MyArray[j] = MyArray[j + 1];   //Swap elements of the array.
	   MyArray[j + 1] = temp;
	 }
   }
  }else{
	  for (int i = 1; i < MyArray.length; i++)
	     {
	       for (int j = 0; j < MyArray.length - 1; j++)
	  	 if (MyArray[j] < MyArray[j + 1])
	  	 {
	  	   int temp = MyArray[j];
	  	   MyArray[j] = MyArray[j + 1];   //Swap elements of the array.
	  	   MyArray[j + 1] = temp;
	  	 }
   }
  }
}
/**************END of linearSort() method*****************************/


/********************************************************/
/*					Insertion Sort						*/
//////////////////////////////////////////////////////////
/* In most cases the insertion sort executes in O(N2) time, but it's about twice
as fast as the bubble sort and somewhat faster than the selection sort in normal
situations. It's also not too complex, although it's slightly more involved than
the bubble and selection sorts. It's often used as the final stage of more
sophisticated sorts, such as quicksort.*/

public void insertionSort(int[] A){
	  int i, j, temp;

  System.out.println("Insertion Sort in action:");
  for (i = 1; i < A.length; i++) {
	 if (A[i] > A[i-1]) continue;
	  temp = A[i];
	     j = i-1;

	 while ((j>=0)&&(A[j]>temp)) {
	    A[j+1] = A[j];
	    j--;
	 }
	  A[j+1]=temp;

   //If WANT to see the action of the SORT, then UNcomment the next for-loop.
   //  for(int k = 0; k < A.length; k++){ // inner loop
   //     System.out.print(A[k] + "   ");
   //  }  //end of inner-for
   //  System.out.println();
	}
}
/**************END of insertionSort() method*****************************/


/********************************************************/
/*					Selection Sort						*/
//////////////////////////////////////////////////////////
/*The selection sort improves on the bubble sort by reducing the number of swaps
necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2).
However, the selection sort can still offer a significant improvement for large
records that must be physically moved around in memory, causing the swap time to
be much more important than the comparison time. (Typically, this isn't the case in
Java, where references are moved around, not entire objects.)*/

public void selectionSort(int[] A){
  int i, j, min, temp;

  System.out.println("Selection Sort in action:");
  for(i=0; i< A.length; i++){
   min = i;
//   System.out.print(A[i] + "   ");

   for(j = i+1; j < A.length; j++){ // inner loop
     if(A[j] < A[min] )
        min = j; //swap the indices of the array.
	}  //end of inner-for

   //If WANT to see the action of the SORT, then UNcomment the next for-loop.
   //for(int k = 0; k < A.length; k++){ // inner loop
   //     System.out.print(A[k] + "   ");
   //}  //end of inner-for
   //System.out.println();
	temp = A[i]; //Swap elements of the array.
	A[i] = A[min];
	A[min] = temp;
   } // end outer-for
  }
/**************END of selectionSort() method*****************************/


/********************************************************/
/*					Merge Sort							*/
//////////////////////////////////////////////////////////

   public static int[] mergeSort(int[] whole) {
	if (whole.length == 1) {
	    return whole;
	}
	else {
	    // Create an array to hold the left half of the whole array
	    // and copy the left half of whole into the new array.
	    int[] left = new int[whole.length/2];
	    System.arraycopy(whole, 0, left, 0, left.length);

	    // Create an array to hold the right half of the whole array
	    // and copy the right half of whole into the new array.
	    int[] right = new int[whole.length-left.length];
	    System.arraycopy(whole, left.length, right, 0, right.length);

	    // Sort the left and right halves of the array.
	    left = mergeSort(left);
	    right = mergeSort(right);

	    // Merge the results back together.
	    merge(left, right, whole);

	    return whole;
	}
    }

    /**
     * Merge the two sorted arrays left and right into the
     * array whole.
     *
     * @param left a sorted array.
     * @param right a sorted array.
     * @param whole the array to hold the merged left and right arrays.
     */

public static void merge(int[] left, int[] right, int[] whole) {
	int leftIndex = 0;
	int rightIndex = 0;
	int wholeIndex = 0;

	// As long as neither the left nor the right array has
	// been used up, keep taking the smaller of left[leftIndex]
	// or right[rightIndex] and adding it at both[bothIndex].
	while (leftIndex < left.length &&
	       rightIndex < right.length) {
	    if (left[leftIndex] < right[rightIndex]) {
		whole[wholeIndex] = left[leftIndex];
		leftIndex++;
	    }
	    else {
		whole[wholeIndex] = right[rightIndex];
		rightIndex++;
	    }
	    wholeIndex++;
	}

	int[] rest;
	int restIndex;
	if (leftIndex >= left.length) {
	    // The left array has been use up...
	    rest = right;
	    restIndex = rightIndex;
	}
	else {
	    // The right array has been used up...
	    rest = left;
	    restIndex = leftIndex;
	}

	// Copy the rest of whichever array (left or right) was
	// not used up.
	for (int i=restIndex; i<rest.length; i++) {
	    whole[wholeIndex] = rest[i];
	    wholeIndex++;
	}
    }
/**************END of MergeSort() method*****************************/


/********************************************************/
/*					Quick Sort							*/
//////////////////////////////////////////////////////////
//This is probably the fastest sort method known so far.
//This sort method use recursion.

public void quickSort(int a[], int lo0, int hi0) throws Exception
   {
      int lo = lo0;
      int hi = hi0;
      int mid;

      if ( hi0 > lo0){
      /* Arbitrarily establishing partition element as the midpoint of
       * the array.*/
         mid = a[ ( lo0 + hi0 ) / 2 ];

         // loop through the array until indices cross
         while( lo <= hi ){
            /* find the first element that is greater than or equal to
             * the partition element starting from the left Index.
             */
            while( ( lo < hi0 ) && ( a[lo] < mid ) )
               ++lo;

            /* find an element that is smaller than or equal to
             * the partition element starting from the right Index.
             */
            while( ( hi > lo0 ) && ( a[hi] > mid ) )
               --hi;

            // if the indexes have not crossed, swap
            if( lo <= hi ){
               swap(a, lo, hi);
               ++lo;
               --hi;
            }
         }

         /* If the right index has not reached the left side of array
          * must now sort the left partition.
          */
         if( lo0 < hi )
            quickSort( a, lo0, hi );

         /* If the left index has not reached the right side of array
          * must now sort the right partition.
          */
         if( lo < hi0 )
            quickSort(a, lo, hi0 );
      }
   }

   public void swap(int a[], int i, int j){
      int T;
      T = a[i];
      a[i] = a[j];
      a[j] = T;
   }
/**************END of quickSort() method*****************************/


/********************************************************/
/*					Binary Search					    */
//////////////////////////////////////////////////////////

//public static int BinarySearch(int[] newarray, int searchKey){
  public boolean binarySearch(int[] newarray, int searchKey){
  int middle, low = 0, high;   //low = 0 means the first index in the array.
  high = newarray.length - 1;   //the last element of the array.
  int size = newarray.length;   //length of the aray.
  boolean TF = false;

  while (low <= high) {
	middle = (low + high)/2;
        //printRow(newarray, low, middle, high, size);
    if( searchKey == newarray[middle]){ //if found the match
    	TF = true;
		return TF;
	//	return middle;
	}
    else if (searchKey < newarray[middle])
	high = middle - 1;
    else
	low = middle + 1;
  }   //END of WHILE.
//  return -1;   //searchKey not found.
  return TF;   //searchKey not found.
}
/**************END of binarySearch() method*****************************/

}  //end of class SortNSearch{}