Question

This lab will focus on creating a better understanding of Selection Sort and Insertion Sort algorithms.

What you need to do

I have provided a driver and a Utility class with three methods. You must finish writing Selection Sort and Insertion Sort in the Utility class. Below is pseudocode for Selection and Insertion Sort, which you may use as a guide. Your selection sort will sort an array of Strings lexicographically, meaning A-Z. Your insertion sort will sort an array of Strings in reverse, meaning Z-A.

                      Selection Sort Pseudo Code

for i = 0 to length(A) min = i

for j = i to length(A) if A[j] < A[min]

min = j end for

                           swap A[i] and A[min]
                      end for

                      Insertion Sort Pseudo Code

for i = 1 to length(A) j=i

while j > 0 and A[j-1] < A[j] swap A[j] and A[j-1]

j=j-1 end while

end for

How do we compare strings to sort them correctly? Use the method compareTo provided in the string class. This method returns a int value and is used as follows:

<str1>.compareTo(<str2>)

If str1 comes before str2, compareTo will return a negative number. If str1 comes after str2, compareTo will return a positive number.
If str1 and str2 are the same, compareTo will return 0.

Driver Output

Unsorted array:
Tom, Steve, Ann, Zoe, Bob, Moana, Naomi, Kevin, Ryan, Nina, Dora, Wanda, Eric

Selection Sorted array from A-Z:
Ann, Bob, Dora, Eric, Kevin, Moana, Naomi, Nina, Ryan, Steve, Tom, Wanda, Zoe

Insertion Sorted array from Z-A:
Zoe, Wanda, Tom, Steve, Ryan, Nina, Naomi, Moana, Kevin, Eric, Dora, Bob, Ann

Driver.java///////

public class Driver {

   public static void main(String[] args) {
       // TODO Auto-generated method stub

       String[] names = {"Tom", "Steve","Ann","Zoe","Bob","Moana","Naomi","Kevin","Ryan","Nina","Dora","Wanda","Eric"};
      
       System.out.println("Unsorted array:");
       Utility.printArray(names);
       System.out.println();
      
       Utility.selectionSort(names);
       System.out.println("Selection Sorted array from A-Z:");
       Utility.printArray(names);
       System.out.println();

       Utility.insertionSort(names);
       System.out.println("Insertion Sorted array from Z-A:");
       Utility.printArray(names);
      
   }

}

Utility.java///////

public class Utility {

   public static void selectionSort(String[] array) {
       //TODO - Sort array from A-Z
   }
  
   public static void insertionSort(String[] array) {
       //TODO - Sort array from Z-A
   }
  
   public static void printArray(String[] array) {
      
       for(int i = 0; i < array.length; i++) {
           System.out.print(array[i]);
           if(i != array.length -1) {
               System.out.print(", ");
           }
       }
       System.out.println();
   }
  
}

Answer 1

Answer:

Driver.java:

public class Driver {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        String[] names = {"Tom", "Steve","Ann","Zoe","Bob","Moana","Naomi","Kevin","Ryan","Nina","Dora","Wanda","Eric"};

        System.out.println("Unsorted array:");
        Utility.printArray(names);
        System.out.println();

        Utility.selectionSort(names);
        System.out.println("Selection Sorted array from A-Z:");
        Utility.printArray(names);
        System.out.println();

        Utility.insertionSort(names);
        System.out.println("Insertion Sorted array from Z-A:");
        Utility.printArray(names);

    }

}

Utility.java:

public class Utility {

    public static void selectionSort(String[] array) {
        //TODO - Sort array from A-Z
        int n = array.length;

        // One by one move boundary of unsorted subarray
        for (int i=0; i<n-1; i++)
        {
            // Find the minimum element in unsorted array
            for (int j=i+1; j<n; j++)
            {
                if (array[i].compareTo(array[j]) > 0)
                {
                    // Swap the found minimum element with the first
                    // element
                    String temp=array[j];
                    array[j]=array[i];
                    array[i]=temp;
                }
            }
        }
    }


    public static void insertionSort(String[] array) {
        //TODO - Sort array from Z-A
        int n = array.length;
        int i,j;
        for (i = 1; i < n; i++)
        {

           String temp = array[i];
            j=i;
            while (i > 0 && array[i - 1].compareTo(temp) < 0)
            {
                array[i]=array[i-1];
                i--;
            }
            array[i]=temp;
        }
    }

    public static void printArray(String[] array) {

        for(int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            if(i != array.length -1) {
                System.out.print(", ");
            }
        }
        System.out.println();
    }

}

Output: