CODEWITHSUNDEEP
java
pro
pro

Reputation: 75

How to sort an arraylist of numbers depending on size?

Edit: I should have specified that I can't use the built in sort algorithm for this.

I have an arraylist of rational numbers and I want to sort it by adding the numbers in order of highest to lowest into a new arraylist. At the moment my output is just the first rational number of the arraylist. What am I doing wrong and how can I get it to work?

public static Collection<Rational> sort(List<Rational> list){
    List<Rational> sortedList = new ArrayList<Rational>();

    for (Iterator<Rational> it = list.iterator(); it.hasNext(); ) {
        Rational currentValue = it.next();

        // Look into sortedList the position where currentValue should go into
        Rational pos = null;
        for (int i=0;i<sortedList.size();i++) { 
             // Compare currentValue with sortedList.get(i) 
             // to know if i is the right position for currentValue. 
             // If it is, assign it to pos
            if(currentValue.compareTo(sortedList.get(i)) > 0){
                pos = (sortedList.get(i));
            }
            else if((currentValue.compareTo(sortedList.get(i)) == 0)){
                pos = (sortedList.get(i));
            }
            else if(currentValue.compareTo(sortedList.get(i)) < 0){
                pos = (sortedList.get(i));
            }
         }
         sortedList.add(pos);
     }
     return sortedList;
}

Upvotes: 2

Views: 498

Answers (5)

Andy Senn
Andy Senn

Reputation: 649

Create your own Comparator implementation. In this manner, you can define any number of comparators if your sorting needs change depending on context.

public static Comparator<Rational> comparator = new Comparator<Rational>() {
    @Override
    public int compare ( Rational o1, Rational o2 ) {
        // Sort logic here
    }
};

public static Collection<Rational> sort( List<Rational> list ) {
    List<Rational> sortedList = new ArrayList<Rational>(list);
    Collections.sort( sortedList, comparator );
    return sortedList;
}

Upvotes: 0

Michikawa
Michikawa

Reputation: 123

Edit: corrected i to j in inner loop

The previous answers provide "the best" way to go about this. However, if you'd like to know how to fix your original take on the problem, here's a way to make your original code work like you wanted it to work. I also changed the iterator to index syntax so that both lists are handled the same way for more readable code. Other way to go about this would have been to make also sortedList use iterator. If you'd change the comparison > 0 to comparison < 0, you'd get reverse order.

public static Collection<Rational> sort(List<Rational> list){
  List<Rational> sortedList = new ArrayList<Rational>();

  for (int i=0;i < rationalList.size();i++) {
     Rational currentValue = rationalList.get(i);

     int pos = sortedList.size(); // default is to the end of the list
     for (int j=0;j<sortedList.size();j++) {
        int comparison = currentValue.compareTo(sortedList.get(j))
        //this is the right position if the currentValue is greater or equal 
        //to the sorted value at this position
        if(comparison > 0 || comparison == 0){
           pos = j;
           break;
        }
     }
     sortedList.add(pos, currentValue);
  }
  return sortedList;
}

The problems with your original code were:

1) You weren't looking for the int index value of the right position, you had Rational position, which feels a bit weird 2) In your sortedList check phase, you called pos = (sortedList.get(i)); no matter what the comparison was 3) You added the value of pos itself to the sortedList: sortedList.add(pos);

So the corrections were:

1) We are looking for the int index value of the right position in the current sortedList 2) We are only interested in the position, where the new value is either greater or equal to the current sorted value at that position 3) We put the currentValue into the sortedList only to the specific index that we found by comparison. Default position is at the end.

Upvotes: 0

fge
fge

Reputation: 121712

Using tools available in the JDK, this is what you can do:

private static final Comparator<Rational> INVERSE_RATIONAL
    = new Comparator<Rational>()
    {
        @Override
        public int compare(final Rational a, final Rational b)
        {
            return b.compareTo(a);
        }
    }

// ...

public static Collection<Rational> sort(final List<Rational> list)
{
    // Note: supposes Java 7
    final List<Rational> ret = new ArrayList<>(ret);
    Collections.sort(ret, INVERSE_RATIONAL);
    return ret;
}

EDIT @Makoto rightly points to Collections.reverse(), which makes the above code even more simple:

// No need for a custom Comparator...
public static Collection<Rational> sort(final List<Rational> list)
{
    // Note: supposes Java 7
    final List<Rational> ret = new ArrayList<>(ret);
    Collections.sort(ret);
    Collections.reverse(ret);
    return ret;
}

Upvotes: 1

ug_
ug_

Reputation: 11440

You should use Collections.sort as its fast, efficient and you can count on it not having bugs. Your code has some bugs, take this line for instance:

// Look into sortedList the position where currentValue should go into
Rational pos = null;

Here you say its the position which is correct but you have a Rational Object where you should have an int value. For an insertion sort you need to go through the list until you find the correct spot to place the object. So here we go through the list until we find a good position for the object, then we add that object at the position.

Your inner loop should look like this:

// Look into sortedList the position where currentValue should go into
int pos = 0;
for (int i=0;i<sortedList.size();i++) { 
     // Compare currentValue with sortedList.get(i) 
     // to know if i is the right position for currentValue. 
     // If it is, assign it to pos
    if(currentValue.compareTo(sortedList.get(i)) > 0) {
        // For lowest to highest sort, uncomment this
        //pos = i+1;
    }
    else if((currentValue.compareTo(sortedList.get(i)) == 0)){
        pos = i;
    }
    else if(currentValue.compareTo(sortedList.get(i)) < 0){
        // For highest to lowest.
        pos = i+1;
    }
 }
 sortedList.add(pos, currentValue);

There are better ways to write this code but I left it as close to what you had as possible.

Upvotes: 0

Makoto
Makoto

Reputation: 106390

Since your elements appear to be Comparable, you can do two things:

  • Use Collections.sort to sort them in ascending order (lowest to highest),
  • Then use Collections.reverse to reverse the order.

Both of these operations modify the list in place. If this is undesirable, copy the contents of the list to an intermediate list and modify that.

Collections.sort(sortedList);
Collections.reverse(sortedList);

You could copy the contents to an intermediate list, and mutate that as well:

List<Rational> sortedList = new ArrayList<Rational>();
for(Rational rational : list) {
    sortedList.add(rational);
}
Collections.sort(sortedList);
Collections.reverse(sortedList);

Upvotes: 1

Related Questions