How to merge two sorted arrays in Java?

Question

I'm trying to create a third sorted array, c, from the two previously created arrays, a and b; however, I'm getting several errors within the merge method that say "The type of the expression must be an array type but it resolved to OrdArray". I've been at it for hours already, and feel like my brain is mush now. Can someone help me out?

class OrdArray
{
    private long[] a;                 // ref to array a 
    private int nElems;               // number of data items
    //-----------------------------------------------------------
    public OrdArray(int max)          // constructor
    {
        a = new long[max];             // create array a  
        nElems = 0;
    }
    //-----------------------------------------------------------
    public int size()
    { return nElems; }
    //-----------------------------------------------------------
    public int find(long searchKey)
    {
        int lowerBound = 0;
        int upperBound = nElems-1;
        int curIn;

        while (true)
        {
            curIn = (lowerBound + upperBound ) / 2;
            if (a[curIn] == searchKey)
                return curIn;              // found it
            else if (lowerBound > upperBound)
                return nElems;             // can't find it
            else                          // divide range
            {
                if (a[curIn] < searchKey)
                    lowerBound = curIn + 1; // it's in upper half
                else
                    upperBound = curIn - 1; // it's in lower half
            }  // end else divide range
        }  // end while

    }  // end find()
    //-----------------------------------------------------------
    public void insert(long value)    // put element into array
    {
    int j;
    for (j = 0; j < nElems; j++)        // find where it goes
        if (a[j] > value)            // (linear search)
            break;
        for (int k = nElems; k > j; k--)    // move bigger ones up
            a[k] = a[k-1];
        a[j] = value;                  // insert it
        nElems++;                      // increment size
    }  // end insert()
    //-----------------------------------------------------------
    public boolean delete(long value)
    {
        int j = find(value);
        if (j == nElems)                  // can't find it
            return false;
        else                           // found it
        {
            for (int k = j; k < nElems; k++) // move bigger ones down
                a[k] = a[k+1];
            nElems--;                   // decrement size
            return true;
        }
    }  // end delete()
    //-----------------------------------------------------------
    public void display()             // displays array contents
    {
        for (int j = 0; j < nElems; j++)       // for each element,
            System.out.print(a[j] + " ");  // display it
        System.out.println("");
    }
    //-----------------------------------------------------------
    public static long[] merge(OrdArray a, OrdArray b) 
    {

    long[] c = new long[a.nElems + b.nElems];
    int i = 0, j = 0, k = 0;

    while (i < a.nElems && j < b.nElems)
    {
        if (a.data[i] < b.data[j])     
            c[k++] = a.data[i++]; 
        else        
            c[k++] = b.data[j++];              
    }

    while (i < a.nElems)  
        c[k++] = a.data[i++];      

    while (j < b.nElems)    
        c[k++] = b.data[j++]; 
    return c;
    }
    }  // end class OrdArray
    ////////////////////////////////////////////////////////////////
  class OrderedApp
  {
      public static void main(String[] args)
      {
      int maxSize = 100;             // array size
      OrdArray a, b, c;                  // reference to array
      a = new OrdArray(maxSize);   // create the array
      b = new OrdArray(maxSize);
      c = new OrdArray(maxSize);

      a.insert(11);
      a.insert(13);
      a.insert(15);
      a.insert(17);
      a.insert(19);
      a.insert(21);
      a.insert(23);
      a.insert(25);
      a.insert(27);
      a.insert(29);

      b.insert(12);
      b.insert(14);
      b.insert(16);
      b.insert(18);
      b.insert(20);
      b.insert(32);
      b.insert(24);
      b.insert(26);
      b.insert(28);
      b.insert(30);

      OrdArray.merge(a,b);

      System.out.print("Array a: ");
      a.display();
      System.out.println();
      System.out.print("Array b: ");
      b.display();
      System.out.println();
      System.out.print("Array c: ");
      c.display();
      System.out.println();
      }  // end main()
  }// end class OrderedApp

Could you please mark the line(s) where you got the error? (Edit the source and put a comment on the problem line(s). Don't tell us the line number included in the error message, because we won't be able to figure out which line that is.) — ajb
– ajb, Commented Sep 8, 2015 at 3:38
Hi @Rainwater. My aproach looks similar to yours. Are you preparing from Robert Lafore's book? See my answer. Thanks. I am confused why you are using binary search. Simple way is to insert two arrays using two insert methods or one. Using a merge method, just merge those two already sorted arrays by comparing the least element among two sorted arrays. — user4398985
– user4398985, Commented Sep 8, 2015 at 7:00

ajb · Accepted Answer · 2015-09-08 04:01:27Z

1

OrdArray is not an array type (despite the name); therefore, you can't index it like an array. This expression

a[i++]

where a is an OrdArray, will have no meaning. Java doesn't give you a way to define your own [] operator for classes (unlike C++). Therefore, you'll have to add a method to OrdArray to return the element at a given index, something like

public long get(int index) { ...write the code... }

a.get(i++) // will then get the element at that index

Although I'm not sure this is what you want, since you've declared c to be an int[] and the array in OrdArray to be a long[], so I'm not sure what you're trying to do.

EDIT: After reading your comment, I realized that the merge method is inside the OrdArray class. I missed that before. Since that's the case, you don't need to add a get method; you can access the private fields of your OrdArray parameters directly. In your method:

public void merge(OrdArray a, OrdArray b)

you want to get at the private array a that you declare for each OrdArray. If you just use a, the variable will refer to the OrdArray, which isn't an array (as described above); to get at the long[] a belonging to the OrdArray a, you need to say

a.a[i++]

and likewise, for b,

b.a[i++]

This can look confusing to a reader, so I suggest coming up with a better name so that you're not calling two things a. Perhaps data?

A couple other things: You use merge like this: c.merge(a,b), which means that merge is an instance method and c is the instance you're operating on. But your method doesn't do anything with the current instance. (The c you declare in merge is a local variable that has nothing to do with the c you use when calling merge.) Right now, your method is going to a lot of trouble to construct the local array c, but then it just throws it away. You either need to (1) fix the method so that it sets up the a (or data) array in the current instance; or (2) make it a static method and make the method return the new array as a function result. I'm not sure which one your instructor wants you to do.

edited Sep 8, 2015 at 4:01

answered Sep 8, 2015 at 3:42

ajb

31.8k4 gold badges63 silver badges86 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Tangwheeler Over a year ago

c should actually be a long[]. I was tinkering around and forgot to change it back. I don't believe our instructor wanted us to make any methods other than the merge method. Your way of using get makes plenty of sense to me, but as I said, I don't think he wants us to do that.

Tangwheeler Over a year ago

I updated it with some of the changes you suggested, and I'm error free now! The problem is that it isn't returning anything for c.display();. I'm getting really confused with this, so please bear with me. I also changed it to OrdArray.merge because it suggested the fix when I changed the method to static. I'm sure that isn't right, but like I said, I'm getting rather confused at this point.

ajb Over a year ago

If you can't figure it out on your own, you'll probably need to post this as a new question, with the latest version of your source (hopefully trimmed dwon to the smallest piece of code that demonstrates the problem). StackOverflow is organized in a question-and-answer format, not as a running discussion.

Karthik R · Accepted Answer · 2015-09-08 04:14:33Z

I'm not exactly sure what you are trying to do. But to resolve error, i have corrected the articular block.

To note, OrdArray class is not an array. It's a class that has a long[] a. So you need to get the array like any other property from the object.

For betterment, please change the method signature like this:

public void merge(OrdArray ordArr1, OrdArray ordArr2) {//Note parameters' name change
.
.
.

while (i < ordArr1.nElems && j < ordArr2.nElems)
  {
      if (ordArr1.a[i] < ordArr2.a[j])      //should resolve
          c[k++] = ordArr1.a[i++]; 
      else        
          c[k++] = ordArr2.a[j++];              
  }

  while (i < a.nElems)  
      c[k++] = ordArr1.a[i++];      

  while (j < b.nElems)    
      c[k++] = ordArr2.a[j++]; 
  }

Marcin Szymczak · Accepted Answer · 2015-09-08 06:43:22Z

0

If you accept solution wit Lists it would be:

List<Integer> result = new ArrayList<Integer>(Arrays.asList(sourceArray));
result.addAll(Arrays.asList(secondSourceArray));
Collections.sort(result);

You can optionally convert it back to array with

result.toArray();

answered Sep 8, 2015 at 6:43

Marcin Szymczak

11.5k5 gold badges58 silver badges65 bronze badges

Comments

score 0 · Accepted Answer · 2015-09-08 06:58:57Z

I am confused why you are using binary search. Simple way is to insert two arrays using two insert methods or one. Using a merge method, just merge those two already sorted arrays by comparing the least element among two sorted arrays.

Remove delete, search etc methods, they are not required.

This is my code. I have inserted two integer arrays(elements) into inserta() and insertb() sorted them and merged them using insert() method. Finally I have this sorted array after merging them. Please see my code here:

    package sample;

/**
 *
 * @author Shivasai
 */
public class Merge {
    int i;
    int j;
    int k;
    int n;
    int m;
    int p;
    private long[] a;
    private long[] b;
    private long[] c;
    public Merge()
    {
        a=new long[10];
        b=new long[10];
        c=new long[100];
        n=0;
        m=0;
        p=0;
    }
    void inserta(long key)
    {
      for(i=0;i<n;i++)
      {
          if(a[i]>key)
              break;
      }
      for(j=n;j>i;j--)
      {
          a[j]=a[j-1];

      }
      a[j]=key;
      n++;

    }
    void insertb(long value)
    {
      for(i=0;i<m;i++)
      {
          if(b[i]>value)
              break;
      }
      for(j=m;j>i;j--)
      {
          b[j]=b[j-1];

      }
      b[j]=value;
      m++;

    }
    void insert()
    {
        i=0;
        j=0;

        while(i>n || j<m)
        {
            if(a[j]<b[i])
            {
                c[p]=a[j];
                j++;
            p++;
            }
            else
            {
                c[p]=b[i];
                i++;
                p++;
            }


        }



    }
    void displaya()
    {
        for(k=0;k<10;k++)
        {
            System.out.print("," +a[k]);
        }
        System.out.println();

    }
    void displayb()
    {
        for(k=0;k<10;k++)
        {
            System.out.print("," +b[k]);
        }
        System.out.println();

    }
    void displayc()
    {
        for(k=0;k<20;k++)
        {
            System.out.print("," +c[k]);
        }
    }
    public static void main(String[] args)
    {
        Merge obj = new Merge();
        obj.inserta(25);
                                    obj.inserta(12);
                                    obj.inserta(1800);
                                    obj.inserta(9);
                                    obj.inserta(10);
                                    obj.inserta(15);
                                    obj.inserta(18);
                                    obj.inserta(19);
                                    obj.inserta(0);
                                    obj.inserta(1500);
                                    obj.insertb(36);
                                    obj.displaya();
                                    obj.insertb(2);
                                    obj.insertb(3);
                                    obj.insertb(2000);
                                    obj.insertb(5);
                                    obj.insertb(6);
                                    obj.insertb(7);
                                    obj.insertb(8);
                                    obj.insertb(21);
                                    obj.insertb(85);
                                    obj.displayb();
                                    obj.insert();
                                    obj.displayc();


    }


}

Collectives™ on Stack Overflow

How to merge two sorted arrays in Java?

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related