Review:   the selection sort algorithm for String arrays 

    public static void selectionSort(String[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        String help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(String[] myList, int start)
   {
       String min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].compareTo(min) < 0 ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        String[] myList = {"james", "abbot", "pat", "mary", "john"};
 
        selectionSort(myList);
       
       for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Problem:    write a selection sort algorithm to sort and array of Circle objects by their area

Original program: 

    public static void selectionSort(String[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        String help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(String[] myList, int start)
   {
       String min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].compareTo(min) < 0 ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        String[] myList = {"james", "abbot", "pat", "mary", "john"};
 
        selectionSort(myList);
       
       for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Problem:    write a selection sort algorithm to sort and array of Circle objects by their area

Modified program that sorts an array of Circle objects: 

    public static void selectionSort(Circle[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        Circle help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(Circle[] myList, int start)
   {
       Circle min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].getArea() < min.getArea() ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        Circle[] myList = new Circle[4]; // Array of Circles objs
        myList[0] = new Circle("red", 2);
        myList[1] = new Circle("blue", 1);
        myList[2] = new Circle("white", 5);
        myList[3] = new Circle("black", 3);
 
        selectionSort(myList);
        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Another problem:    write a selection sort algorithm to sort and array of Rectangle objects by their area

 

 

 

What do you have to do if you want to write a selectionSort( ) method that sorts Rectangle objects by their area ???

Another problem:    write a selection sort algorithm to sort and array of Rectangle objects by their area

We will have to change the data type of the selectionSort( ) to Rectangle: 

    public static void selectionSort(Circle[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        Circle help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(Circle[] myList, int start)
   {
       Circle min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].getArea() < min.getArea() ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        Circle[] myList = new Circle[4]; // Array of Circles objs
        myList[0] = new Circle("red", 2);
        myList[1] = new Circle("blue", 1);
        myList[2] = new Circle("white", 5);
        myList[3] = new Circle("black", 3);
 
        selectionSort(myList);
        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Another problem:    write a selection sort algorithm to sort and array of Rectangle objects by their area

Modified program that sorts an array of Rectangle objects: 

    public static void selectionSort(Rectangle[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        Rectangle help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(Rectangle[] myList, int start)
   {
       Rectangle min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].getArea() < min.getArea() ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        Rectangle[] myList = new Rectangle[4]; // Array of Rectangles objs
        myList[0] = new Rectangle("red", 2, 1);
        myList[1] = new Rectangle("blue", 1, 1);
        myList[2] = new Rectangle("white", 5, 1);
        myList[3] = new Rectangle("black", 3, 2);
 
        selectionSort(myList);
        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Problem with our solution

  • We can redundant (= duplicate) code:

      • The selectionSort( ) method for Circle and Rectangle is identical

      • The findSmallest( ) method for Circle and Rectangle is identical

  • $64,000 question:

      • Can we avoid writing 2 different methods to sort similar objects ???

  • Answer:

      • ???

         

         

Problem with our solution

  • We can redundant (= duplicate) code:

      • The selectionSort( ) method for Circle and Rectangle is identical

      • The findSmallest( ) method for Circle and Rectangle is identical

  • $64,000 question:

      • Can we avoid writing 2 different methods to sort similar objects ???

  • Answer:

      • We can write a selectionSort() to sort objects of the superclass !!!

      • Requirement:   the superclass object must provide all the necessary actions used in the selectionSort() algorithm

Using polymorphism to make a method more general

Consider the selectionSort algorithm on an array of Rectangle objects:    it only require the getArea() action. 

    public static void selectionSort(Rectangle[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        Rectangle help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(Rectangle[] myList, int start)
   {
       Rectangle min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].getArea() < min.getArea() ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        Rectangle[] myList = new Rectangle[4]; // Array of Rectangles objs
        myList[0] = new Rectangle("red", 2, 1);
        myList[1] = new Rectangle("blue", 1, 1);
        myList[2] = new Rectangle("white", 5, 1);
        myList[3] = new Rectangle("black", 3, 2);
 
        selectionSort(myList);
        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Using polymorphism to make a method more general

We specify the superclass GeometricObject as data type of the objects as parameter: 

    public static void selectionSort(GeometricObject[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        GeometricObject help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(GeometricObject[] myList, int start)
   {
       GeometricObject min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].getArea() < min.getArea() ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        GeometricObject[] myList = new GeometricObject[4]; // Array of GeometricObjects objs
        myList[0] = new Rectangle("red", 2, 1);   // Allowed !
        myList[1] = new Rectangle("blue", 1, 1);  // Allowed !
        myList[2] = new Rectangle("white", 5, 1); // Allowed !
        myList[3] = new Rectangle("black", 3, 2); // Allowed !
 
        selectionSort(myList);
        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Using polymorphism to make a method more general

The same method with an array of GeometricObject parameter can also be used to sort Circle objects: 

    public static void selectionSort(GeometricObject[] list) 
    {
        for (int i = 0; i < list.length - 1; i++) 
	{
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
	       ----------------------------------------------- */
            int minIndex = findSmallest(list, i );
  
	    /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary;
	       ------------------------------------------------------ */
	    if ( minIndex != i ) 
	    {   // Swap list[minIndex] and list[i]
	        GeometricObject help = list[minIndex];
                list[minIndex] = list[i];
		list[i] = help;
            }
        }
    }


   public static int findSmallest(GeometricObject[] myList, int start)
   {
       GeometricObject min;        // smallest value in array
       int    indexOfMin; // index where the smallest value is found

       // Find min value and its index
       min = myList[start];  // Assume first element is min
       indexOfMin = start;
       for ( int i = start+1; i < myList.length; i++ )
           if ( myList[i].getArea() < min.getArea() ) // Found a smaller element
           {
               min = myList[i];  // Update min value
               indexOfMin = i;
           }

       return indexOfMin;
   } 


    public static void main(String[] args)
    {
        GeometricObject[] myList = new GeometricObject[4]; // Array of GeometricObjects objs
        myList[0] = new Circle("red", 2);   // Allowed !
        myList[1] = new Circle("blue", 1);  // Allowed !
        myList[2] = new Circle("white", 5); // Allowed !
        myList[3] = new Circle("black", 3); // Allowed !
 
        selectionSort(myList);
        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }

Summary and postscript

  • A common technique to re-use code is write methods with a superclass type as parameter type

  • Such a method can receive objects of any subclass type as argument !

  • Requirement:

      • The superclass type must provide all the actions necessary to code the method

  • Java provides an interface mechanism that is similar to the inheritance mechanism for defining superclass type and subclass type relationship

  • Using this interface mechanism, we can make a "superclass" type that can unite the String , the Circle and the Rectangle classes !

  • The interface mechanism will be discussed in Chapter 13