//********************************************************************
//  Sorts.java       Author: Lewis/Loftus/Cocking
//
//  Demonstrates the selection sort and insertion sort algorithms,
//  as well as a generic object sort.
//********************************************************************
@SuppressWarnings("unchecked")
public class Sorts
{
   //-----------------------------------------------------------------
   //  Sorts the specified array of integers using the selection
   //  sort algorithm.
   //-----------------------------------------------------------------
   public static void selectionSort (int[] numbers)
   {
      int min, temp;

      for (int index = 0; index < numbers.length-1; index++)
      {
         min = index;
         for (int scan = index+1; scan < numbers.length; scan++)
            if (numbers[scan] < numbers[min])
               min = scan;

         // Swap the values
         temp = numbers[min];
         numbers[min] = numbers[index];
         numbers[index] = temp;
      }
   }

   //-----------------------------------------------------------------
   //  Sorts the specified array of integers using the insertion
   //  sort algorithm.
   //-----------------------------------------------------------------
   public static void insertionSort (int[] numbers)
   {
      for (int index = 1; index < numbers.length; index++)
      {
         int key = numbers[index];
         int position = index;

         // shift larger values to the right
         while (position > 0 && numbers[position-1] > key)
         {
            numbers[position] = numbers[position-1];
            position--;
         }
            
         numbers[position] = key;
      }
   }

   //-----------------------------------------------------------------
   //  Sorts the specified array of objects using the insertion
   //  sort algorithm.
   //-----------------------------------------------------------------
   public static void insertionSort (Comparable[] objects)
   {
      for (int index = 1; index < objects.length; index++)
      {
         Comparable key = objects[index];
         int position = index;

         // shift larger values to the right
         while (position > 0 && objects[position-1].compareTo(key) > 0)
         {
            objects[position] = objects[position-1];
            position--;
         }
            
         objects[position] = key;
      }
   }
}

Classwork:
1. Tell the story of the Insertion Sort to someone who knows no computer programming.
2. Show the sequence of changes the insertion sort algorithm makes to the following list of numbers:
5 7 1 8 2 4 3

Assignments:
MC 6.6
T/F 6.8 and 6.10
SA 6.4 and 6.5
Programming Projects 6.11:
Modify the Tunes program so that it keeps the CDs sorted by title. Use the general object sort defined in the Sorts class from this chapter.

Programming Projects 6.12
Modify the Sorts class to include an overloaded version of the SelectionSort method that performs a general object sort. Modify the SortPhoneList program to test the new sort.