CODEWITHSUNDEEP
javaalgorithmsorting
JDC
JDC

Reputation: 4385

Sort a List by attribute but keep order of same attributes

I have a list that could look like this:

{A[1], A[2], B[1], A[3], B[2], B[3], A[4]}

whereas A,B is an attribute of object in the list.
The numbers indicate the order of the objects related to each other with the same attribute.

Now, I want to sort the list so that I have the following result:

{A[1],A[2],A[3],A[4],B[1],B[2],B[3]}

In concrete, this means the order of the objects related to each other object with the same attribute should stay the same, but the general order should be by the attribute. The problem is that the order related to each other is not determinable by an additional attribute, it is just specified by the order in the root list.

How could I do this?

Upvotes: 1

Views: 791

Answers (4)

MBo
MBo

Reputation: 80287

You may use stable sort algorithm.

Don't know whether Java inbuilt methods use some stable sort (like TimSort). If not, you easily may find Insertion Sort or Merge Sort implementation.

Upvotes: 0

jfcorugedo
jfcorugedo

Reputation: 10059

Just use List.sort method to sort all the elements based on the attribute value.

Elements with same attribute value will remain in the same order they have been inserted.

For instance:

@Test
public void testSortList() {

    List<Element> list = new ArrayList<>();
    list.add(new Element("A", 1));
    list.add(new Element("A", 2));
    list.add(new Element("B", 1));
    list.add(new Element("A", 3));
    list.add(new Element("B", 2));

    list.sort((element1, element2) -> element1.getValue().compareTo(element2.getValue()));

    assertThat(list.get(0).getValue()).isEqualTo("A");
    assertThat(list.get(0).getPosition()).isEqualTo(1);
    assertThat(list.get(1).getValue()).isEqualTo("A");
    assertThat(list.get(1).getPosition()).isEqualTo(2);
    assertThat(list.get(2).getValue()).isEqualTo("A");
    assertThat(list.get(2).getPosition()).isEqualTo(3);
    assertThat(list.get(3).getValue()).isEqualTo("B");
    assertThat(list.get(3).getPosition()).isEqualTo(1);
    assertThat(list.get(4).getValue()).isEqualTo("B");
    assertThat(list.get(4).getPosition()).isEqualTo(2);
}

Where Element class looks as follow:

class Element {

  /** Attribute used to sort the elements */
  private String value;

  /** Attribute used to remember the original position of this element in the list */
  private int position;

  public Element(String value, int position) {
    this.value = value;
    this.position = position;
  }

  public String getValue() {
    return value;
  }

  public int getPosition() {
    return position;
  }

  /** Insert equals and hashCode! */
}

Upvotes: 1

ctst
ctst

Reputation: 1690

I am not sure, if the already implemented method list.sort() maintains your condition, so I would suggest you the simple sort with O(n²) calculations, assuming your compare-method returns 0, if the attribute is the same:

List<T> sortList(List<T> list){
    for(int ind=1; ind<list.size(); ind++){
        for(int indBack=ind; indBack>0; indBack--){
            if(compare(list.get(indBack), list.get(indBack-1))==1){
                T tempSave = list.get(indBack-1);
                list.set(indBack-1, list.get(indBack));
                list.set(indBack, tempSave);
            }
        }
    }
    return list;
}

Upvotes: 0

Matteo Di Napoli
Matteo Di Napoli

Reputation: 577

Just define a new comparator specifying in it your requirements: check if objects have the same attribute, and in that case specify the priority on the base of the position in the rootlist; otherwise, order by the attribute itself. 

Collections.sort(rootlist, new YourComparator());

class YourComparator implements Comparator<YourClass> {
    @Override
    public int compare(YourClass a, YourClass b) {
        if(a.attribute == b.attribute){
            return rootlist.indexOf(a) < rootlist.indexOf(b) ? -1 : rootlist.indexOf(a) == rootlist.indexOf(b) ? 0 : 1;
        }
        else 
            return a.attribute < b.attribute ? -1 : 1;

    }
}

Upvotes: 1

Related Questions