//Recursive implementations of 3 common order N^2 sorting algorithms
// Insertion Sort    Selection Sort    Bubble Sort
import java.util.*;
public class SortMethods
{
   //INSERTION sort -------------------------------------------
   public static void insertionSort(ArrayList<Comparable> data)
   {
      if (data.size() > 1)
      {
         //Remove any data element from the list
         Comparable item = data.remove(0);
         
         //Recursively, sort the remaining data items
         insertionSort(data);
         
         //Insert the removed item into the now sorted remaining elements
         insert(item, data);
      }
   }
   
   //Insert a data item into a sorted list of data elements
   private static void insert(Comparable item, ArrayList<Comparable> data)
   {
      //Base Cases:
      //1) the list is empty
      //2) the item is smaller than, or equal to, the first data element
      if (data.isEmpty() || item.compareTo(data.get(0)) <= 0)
         data.add(0, item);
      else
      {
         //Remove the first element .. its the smallest
         Comparable first = data.remove(0);
         
         //Insert the new item into the remaining list of data elements
         insert(item, data);
         
         //Replace the removed smallest element at the head of the list
         data.add(0, first);
      }
   }
 
   
   //SELECTION sort -------------------------------------------
   public static void selectionSort(ArrayList<Comparable> data)
   {
      if (data.size() > 1)
      {
         //Select and remove the biggest data element
         Comparable biggest = selectMax(data);
         data.remove(biggest);
         
         //Recursively, sort the reduced data list
         selectionSort(data);
         
         //Append the biggest data element
         data.add(biggest);
      }
   }
   
   //A single pass/scan of SelectionSort scans the list to determine
   // the largest element of the list
   private static Comparable selectMax(ArrayList<Comparable> data)
   {
      //Base Case: The only element is biggest
      if (data.size() == 1)
         return data.get(0);
      
      //Remove the first data element  
      Comparable first = data.remove(0);
      
      //Recursively, elect the biggest of the remaining elements
      Comparable biggest = selectMax(data);
      
      //Replace the first data element
      data.add(0, first);
      
      //Return the bigger of the first, and biggest of the remainder
      return (first.compareTo(biggest) > 0 ? first : biggest);
    }

   
   //BUBBLE sort ---------------------------------------------      
   public static void bubbleSort(ArrayList<Comparable> data)
   {
      if (data.size() > 1)
      {
         //Bubble the biggest data element to the tail of the list
         bubbleScan(data);
         
         //Remove the biggest data element (from the tail of the list)
         Comparable biggest = data.remove(data.size() - 1);
         
         //Recursively, sort the remaining data elements
         bubbleSort(data);

         //Replace the biggest data element at the tail of the list
         data.add(biggest);
      }
   } 
   
   //A single pass/scan of BubbleSort swaps the biggest element
   // to the tail end of the list
   private static void bubbleScan(ArrayList<Comparable> data)
   {
      if (data.size() > 1)
      {
         //Remove the smaller of the first two data elements
         Comparable first = data.get(0).compareTo(data.get(1)) < 0 ?
                            data.remove(0) : data.remove(1) ;

         //Recursively, perform a bubble-scan of the remaining elements
         bubbleScan(data);
         
         //Replace the removed data element at the head of the list
         data.add(0, first);
       }
    }
}