Question

1. Implement a method that meets the following requirements:

(a) Do not reuse any code for the following:

i. Try to write this method with as few lines of code as you can

ii. Sorts a group of three integers, x,y and z, into decreasing order (they do not have to be in a sequence).

iii. Assume the value in x is less than the value in z. You can also assume there are no duplicates among x, y and z (none of them contain the same value)

iv. Prints a message each time the order of two elements are changed.

v. Prints the list before and after sorting

(b) You can reuse Java API code and module code for the following:

i. Calls mergesort to sort the sequence of numbers into increasing order

ii. Prints the list after the second sorting.

(c) Implement a main method that calls the above methods, demonstrating their use with all applicable printed output

Answer 1

import java.util.*;
public class MergeSort
{
   // Function for 3-way merge sort process
   public static void mergeSort(Integer[] z)
   {
       // if array of size is zero returns null
       if (z== null)
           return;

       // creating duplicate of given array
       Integer[] x = new Integer[z.length];

       // copying alements of given array into
       // duplicate array
       for (int i = 0; i < x.length; i++)
           x[i] = z[i];

       // sort function
       mergeSort(x, 0, z.length, z);

       // copy back elements of duplicate array
       // to given array
       for (int i = 0; i < x.length; i++)
           z[i] = x[i];
   }

   /* Performing the merge sort algorithm on the
   given array of values in the rangeof indices
   [low, high). low is minimum index, high is
   maximum index (exclusive) */
   public static void mergeSort(Integer[] z,
               int low, int high, Integer[] y)
   {
       // If array size is 1 then do nothing
       if (high - low < 2)
           return;

       // Splitting array into 3 parts
       int mid1 = low + ((high - low) / 3);
       int mid2 = low + 2 * ((high - low) / 3) + 1;

       // Sorting 3 arrays recursively
       mergeSort(y, low, mid1, z);
       mergeSort(y, mid1, mid2, z);
       mergeSort(y, mid2, high, z);

       // Merging the sorted arrays
       merge(y, low, mid1, mid2, high, z);
   }

   /* Merge the sorted ranges [low, mid1), [mid1,
   mid2) and [mid2, high) mid1 is first midpoint
   index in overall range to merge mid2 is second
   midpoint index in overall range to merge*/
   public static void merge(Integer[] z, int low,
                       int mid1, int mid2, int high,
                               Integer[] y)
   {
       int i = low, j = mid1, k = mid2, l = low;

       // choose smaller of the smallest in the three ranges
       while ((i < mid1) && (j < mid2) && (k < high))
       {
           if (z[i].compareTo(z[j]) < 0)
           {
               if (z[i].compareTo(z[k]) < 0)
                   y[l++] = z[i++];

               else
                   y[l++] = z[k++];
           }
           else
           {
               if (z[j].compareTo(z[k]) < 0)
                   y[l++] = z[j++];
               else
                   y[l++] = z[k++];
           }
       }

       // case where first and second ranges have
       // remaining values
       while ((i < mid1) && (j < mid2))
       {
           if (z[i].compareTo(z[j]) < 0)
               y[l++] = z[i++];
           else
               y[l++] = z[j++];
       }

       // case where second and third ranges have
       // remaining values
       while ((j < mid2) && (k < high))
       {
           if (z[j].compareTo(z[k]) < 0)
               y[l++] = z[j++];

           else
               y[l++] = z[k++];
       }

       // case where first and third ranges have
       // remaining values
       while ((i < mid1) && (k < high))
       {
           if (z[i].compareTo(z[k]) < 0)
               y[l++] = z[i++];
           else
               y[l++] = z[k++];
       }

       // copy remaining values from the first range
       while (i < mid1)
           y[l++] = z[i++];

       // copy remaining values from the second range
       while (j < mid2)
           y[l++] = z[j++];

       // copy remaining values from the third range
       while (k < high)
           y[l++] = z[k++];
   }

   // Driver function
   public static void main(String args[])
   {
       // test case of values
       Integer[] data = new Integer[] {45, -2, -45, 78,
                           30, -42, 10, 19, 73, 93};
      
      
       System.out.println("data before sorting decreasing order ");
       for(int i=0;i<data.length;i++)
       System.out.print(data[i]+ " ");
       mergeSort(data);

       System.out.println("\nAfter merge sort: \n");
       for (int i = 0; i < data.length; i++)
           System.out.print(data[i] + " ");
   }
}
output

sorting before sorting decreasing order
45 -2 -45 78 30 -42 10 19 73 93
After merge sort:

-45 -42 -2 10 19 30 45 73 78 93