Sorting array list in Java

Question

I have following class. In this, Iris is another class with some attributes.

public class Helper {
 Iris iris;
 double distance;
 public Helper(Iris iris, double distance) {
 this.iris = iris;
 this.distance = distance;
 }
}

I want to sort an array list of this (i.e List < Helper> helperList), descending based on distance parameter. I have written the following method but it is not working.

public void sort(){
for(int k=0; k < helperList.size(); k++)
 {
 double distance = helperList.get(k).distance; 
 for(int l=0; l < helperList.size(); l++)
 {
 Helper temp = helperList.get(l);
 if( distance < temp.distance )
 {
 helperList.set(l, helperList.get(k));
 helperList.set(k, temp);
 }
 }
 }
}

Can anybody suggest a solution?

• Michael Petrotta: In what way is it not working?
• Ammar: It is not sorting the list properly.
• Daniel Fischer: Consider what happens with two elements, say [1,2]. for k = 0, l = 1, because list.get(1) > 1, you swap, giving [2,1]. Then for k = 1, l = 0 you swap again. You should compare each element only to those on one side of it.
• Ammar: @Daniel Fischer ! In my case the list consists of 120 elements. More than half of the starting elements are sorted correctly but some at the ending aren't. I couldn't understand this behavior.
• Daniel Fischer: It's because you're swapping back and forth. I haven't analyzed, perhaps if you start the inner loop at k+1 instead of 0 it works. However, the proper way would be to create a Comparator meeting your needs and use a library sort. Or implement one of the classical sorting algorithms.

Answer 1

Why don't you get your Helper class to implement Comparable interface and then use the in-built sort method offered by the Collections class.

Collections.sort(helperList) 

I think that would solve the problem. Plus, this sort method is stable.

http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#sort%28java.util.List%29

http://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html

Implementing Comparable interface:

public class Helper implements Comparable{
 Iris iris;
 double distance;
 public Helper(Iris iris, double distance) {
 this.iris = iris;
 this.distance = distance;
 }
 public int compareTo(Helper other) {
 return new Double(this.distance).compareTo(new Double(other.distance));
 }
}

• jackrabbit: If the two distances are less than 1 apart, this compareTo implementation will return 0 (if you would cast correctly). return this.distance < other.distance ? -1 : this.distance > other.distance ? 1 : 0
• Ammar: It works. Thanx to all and specially to @Divya for her suggestion.
• jackrabbit: Why would you create 2 Double objects every time you do a comparison? And even if you want to, use Double.valueOf().
• COD3BOY: When you add link to javadoc, try to include the latest one :)

Answer 2

Divya's answer is good, but if you don't want to implement Comparable interface, following might be help:

Collections.sort(helperList, new Comparator<Helper>() {
 public int compare(Helper helper1, Helper helper2) {
 return Double.compare(helper1.distance, helper2.distance);
 }
})

• Divya: helper1.distance - helper2.distance gives a double and not an int. I made the same mistake.

Answer 3

The problem is that the loop looses track of where the distance index is located after it has been swapped. This algorithm should work fine.

 for(int k = 1; k < helperList.size(); k++) {
 double distance = helperList.get(k).distance;
 int j = k - 1;
 boolean done = false;
 while(!done) {
 Helper temp = helperList.get(j);
 if(temp.distance < distance) {
 helperList.set(j+1, temp);
 j = j - 1;
 if(j < 0) {
 done = true;
 }
 } else {
 done = true;
 }
 helperList.set(j+1, value);
 }
}

• Ammar: Thanx Shawn. I used Collections.sort(object) as suggested by Divya and it works fine.

Answer 4

The article on bubble sort on Wikipedia contains pseudo code and also some optimized versions. Compare with that one to see where you are going wrong.

Bubble sort is one of the most obvious sorting algorithms, but not exactly the most efficient. Why don't you let the platform do the sort? java.util.Collections contains a sort method that lets you supply your own Comparator. All that comparator has to do is decide which of two Helper instances should come first.