//COP 2210 Lab 10
//Demonstrate the Selection Sort algorithm by sorting an array of integers
//
// Norman Pestaina   July 19, 2015     Revised: July 24, 2016
//                                              July 19, 2017
import java.util.*;
import javax.swing.*;
public class SelectionSortDemo
{
   public static void main(String[] args)
   {
      int[] data = {57, 48, 17, 88, 12, 61, 27, 35, 28, 36};
      
      boolean again = false;  //Demo Continuation Flag
      
      do
      {
         selectionSort(data);       //Sort the current data
         
         again = newSortDemoPrompt();  //Prompt to repeat
         if ( again )
            data = randomData(10);     //Refresh the data
         
      } while ( again );
      
   }
   
   //An implementation of the ASCENDING order SELECTION SORT
   // @param data: an array of integers to be sorted
   private static void selectionSort( int[] data )
   {
      for (int pass = 1; pass < data.length; pass++)
      {
         int last = data.length - pass;     //index of last unsorted element
         int maxi = indexOfMax(data, last); //index of largest unsorted element
         swapElements(data, last, maxi);    //swap largest into highest position
         
         //This is not part of the Selection Sort process
         //It is included to demo the data after each pass
         display(data, pass, last, maxi);   
      }
   }
   
   //Return the index of the largest element in a prefix of an array
   // @param data : the data items 
   // @param limit: the highest index of the array to be scanned
   private static int indexOfMax(int[] data, int last)
   {
      int imax = 0;
      for (int scan = 0; scan <= last; scan++)
         if (data[scan] > data[imax])
            imax = scan;
      return imax;
   }
   
   //Swap (exchange) the items in a pair of array elements
   // @param data  : the data items
   // @param index1: the index of one element to be swapped
   // @param index2: the index of the other element of the pair
   private static void swapElements(int[] data, int index1, int index2)
   {
      int temporary = data[index1];
      data[index1] = data[index2];
      data[index2] = temporary;
   }
   
    //*************************************************************************
   //****************** Demo Implementation Helper Methods ********************
   
   //Display the sort parameters and data at the end of any Selection Sort pass
   private static void display(int[] data, int pass, int last, int maxi)
   {
      if ( pass == 1 )
         printHeader(data, pass, last, maxi);
      
      //Display the pass parameters
      JOptionPane.showInputDialog("Click OK when ready for Pass " + pass + " ?");
      System.out.print(pass + "\t\t" + last + "\t\t" + maxi);
      
      //Display the data at the end of the pass (already swapped)
      JOptionPane.showInputDialog("Swap  DATA[" + maxi + "] & DATA[" + last + "]" + 
                                  "\nClick OK to see the data AFTER swapping"  );
      System.out.println("\t\t" + Arrays.toString(data) );
   }
   
   //Header showing the captions & original data
   private static void printHeader(int[] data, int pass, int last, int maxi)
   {
      //Display Array Indexes
      String indexHeader = "\t\t\t\t\t\t ";
      for (int index = 0; index < data.length; index++)
         indexHeader += index + "   ";

      //Display Captions and Data in its original random order
      swapElements(data, last, maxi); //Restore original data order for the header
      System.out.println("\n\n" + indexHeader + "\nPass\tLast\tMaxi\t" + Arrays.toString(data));
      swapElements(data, last, maxi); //Restore pass-1 data order
   }
   
 
   //Prompt the user to play again or quit playing          
   private static boolean newSortDemoPrompt()
   {
      int option = JOptionPane.showConfirmDialog(null,
                   "Click YES To demo sort again. NO to Quit",
                   "SELECTION SORT DEMO", 
                   JOptionPane.YES_NO_OPTION );
                                                                  
      return option == JOptionPane.YES_OPTION ;
   }   
   
   //Return a 10-element array of random 2-digit integers
   private static int[] randomData(int size)
   {
      //Allocate array storage
      int[] data = new int[size];
      
      //Fill array with random 2-digit integers
      Random gen = new Random();
      for (int index = 0; index < data.length; index++)
         data[index] = 10 + gen.nextInt(90);
         
      return data;
   }
}