CODEWITHSUNDEEP
javanetbeansarraylistsorting
Alyssa Klein
Alyssa Klein

Reputation: 1

Inserting an object in ascending order with an ArrayList in Java

So I've went back and forth quite a few times trying multiple different methods but I just can't seem to wrap my head around the appropriate algorithm for this method. I am creating a Polynomial class that uses an ArrayList where Term(int coeff, int expo) The coeff is the coefficient of the polynomial and the expo is the exponent. In the test class I have to insert multiple different Term objects but they need to be inserted in ascending order by their exponents (for example, 4x^1 + 2x^3 + x^4 + 5x^7)

This is the code I have up to the end of the insert() method which takes two parameters, the coeff and expo:

public class Polynomial
{

   private ArrayList<Term> polynomials ;

   /**
     * Creates a new Polynomial object with no terms
     */
  public Polynomial()
  {
       polynomials = new ArrayList<>() ;
  }

  /**
    * Inserts a new term into its proper place in a Polynomial
    * @param coeff the coefficient of the new term
    * @param expo the exponent of the new term
    */
   public void insert(int coeff, int expo)
   {

      Term newTerm = new Term (coeff, expo) ; 


      if (polynomials.isEmpty())
      {
          polynomials.add(newTerm);
          return;
      }


      int polySize = polynomials.size() - 1 ;


      for (int i = 0 ; i <= polySize ; i++)
      {
            Term listTerm = polynomials.get(i) ;  
            int listTermExpo = listTerm.getExpo() ;

            if ( expo <= listTermExpo )
            {
                 polynomials.add(i, newTerm);
                 return;
            }

            else if ( expo > listTermExpo )
           {
                 polynomials.add(newTerm) ;
                 return ;
           }

    }

}

The problem arises near the end of the code. Once I put in a Term whose coefficient isn't <= the Term at the index it goes to the else if statement and adds it to the end of the list. Which is wrong, since it needs to be added where it JUST becomes bigger than the next coefficient. Just because it's larger than that coefficient doesn't mean its the LARGEST coefficient. I've tried doing the for statement backwards where:

for (i = polySize ; i >= 0 ; i--)
{
  etc.
}

But that didn't work either since it raises the same issue just the other way around. If anyone could provide some solution or answer it would be much appreciated since I am very confused. At this point I'm sure I'm just making it too complicated. I just want to know how to recognize that the exponent is larger but then go back into the for loop until it is smaller than or equal to the index's exponent.

Also, I should mention, I am not allowed to use any other collection or class, so I must do this using a for, if, else, or do while statement. Thanks in advance!

Upvotes: 0

Views: 1603

Answers (2)

Jan Kebernik
Jan Kebernik

Reputation: 154

This should have the exact behaviour you specified:

public void insert(int coeff, int expo) {
    Term newTerm = new Term(coeff, expo);
    int max = polynomials.size();
    int min = 0;
    int pivot;
    while (max > min) {
        pivot = (min + max) / 2;
        if (expo > polynomials.get(pivot).getExpo()){
            min = pivot + 1;
        }
        else {
            max = pivot;
        }
    }
    polynomials.add(min, newTerm);
}

This algorithm will add new Terms right in front of the first term with the same exponent if any such Term is already in the list.

Upvotes: 0

Patashu
Patashu

Reputation: 21783

Remove this from the for loop:

       else if (expo > listTermExpo)
       {
             polynomials.add(newTerm);
             return;
       }

Place this after the for loop:

polynomials.add(newTerm);
return;

Reasoning: You want to add the term to the end of the list only if it is not less than ANY term in it - not just the first term.

Also, it is good formatting to have the ; immediately after the statement it is for with no space in between, and for ()s to not have any spaces immediately inside them. I've edited the code I copied from you to show what I mean.

Upvotes: 1

Related Questions