Solved

# Java Merge Sort implementation to sort increase and sort decrease an array

Posted on 2006-04-05
Medium Priority
621 Views
I have write a program with the following specifications:

1. I have to use merge-sort algorithm, modifying methods sortIncrease(double[] x) and sortDecrease(double[] x) below, for a given array:

public interface MyapiA {

public void sortIncrease(double[] x);

public void sortDecrease(double[] x);
}
__________________________________________________________________________
public class SortA implements MyapiA {

public void sortIncrease(double[] x) {
for (int i = 0; i <x.length; i++) {
for (int j = 1; j < x.length; j++) {
if (x[j] < x[j - 1]){
double temp = x[j];
x[j] = x[j - 1];
x[j - 1] = temp;
}
}
}
}

public void sortDecrease(double[] x) {
for (int i = 0; i <x.length; i++) {
for (int j = 1; j < x.length; j++) {
if (x[j] > x[j - 1]){
double temp = x[j];
x[j] = x[j - 1];
x[j - 1] = temp;
}
}
}
}
}
____________________________________________________________________
public interface MyapiB {

public void sortIncrease(int x);

public void sortDecrease(int x);
}
____________________________________________________________________

public class SortB extends SortA implements MyapiB{

//instance variables
double[] array;

/**
* Method SortB
*
*
*/
public SortB(int x) {

//creates the array to hold the random numbers
array = new double[x];// array with x doubles

}

/**
* Method getArray
*
* To return the array
*
*
*/
public double[] getArray()
{
return array;
}

/**
* Method sortIncrease
*
* Creates the array acording to the size input;
* Generates random numbers;
* Calls SortA sortIncrease(double[] x) to sort the array (increasing)
* Prints results
*
*/
public void sortIncrease(int x){

//generates random numbers and stores in the array
for (int i = 0; i < x; i++){
array[i] = Math.random()*100;
}

//calls sortIncrease(double[] x) from SortA

sortIncrease(array);

//prints out the sorted array

System.out.println("SortIncrease---");
System.out.println();
for (int i=0; i < array.length; i++){
System.out.println("i="+i+"  "+getArray()[i]);
if((i+1)%3==0){
System.out.println();
}
}
}

/**
* Method sortDecrease
*
* Creates the array acording to the size input;
* Generates random numbers;
* Calls SortA sortDecrease(double[] x) to sort the array (increasing)
* Prints results
*
*/
public void sortDecrease(int x){

//creates the array to hold the random numbers
// array = new double[x];// array with x doubles

//generates random numbers and stores in the array
for (int i = 0; i < x; i++){
array[i] = Math.random()*100;
}

//calls sortDecrease(double[] x) from SortA

sortDecrease(array);

//prints out the sorted array

System.out.println("SortDecrease---");
System.out.println();
for (int i=0; i< x; i++){
System.out.println("i="+i+"  "+getArray()[i]);
if((i+1)%3==0){
System.out.println();
}
}
}
}
_______________________________________________________________________

public class Sort extends SortB{

int x;
SortB s = new SortB(x);

public static void main(String[] args) {

int x = Integer.parseInt(args[0]);

//creates a new object SortB, which will take the argument for the size
//of the array from the user input

//  SortB s = new SortB(x);

//chararacter "c" is an input from the user, as for which operation to
//perform: increase, or decrease sorting

char c = args[1].charAt(0);

//if statement to direct the flow to either increase, if chosen "i", or
//decrease, if chosen "d"

if(c=='i'){
sortIncrease(x);
}else if(c=='d'){
sortDecrease(x);
}

}
}

Class Sort was not working, though, but the others were fine.

The implementation of merge sort, has to use an interface MyapiC, defining the methods already created below:

public interface MyapiC
{
public void mergeSort(double[] x, Comparator c);

public void merge(double[] x1, double[] x2, Comparator c, double[] x);
}

And then, I have to create a new class mergeSort to implement this interface:

public class mergeSort implements MyapiC
{
// instance variables - replace the example below with your own
private int x;

/**
* Constructor for objects of class mergeSort
*/
public static void mergeSort(double[] x, Comparator c) { // nonrecursive
double[] x1 = new double[x.length]; // make a new temporary array
System.arraycopy(x,0,x1,0,x1.length); // copy the input
double[] x2 = new double[x1.length]; // output array
double[] temp; // temp array reference used for swapping
int n = x1.length;
for (int i=1; i < n; i*=2) { // each iteration sorts all length-2*i runs
for (int j=0; j < n; j+=2*i)  // each iteration merges two length-i pairs
merge(x1,x2,c,j,i); // merge from in to out two length-i runs at j
temp = x1; x1 = x2; x2 = temp; // swap arrays for next iteration
}
// the "in" array contains the sorted array, so re-copy it
System.arraycopy(x1,0,x,0,x1.length);
}

/**
* An example of a method - replace this comment with your own
*
* @param  y   a sample parameter for a method
* @return     the sum of x and y
*/
protected static void merge(double[] x1, double[] x2, Comparator c, int start,
int inc) { // merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]
int x = start; // index into run #1
int end1 = Math.min(start+inc, x1.length); // boundary for run #1
int end2 = Math.min(start+2*inc, x1.length); // boundary for run #2
int y = start+inc; // index into run #2 (could be beyond array boundary)
int z = start; // index into the out array
while ((x < end1) && (y < end2))
if (c.compare(x1[x],x1[y]) <= 0) x2[z++] = in[x++];
else x2[z++] = x1[y++];
if (x < end1) // first run didn't finish
System.arraycopy(x1, x, x2, z, end1 - x);
else if (y < end2) // second run didn't finish
System.arraycopy(x1, y, x2, z, end2 - y);
}
}

However, I got stuck in how to proceed. To begin with, my class mergeSort is not compiling, stating this is not an abstract class and does not override abstract method merge from MyapiC.

Any idea on how to implement that?

Thanks!
0
Question by:EDTW
• 6
• 3
• 3

LVL 14

Expert Comment

ID: 16385241
First of all You should inform Your instructor, that class names begins with capital letter(at least this is the practice).

Second, what errors do You get from compiler
0

Author Comment

ID: 16385394
Yes, I've noticed some classes are using capital letters and others are not... but I guess he is keeping consistency with the textbook, for some reason is doing the same. Interesting, isn't it?

The error message, when compiling mergeSort is exactly: mergeSort is not abstract and does not override abstract method merge(double[],double[],java.util.Comparator,double[]) in MyapiC
0

LVL 14

Accepted Solution

StillUnAware earned 1000 total points
ID: 16385466
> public void merge(double[] x1, double[] x2, Comparator c, double[] x);  // in MyapiC

> protected static void merge(double[] x1, double[] x2, Comparator c, int start, int inc) { // in mergeSort

those two doesn't match, the parameters are different and You try to lower the access to the method, so it should become something like this:

public void merge(double[] x1, double[] x2, Comparator c, double[] x) { // in mergeSort
//at the beggining You can do that:
int start = (int)x[0];
int inc = (int)x[1];
// but also the calling method must suply the right values
}

0

Author Comment

ID: 16385722
Did it... but still get the message: merge(double[],double[],java.util.Comparator,double[]) in mergeSort cannot implement merge(double[],double[],java.util.Comparator,double[]) in MyapiC; overriding method is static
0

LVL 14

Expert Comment

ID: 16386182
as I wrote, the method declaration must match the one it overrides, in other words it must not be static
0

Author Comment

ID: 16386348
Yeap! I removed the static... it was still giving an error because of the protected class, so I removed that, as well. Then I had to change: merge(x1,x2,c,x);  removing the integers and replacing by x, however this is the cause of another error (x is already defined in merge(double[],double[],java.util.Comparator,double[])...

I copied the modified class below for clarity:

public class mergeSort implements MyapiC
{
// instance variables - replace the example below with your own
private int x;

/**
* Constructor for objects of class mergeSort
*/
public void mergeSort(double[] x, Comparator c) { // nonrecursive
double[] x1 = new double[x.length]; // make a new temporary array
System.arraycopy(x,0,x1,0,x1.length); // copy the input
double[] x2 = new double[x1.length]; // output array
double[] temp; // temp array reference used for swapping
int n = x1.length;
for (int i=1; i < n; i*=2) { // each iteration sorts all length-2*i runs
for (int j=0; j < n; j+=2*i)  // each iteration merges two length-i pairs
merge(x1,x2,c,x); // merge from in to out two length-i runs at j
temp = x1; x1 = x2; x2 = temp; // swap arrays for next iteration
}
// the "in" array contains the sorted array, so re-copy it
System.arraycopy(x1,0,x,0,x1.length);
}

/**
* An example of a method - replace this comment with your own
*
* @param  y   a sample parameter for a method
* @return     the sum of x and y
*/
public void merge(double[] x1, double[] x2, Comparator c, double[] x) { // merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]
int start = (int)x[0];
int inc = (int)x[1];

int x = start; // index into run #1
int end1 = Math.min(start+inc, x1.length); // boundary for run #1
int end2 = Math.min(start+2*inc, x1.length); // boundary for run #2
int y = start+inc; // index into run #2 (could be beyond array boundary)
int z = start; // index into the out array
while ((x < end1) && (y < end2))
if (c.compare(x1[x],x1[y]) <= 0) x2[z++] = in[x++];
else x2[z++] = x1[y++];
if (x < end1) // first run didn't finish
System.arraycopy(x1, x, x2, z, end1 - x);
else if (y < end2) // second run didn't finish
System.arraycopy(x1, y, x2, z, end2 - y);
}
}
0

LVL 30

Assisted Solution

Mayank S earned 1000 total points
ID: 16389447
>> int x = start; // index into run #1

Change that to int k = start ; as you already have double[] x as a method argument (same variable-name).

>> while ((x < end1) && (y < end2))

while ( ( k < end1) && ( y < end2 ) )

>> if (c.compare(x1[x],x1[y]) <= 0) x2[z++] = in[x++];

if ( c.compare ( x1[k], x1[k]) <= 0 ) x2[z++] = in[k++];

>> if (x < end1) // first run didn't finish

if ( k < end1 )

>> System.arraycopy(x1, x, x2, z, end1 - x);

System.arraycopy ( x1, k, x2, z, end1 - k ) ;

BTW, what is the x[] needed for?

0

Author Comment

ID: 16392362
Thanks guys! It is compiling. I copied the class below, just to keep track of the current version.
Which x[] are you talking about?
Now, how to proceed from here. The previous classes were in the following relationship:

MyapiA          MyapiB          MyapiC
|                   |                   |
SortA-----------SortB            mergeSort
|
Sort

So, class Sort extends class SortB (Sort was not working, though), SortB extends SortA and implements MyapiB and SortA implements MyapiA. SortA was sorting the array in either increasing, or decreasing order. SortB was creating the ramdon array and calling SortA (printing in the screen, as well). Sort should call SortB. But now, I have to modify those classes to accomodate mergeSort and merge. How should I do that?

public void merge(double[] x1, double[] x2, Comparator c, double[] x) { // merge in[start..start+inc-1] and in[start+inc..start+2*inc-1]
int start = (int)x[0];
int inc = (int)x[1];

int k = start; // index into run #1
int end1 = Math.min(start+inc, x1.length); // boundary for run #1
int end2 = Math.min(start+2*inc, x1.length); // boundary for run #2
int y = start+inc; // index into run #2 (could be beyond array boundary)
int z = start; // index into the out array
while ((k < end1) && (y < end2))
if (c.compare(x1[k],x1[y]) <= 0) x2[z++] = x1[k++];
else x2[z++] = x1[y++];
if (k < end1) // first run didn't finish
System.arraycopy(x1, k, x2, z, end1 - k);
else if (y < end2) // second run didn't finish
System.arraycopy(x1, y, x2, z, end2 - y);
}
0

LVL 30

Expert Comment

ID: 16392517
>> Which x[] are you talking about?

This one: >> public void merge(double[] x1, double[] x2, Comparator c, double[] x) // the double[] x in the end
0

Author Comment

ID: 16393442
Technically, this last double[]x is replacing int start, int inc that were there before. However, the question specifies double[]x instead.
0

LVL 30

Expert Comment

ID: 16398052
Buf effectively - it is not being used in that method?
0

Author Comment

ID: 16400526
Well, that was one of my problems: as the specification requires the use of this double[]x and looks like it replaces the int start and int inc, how to use it, then?
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectioâ€¦
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilationâ€¦
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Booleâ€¦
Viewers will learn one way to get user input in Java. Introduce the Scanner object: Declare the variable that stores the user input: An example prompting the user for input: Methods you need to invoke in order to properly get  user input:
###### Suggested Courses
Course of the Month14 days, 3 hours left to enroll

#### 807 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.