?
Solved

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

Posted on 2006-04-05
14
Medium Priority
?
621 Views
Last Modified: 2013-11-23
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) {
            // TODO: Add your code here
            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) {
            // TODO: Add your code here
            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
Comment
Question by:EDTW
  • 6
  • 3
  • 3
12 Comments
 
LVL 14

Expert Comment

by:StillUnAware
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

by:EDTW
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

by:
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 

Author Comment

by:EDTW
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

by:StillUnAware
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

by:EDTW
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

by:Mayank S
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

by:EDTW
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

by:Mayank S
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

by:EDTW
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

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

Author Comment

by:EDTW
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

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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.

Join & Ask a Question