Review:   the selection sort algorithm

Recall the selection sort algorithm for an array of integer: : 

    public static void selectionSort(int[] list) 
    {
        for (int i = 0; i < list.length-1; i++)
        {
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
               ----------------------------------------------- */
           int min      = list[i];     // Assume first element is min
           int minIndex = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k] < min ) // Found a smaller element
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                int help       = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

In order to use the selectionSort algorithm to sort an array of Circle object, we must make some changes: : 

    public static void selectionSort(int[] list) 
    {
        for (int i = 0; i < list.length-1; i++)
        {
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
               ----------------------------------------------- */
           int min      = list[i];     // Assume first element is min
           int minIndex = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k] < min ) // Found a smaller element
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                int help       = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

(1) The data type of the elements used in selectionSort( ) (int) must be changed to Circle: 

    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]
               ----------------------------------------------- */
           Circle min   = list[i];     // Assume first element is min
           int minIndex = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k] < min ) // Found a smaller element
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                Circle help    = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

(2) The expression to compare Circles by their area is:   list[k].getArea < min.getArea() 

    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]
               ----------------------------------------------- */
           Circle min   = list[i];     // Assume first element is min
           int minIndex = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // Found a smaller area
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                Circle help    = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

Test program for the selection sort algorithm for an array of Circle objects: 

    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]);
    }



 Output:
         Color = blue : radius = 1.0
	 Color = red : radius = 2.0
	 Color = black : radius = 3.0
	 Color = white : radius = 5.0

DEMO: 04-inheritance/20-sort-geom/Demo.java

Is that all there is ??? --- Wait... things will get more interesting soon 😅

Problem 2:    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 ???

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

In order to use the selectionSort algorithm to sort an array of Rectangle object, we must make some changes: : 

    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]
               ----------------------------------------------- */
           Circle min   = list[i];     // Assume first element is min
           int minIndex = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // Found a smaller element
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                Circle help    = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

(1) The data type of the elements used in sorting (Circle) must be changed to Rectangle: 

    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]
               ----------------------------------------------- */
           Rectangle min = list[i];     // Assume first element is min
           int minIndex  = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // How about this expression?
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                Rectangle help = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

Interestingly, the expression to compare Circles by their area is the same:   list[k].getArea < min.getArea() 

    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]
               ----------------------------------------------- */
           Rectangle min = list[i];     // Assume first element is min
           int minIndex  = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // Use the same expression !!
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                Rectangle help = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

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

Test program that sorts an array of Rectangle objects: 

    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]);
    }



Output:
       Color = blue : width = 1.0, height = 1.0
       Color = red : width = 2.0, height = 1.0
       Color = white : width = 5.0, height = 1.0
       Color = black : width = 3.0, height = 2.0

DEMO: 04-inheritance/19-apply-polym/Demo2.java

Problem with our solution

  • We have redundant (= duplicate) code:

      • The statements in selectionSort( ) method for Circle and Rectangle are identical

        (The difference in data type is not a statement)

  • $64,000 question:

      • Can we avoid writing 2 identical method to sort similar objects ???

  • Answer:

      • ???

Problem with our solution

  • We have redundant (= duplicate) code:

      • The statements in selectionSort( ) method for Circle and Rectangle are identical

        (The difference in data type is not a statement)

  • $64,000 question:

      • Can we avoid writing 2 identical method to sort similar objects ???

  • Answer:

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

      • Provided that:   the superclass object can 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 requires the use of getArea(): 

    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]
               ----------------------------------------------- */
           Rectangle min = list[i];     // Assume first element is min
           int minIndex  = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // Required functionality to sort
               {
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                Rectangle help = list[minIndex];  // Standard exchange alg
                list[minIndex] = list[i];
                list[i]        = help;
            }
        }
    }

 

Using polymorphism to make a method more general

Since the GeometricObject has the getArea() method, we can write insertionSort( ) for GeometricObject object: 

    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]
               ----------------------------------------------- */
           GeometricObject min = list[i];     // Assume first element is min
           int minIndex        = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // getArea() always returns 0 ??
               {                                           Is this useful in sorting ??
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                GeometricObject help = list[minIndex];  // Standard exchange alg
                list[minIndex]       = list[i];
                list[i]              = help;
            }
        }
    }

However:   the getArea( ) method in GeometricObject is a dummy method that always returns 0 (zero)...

Using polymorphism to make a method more general

Review:   using a superclass variable to invoke methods in a subclass object:

 
 

Java allows you to access members in a subclass (e.g.: Rectangle) using a superclass variable (e.g.: GeomObject)

Using polymorphism to make a method more general

This means:   we can pass (= copy) an array of Rectangle objects to this selectionSort( ) method: 

    public static void selectionSort(GeometricObject[] list) // list can be Rectangle[]
    {
        for (int i = 0; i < list.length-1; i++)
        {
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
               ----------------------------------------------- */
           GeometricObject min = list[i];     // Assume first element is min
           int minIndex        = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // --> getArea() will return 
               {                                        //     area of a Rectangle !!
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                GeometricObject help = list[minIndex];  // Standard exchange alg
                list[minIndex]       = list[i];
                list[i]              = help;
            }
        }
    }

If was pass an array of Rectangle objects to selectionSort( ), the getArea( ) will area of the rectangle!

Using polymorphism to make a method more general

Test program to sort an array of Rectangle object: 

    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);
 
        // ******************************************************************
        // We can pass an array of Rectangle to selectionSort
        // because a Rectangle can fulfill requests made to a GeometricObject
        // ******************************************************************
        selectionSort(myList);

        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }



Output:
       Color = blue : width = 1.0, height = 1.0
       Color = red : width = 2.0, height = 1.0
       Color = white : width = 5.0, height = 1.0
       Color = black : width = 3.0, height = 2.0

DEMO: 04-inheritance/19-apply-polym/Demo3.java

Using polymorphism to make a method more general

Also:   we can pass (= copy) an array of Circle objects to this selectionSort( ) method: 

    public static void selectionSort(GeometricObject[] list) // list can be Circle[]
    {
        for (int i = 0; i < list.length-1; i++)
        {
            /* -----------------------------------------------
               Find the minimum in the list[i..list.length-1]
               ----------------------------------------------- */
           GeometricObject min = list[i];     // Assume first element is min
           int minIndex        = i;           // Index where min is found

           for ( int k = minIndex+1; k < list.length; k++ )
               if ( list[k].getArea() < min.getArea() ) // --> getArea() will return 
               {                                        //     area of a Circle !!   
                   min      = list[k]; // Update min value
                   minIndex = k;       // Update its index
               }

            /* ------------------------------------------------------
               Swap list[i] with list[minIndex] if necessary
               ------------------------------------------------------ */
            if ( minIndex != i )
            {   // Swap list[minIndex] and list[i]
                GeometricObject help = list[minIndex];  // Standard exchange alg
                list[minIndex]       = list[i];
                list[i]              = help;
            }
        }
    }

If was pass an array of Circle objects to selectionSort( ), the getArea( ) will area of the circle!

Using polymorphism to make a method more general

Demo program:   pass an array of Circle object to this selectionSort( ) method: 

    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);
 
        // ******************************************************************
        // We can pass an array of Rectangle to selectionSort
        // because a Rectangle can fulfill requests made to a GeometricObject
        // ******************************************************************
        selectionSort(myList);

        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }



 Output:
         Color = blue : radius = 1.0
         Color = red : radius = 2.0
         Color = black : radius = 3.0
         Color = white : radius = 5.0

DEMO: 04-inheritance/19-apply-polym/Demo4.java

Using polymorphism to make a method more general

We can even sort a mix of Circle and Rectangle objects: 

    public static void main(String[] args)
    {
        GeometricObject[] myList = new GeometricObject[4]; // Array of GeometricObject objs

        myList[0] = new Circle("red", 2);          // a Circle
        myList[1] = new Rectangle("blue", 1, 1);   // a Rectangle
        myList[2] = new Circle("white", 5);        // a Circle
        myList[3] = new Rectangle("black", 4, 4);  // a Rectangle

        selectionSort(myList);

        for ( int i = 0; i < myList.length; i++)
           System.out.println(myList[i]);
    }



 Output:
           Color = blue : width = 1.0, height = 1.0       // Area = 1.0
	   Color = red : radius = 2.0                     // Area = 12.56
	   Color = black : width = 4.0, height = 4.0      // Area = 16.0
	   Color = white : radius = 5.0                   // Area = 78.5

DEMO: 04-inheritance/19-apply-polym/Demo5.java

Summary and final comments

  • A common technique to generalize 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

  • Comments:   interface

    • 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 non-related classes (such as String , Circle and Rectangle classes !)

    • The interface mechanism will be discussed in Chapter 13 (next)