/**
 * Class that implements 5 sorting algorithms:  
 *    Bubble Sort
 *    Insertion Sort
 *    Merge Sort
 *    Quick Sort
 *    Selection Sort
 */

public class Sorts {
   /**
    * ----------BUBBLE SORT--------
    * parameter: array of integers
    * return: array of integers in sorted order
    */
   public static int[] bubbleSort(int[] tempArr) {
      int n = tempArr.length;
      int[] numbers = new int[tempArr.length];
      for (int i = 0 ; i < tempArr.length; i++) {
         numbers[i] = tempArr[i];
      }
      boolean sorted = false;
      for (int i=1; (i < numbers.length) && !sorted; i++){
         sorted = true;
         for (int j = 0; j < n - i; j++) {
            int next = j+1;
            if (numbers[j] > numbers[next]) {
               swap(numbers,j,next);
               sorted = false;
            }
         }
      }
      return numbers;
   }
   
   /**
    * ----------INSERTION SORT--------
    * parameter: array of integers
    * return: array of integers in sorted order
    */
   public static int[] insertionSort(int[] tempArr){
      int j, key;
      int[] numbers = new int[tempArr.length];
      for (int i = 0 ; i < tempArr.length; i++) {
         numbers[i] = tempArr[i];
      }      
      for (int i = 1; i < numbers.length; i++){
         key = numbers[i];
         j = i-1;
         while ((j >= 0) && (numbers[j] > key)){
            numbers[j+1] = numbers[j];
            j = j - 1;
         }
         numbers[j+1] = key;
      }
      return numbers;
   }
   
   /**
    * ----------SELECTION SORT--------
    * parameter: array of integers
    * return: array of integers in sorted order
    */
   public static int[] selectionSort(int[] tempArr) {
      int n = tempArr.length;
      int[] numbers = new int[tempArr.length];
      for (int i = 0 ; i < tempArr.length; i++) {
         numbers[i] = tempArr[i];
      }
      
      for (int last=n-1; last >= 1; last--) {
         int largest = indexOfLargest(numbers, last+1);
         swap(numbers,largest,last);
      }
      return numbers;
   }
   
   /**
    * private method used by selection sort.
    */
   private static int indexOfLargest(int[] arr, int size) {
      int indexSoFar = 0;
      for (int i = 1; i < size; i++) {
         if (arr[i] > arr[indexSoFar]) {
            indexSoFar = i;
         }
      }
      return indexSoFar;
   }
   
   /**
    * ----------MERGE SORT--------
    * parameter: array of integers
    * return: array of integers in sorted order
    */
   public static int[] mergeSort(int[] tempArr) {
      int[] numbers = new int[tempArr.length];
      for (int i = 0 ; i < tempArr.length; i++)
         numbers[i] = tempArr[i];
      m_sort(numbers, 0, numbers.length - 1);
      return numbers;
   }
   
   /**
    * private method that performs mergesort.
    */
   private static void m_sort(int numbers[], int first, int last) {
      int mid;
      
      if (first < last)
      {
         mid = (first + last) / 2;
         m_sort(numbers, first, mid);
         m_sort(numbers, mid+1, last);
         
         merge(numbers, first, mid, last);
      }
   }
   
   /**
    * private method used by mergesort to combine segments of an integer array
    * in sorted order.
    */
   private static void merge(int[] numbers, int first, int mid, int last) {   
      int maxSize = numbers.length;
      int[] tempArray = new int[maxSize];
      int first1 = first;
      int last1 = mid;
      int first2 = mid+1;
      int last2 = last;
      int index = first1;
      
      while ((first1 <= last1) && (first2 <= last2)) {
         if (numbers[first1] < numbers[first2]) {
            tempArray[index] = numbers[first1];
            first1++;
         }
         else {
            tempArray[index] = numbers[first2];
            first2++;
         }
         index++;
      }
      
      while (first1 <= last1) {
         tempArray[index] = numbers[first1];
         first1++;
         index++;
      }
      while (first2 <= last2) {
         tempArray[index] = numbers[first2];
         first2++;
         index++;
      }
      
      for (int i=first; i <= last; i++) {
         numbers[i] = tempArray[i];
      }
   }
   
   /**
    * ----------QUICK SORT--------
    * parameter: array of integers
    * return: array of integers in sorted order
    */
   public static int[] quickSort(int[] tempArr) {
      int[] numbers = new int[tempArr.length];
      for (int i = 0 ; i < tempArr.length; i++)
         numbers[i] = tempArr[i];
      q_sort(numbers, 0, numbers.length - 1);
      return numbers;
   }
   
   /**
    * main quicksort algorithm, called by public quicksort method.
    * initial call sends in an integer array, and the entire range of
    * the array.
    */
   private static void q_sort(int[] numbers,int left, int right) {
      int pivot, l_hold, r_hold;      
      if (left < right) {
         pivot = partition(numbers, left, right);
         q_sort(numbers, left, pivot-1);
         q_sort(numbers, pivot+1, right);
      }
   }
    
   /**
    * Private method used by quickSort method
    * parameters: integer array, indexes of the range of the array to
    * be partitioned.
    */
   private static int partition(int[] theArray, int first, int last) {
      int pivot = theArray[first];
      int lastS1 = first;
      int firstUnknown = first+1;
      while (firstUnknown <= last) {
         if (theArray[firstUnknown] < pivot) {
            lastS1++;
            swap(theArray, firstUnknown, lastS1);
            firstUnknown++;          
         } else {
            firstUnknown++;
         }
      }
      swap(theArray, first, lastS1);
      return lastS1;
   }
   
   
   /**
    * method used by bubbleSort, selectionSort, and quickSort
    * parameters: integer array and indexes of array positions to
    * exchange
    */
   private static void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
   }
}