I have a java program with 2 classes(MergeSort, QuickSort) that work only with e
ID: 3843958 • Letter: I
Question
I have a java program with 2 classes(MergeSort, QuickSort) that work only with elements of type double. I'm suppose to modify either of these programs to work with elements of any data type that implements the Comparable interface. This is the prompt that I need to know for my test so any help would be appreciated.
Create a “tester” program which sorts four arrays, one each of the following data types:
Character (the wrapper class)
Integer (the wrapper class)
Double (the wrapper class)
String
Each array should have at least six elements in unsorted order.
Print each array both before and after being sorted.
Submit a listing of your updated QuickSort.java or MergeSort.java program, along with a listing of your “tester” program and a PrintScreen of the results.
Heres what I have so far
* Description: Class that realizes the divide-and-conquer sorting pattern and
* uses the quicksort algorithm.
*
* Instance Variables
* (none)
*
* Methods:
* sort - performs a recursive sort using quicksort algorithm
* split - writes everything below a splitValue (which in this case
* is the first element being "sorted", then the splitValue itself,
* then everything greater than the splitValue
* join - does nothing in the quick sort algorithm
*/
public class QuickSort {
public static void sort(double[] a, int begin, int end) {
// If sorting more than one element, then perform a sort, otherwise
// do nothing
if ((end - begin) >= 1) {
/*******************************************************************
* For a quick sort, this is the method that does all the work. It
* takes the element at index 'begin' as the splitValue, and uses it
* to sort all of the
* elements from begin to end into those less than the split point,
* the split point itself, and those elements greater than the
* split point
********************************************************************/
int splitPoint = split(a, begin, end);
/********************************************************************
* The first sort now sorts everything above the splitValue calculated
* above in splitPoint (which we know is less than the original
* element at a[begin]), and those less than the splitValue from
* above.
********************************************************************/
sort(a, begin, splitPoint) ;
sort(a, splitPoint + 1, end) ;
// In a quick sort, the join method does nothing
join(a, begin, splitPoint, end) ;
}
}
// In a quick sort, this method does all the work
private static int split(double[] a, int begin, int end) {
// Create a new temporary array to store the elements divided into
// those less than the split point (the first element), the split
// point, and those elements greater than the split point
double[] temp;
int size = (end - begin + 1);
temp = new double[size];
// Use the first element in the array being sorted as the split value
double splitValue = a[begin];
int up = 0;
int down = size - 1;
// Note that a[begin] = splitValue is skipped -- the starting value
// If the next element in the array is less than splitValue, then add
// to the front of the new array, otherwise add to the back of the
// new array
for (int i = begin + 1; i <= end; i++) {
if (a[i] < splitValue) { // changed from version in book!!!!
temp[up++] = a[i];
} else {
temp[down--] = a[i];
}
}
// 0 <= up = down < size
// Last thing to do is add the splitValue itself into the array
// of elements in temp
temp[up] = a[begin];
// Copy the temporary array back into the original array
for (int i = 0; i < size; i++)
a[begin + i] = temp[i];
// As a result, we have written elements less than the splitValue element,
// then the splitValue element, then those elements greater than the
// splitValue element:
// temp[i] <= splitValue for i < up
// temp[up] = splitValue
// temp[i] > splitValue for i > up
return (begin + up);
}
private static void join(double[] a, int begin, int splitPoint, int end) {
//Nothing to do.
}
}
* Description: Class that realizes the divide-and-conquer sorting pattern and
* uses the merge sort algorithm.
*
* Instance Variables
* (none)
*
* Methods:
* sort - performs a recursive sort using merge sort algorithm
* split - determines midpoints between two points
* join - joins two sorted arrays of doubles into a single array
*/
public class MergeSort {
public static void sort(double[] a, int begin, int end) {
// If sorting more than one element, then perform a sort, otherwise
// do nothing
if ((end - begin) >= 1) {
/*******************************************************************
* Determine the midpoint between the part of the part of the array
* to be sorted
******************************************************************/
int splitPoint = split(a, begin, end) ;
/*************************************************
* Sort the left chunk, then sort the right chunk
*************************************************/
sort(a, begin, splitPoint) ;
sort(a, splitPoint + 1, end) ;
/*******************************************************
* Merge the two chunks back into a single sorted array
*******************************************************/
join(a, begin, splitPoint, end) ;
}
}
// Determine the midpoint between the beginning and ending indexes
private static int split(double[] a, int begin, int end) {
return (begin + end) / 2 ;
}
// Join two sub arrays (assumed to be sorted) into a single sorted array
// using a temporary array to hold the results, then copy back into the
// original array
private static void join(double[] a, int begin, int splitPoint, int end)
{
// Create a temporary array to hold new sorted array resulting from
// merging left and right chunks of array
double[] temp;
int intervalSize = (end - begin + 1);
temp = new double[intervalSize];
// Left chunk extends from a[index] to a[splitPoint]
// Right chunk extends from a[splitPoint + 1] to a[end]
int nextLeft = begin; //index for first chunk
int nextRight = splitPoint + 1; //index for second chunk
int i = 0; //index into temporary array
// Merge until one side is exhausted, taking the next smallest element
// from either the left or right chunk
while ((nextLeft <= splitPoint) && (nextRight <= end)) {
if (a[nextLeft] < a[nextRight]) {
temp[i++] = a[nextLeft++];
} else {
temp[i++] = a[nextRight++];
}
}
// Copy the rest of the left chunk, if any is left
while (nextLeft <= splitPoint) {
temp[i++] = a[nextLeft++];
}
// Copy the rest of the right chunk, if any if left
while (nextRight <= end) {
temp[i++] = a[nextRight++];
}
// Copy the sorted array (in temp) back to original array
for (i = 0; i < intervalSize; i++) {
a[begin + i] = temp[i];
}
/////
}
public static void sort(int[] a, int begin, int end) {
// If sorting more than one element, then perform a sort, otherwise
// do nothing
if ((end - begin) >= 1) {
/*******************************************************************
* Determine the midpoint between the part of the part of the array
* to be sorted
******************************************************************/
int splitPoint = split(a, begin, end) ;
/*************************************************
* Sort the left chunk, then sort the right chunk
*************************************************/
sort(a, begin, splitPoint) ;
sort(a, splitPoint + 1, end) ;
/*******************************************************
* Merge the two chunks back into a single sorted array
*******************************************************/
join(a, begin, splitPoint, end) ;
}
}
private static int split(int[] a, int begin, int end) {
return (begin + end) / 2 ;
}
private static void join(int[] a, int begin, int splitPoint, int end)
{
// Create a temporary array to hold new sorted array resulting from
// merging left and right chunks of array
int[] temp;
int intervalSize = (end - begin + 1);
temp = new int[intervalSize];
// Left chunk extends from a[index] to a[splitPoint]
// Right chunk extends from a[splitPoint + 1] to a[end]
int nextLeft = begin; //index for first chunk
int nextRight = splitPoint + 1; //index for second chunk
int i = 0; //index into temporary array
// Merge until one side is exhausted, taking the next smallest element
// from either the left or right chunk
while ((nextLeft <= splitPoint) && (nextRight <= end)) {
if (a[nextLeft] < a[nextRight]) {
temp[i++] = a[nextLeft++];
} else {
temp[i++] = a[nextRight++];
}
}
// Copy the rest of the left chunk, if any is left
while (nextLeft <= splitPoint) {
temp[i++] = a[nextLeft++];
}
// Copy the rest of the right chunk, if any if left
while (nextRight <= end) {
temp[i++] = a[nextRight++];
}
// Copy the sorted array (in temp) back to original array
for (i = 0; i < intervalSize; i++) {
a[begin + i] = temp[i];
}
}
}
Explanation / Answer
class QuickSort
{
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
if (arr[j] <= pivot)
{
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
void sort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
*/ to make this program work with different types of variable we need to do minor changes and these are
1. change type of input to desired type
2. we need to change the type of the partition function used in this program and we also need to change the 1st argument that is int arr[] type to desired input.
3. in the function void sort we need to change the type of the argument.
same changes you can do for merge sort also */
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.