In Display 13.5 , we described a sorting method to sort an array of type Comparable[] . In Display 12.6 , we described a sorting method that used the merge sort algorithm to sort an array of type double[] into increasing order. Redo the method in Display 12.6 so it applies to an array of type Comparable[]. Also, do a suitable test program.
Program:
// GeneralizedMergeSort.java
public class GeneralizedMergeSort
{
public static void sort(Comparable[] arr, int be, int en)
{
if((en - be) >= 1)
{
int splPt = split(arr, be, en);
sort(arr, be, splPt);
sort(arr, splPt + 1, en);
join(arr, be, splPt, en);
}
}
private static int split(Comparable[] arr, int be, int en)
{
return ((be + en) / 2);
}
private static void join(Comparable[] arr, int be, int splPt, int en)
{
int splitSize = (en - be + 1);
Comparable[] tempArr = new Comparable[splitSize];
int nextLeft = be;
int nextRight = splPt + 1;
int i = 0;
while((nextLeft <= splPt) && (nextRight <= en))
{
if(arr[nextLeft].compareTo(arr[nextRight]) < 0)
{
tempArr[i] = arr[nextLeft];
i++;
nextLeft++;
}
else
{
tempArr[i] = arr[nextRight];
i++;
nextRight++;
}
}
while(nextLeft <= splPt)
{
tempArr[i] = arr[nextLeft];
i++;
nextLeft++;
}
while(nextRight <= en)
{
tempArr[i] = arr[nextRight];
i++;
nextRight++;
}
for(i = 0; i < splitSize; i++)
{
arr[be + i] = tempArr[i];
}
}
}
// TestGeneralizedMergeSort.java
public class TestGeneralizedMergeSort
{
public static void main(String[] args)
{
Double[] doubles = new Double[6];
doubles[0] = 369.0;
doubles[1] = 891.0;
doubles[2] = 591.0;
doubles[3] = 753.0;
doubles[4] = 214.0;
doubles[5] = 435.0;
System.out.println("Double values before sorting:");
printArray(doubles);
GeneralizedMergeSort.sort(doubles, 0, doubles.length - 1);
System.out.println("\nDouble values after sorting:");
printArray(doubles);
String[] strings = new String[6];
strings[0] = "Plate";
strings[1] = "Bucket";
strings[2] = "Shampoo";
strings[3] = "Bag";
strings[4] = "Apples";
strings[5] = "Mobile";
System.out.println("\n\nString values before sorting:");
printArray(strings);
GeneralizedMergeSort.sort(strings, 0, strings.length - 1);
System.out.println("\nString values after sorting:");
printArray(strings);
}
public static void printArray(Comparable[] arr)
{
for(int i = 0; i < arr.length; i++)
{
System.out.print(arr[i]);
if(i != arr.length - 1)
System.out.print(", ");
}
System.out.println();
}
}
Output:
Double values before sorting:
369.0, 891.0, 591.0, 753.0, 214.0, 435.0
Double values after sorting:
214.0, 369.0, 435.0, 591.0, 753.0, 891.0
String values before sorting:
Plate, Bucket, Shampoo, Bag, Apples, Mobile
String values after sorting:
Apples, Bag, Bucket, Mobile, Plate, Shampoo