Sort list with help of index

Question

Can I access the index of the object in the list somehow?

myList.stream().sorted((o1, o2) -> 0).collect(Collectors.toList())

e.g.:

I'd like odd indices to be displayed first and even indices at the end.

Answer 1

I wouldn’t consider index based reordering operations to be actual sorting operations. E.g., no-one would consider implementing an operation like Collections.reverse(List) as a sorting operation.

An efficient method for moving elements at odd positions to the front in-place would be

public static <T> void oddFirst(List<T> list) {
    final int size = list.size();
    for(int index1=0, index2=list.size()/2|1; index2<size; index1+=2, index2+=2)
        Collections.swap(list, index1, index2);
}

Alternatively, you may stream over the indices like in this answer, to generate a new List.

Answer 2

A filter may help:

List<Integer> listEvenIndicesMembers = IntStream.range(0, list.size()).filter(n -> n % 2 == 0).mapToObj(list::get)
            .collect(Collectors.toList());
List<Integer> listOddIndicesMembers = IntStream.range(0, list.size()).filter(n -> n % 2 != 0).mapToObj(list::get)
            .collect(Collectors.toList());
System.out.println(listEvenIndicesMembers);
System.out.println(listOddIndicesMembers);

[1, 3, 5, 7, 9, 11]

[2, 4, 6, 8, 10]

the problem is now you have 2 lists, appending one after the other will produce the same you want... am still checking the doc maybe I find something more elegant/optimized.

Edit:

Thanks to @Holger for the neat suggestion:

you can concatenate the streams doing:

List<Integer> listOptimal = IntStream
            .concat(IntStream.range(0, list.size()).filter(n -> n % 2 == 0),
                    IntStream.range(0, list.size()).filter(n -> n % 2 != 0))
            .mapToObj(list::get).collect(Collectors.toList());
System.out.println(listOptimal);

Answer 3

I think solution of ΦXocę 웃 Пepeúpa ツ should be fine for you, here's just an alternative (remember, it's just an alternative for the sake of learning, this solution should not be used in 'real life', it's just to show the possibility):

public static void main(String arg[]) {
  List<String> list = Arrays.asList("A", "B", "C", "D", "E", "F", "G", "H");
  List<String> listCopy = new ArrayList<>(list);

  list.sort((o1, o2) -> Integer.compare(listCopy.indexOf(o2) % 2, listCopy.indexOf(o1) % 2));

  System.out.println(list);
}

Output is: [B, D, F, H, A, C, E, G]

Answer 4

The accepted answer works, but this works too (as long as there are no duplicates in the list):

// a list to test with
List<String> list = Arrays.asList("abcdefghijklmnopqrstuvwxyz".split(""));

List<String> list2 = list.stream()
   .sorted(Comparator.comparing(x -> list.indexOf(x) % 2).thenComparing(x -> list.indexOf(x)))
   .collect(Collectors.toList());
list2.forEach(System.out::print);

This prints odd indices first, then the even indices

acegikmoqsuwybdfhjlnprtvxz

---

Just to illustrate the point Holger made in his comment.

• The solution in this answer took my machine 75 ms to run.
• The solution in this answer took only 3 ms.
• And Holger's own answer ends up with an astonishing < 0 ms.

Answer 5

You may use the decorator pattern to store your objects plus extra information for sorting. E.g. if you have a list of strings you want to sort (add getters):

class StringWithIndex {
    String text;
    int index;
    int evenIndex;

    StringWithIndex(String text, int index) {
        this.text = text;
        this.index = index;
        this.evenIndex = index % 2 == 0 ? 1 : -1;
    }
}

And then you can sort such objects instead of strings:

List<String> strings = Arrays.asList("a", "b", "c", "d");

List<String> sorted = IntStream.range(0, strings.size())
        .mapToObj(i -> new StringWithIndex(strings.get(i), i))
        .sorted(comparingInt(StringWithIndex::getEvenIndex).thenComparingInt(StringWithIndex::getIndex))
        .map(StringWithIndex::getText)
        .collect(Collectors.toList());

This adds some overhead to create temporary objects and requires another class. But it can prove very useful as the sorting rules become more complicated.

Answer 6

If all you want to do is move List values around according to their index, then see my other answer.

However, the original wording of your question suggests you want to use sort() or sorted() with a comparator that takes existing position into account as well as other aspects of the value.

This would also be difficult if you just used Collections.sort(), because the Comparator used there doesn't have access to the index either.

You could map your Stream<T> to a Stream<Entry<Integer,T>> and perhaps map it back to Stream<T> when you've finished:

(This is AbstractMap.SimpleEntry -- because it exists in the standard libs -- you could also write your own Pair or use one from a 3rd party -- see A Java collection of value pairs? (tuples?) )

mystream.map(addIndex()).sorted(compareEntry()).map(stripIndex()) ...

private <T> Function<T,Entry<Integer,T>> addIndex() {
    final int[] index = new int[] { 0 };
    return o -> new SimpleEntry(index[0]++, o);    
}

private Comparator<Entry<Integer, T>> compareEntry() {
    return a,b -> {
       // your comparison code here -- you have access to
       // getKey() and getValue() for both parameters
    };
}

private <T> Function<Entry<Integer,T>, T> stripIndex() {
    return e -> e.getValue();
}

Note that addIndex(), at least, is not parallelisable. I suppose that once all the entries are tagged with indices, downstream from there things could be done in parallel.

Answer 7

Bonus answer - if all you want to do is create a new List containing the odd entries followed by the even entries, then using Stream is adding needless complexity.

 for(int i=0; i<inlist.size(); i+=2) {
     outlist.add(inlist.get(i));
 }
 for(int i=1; i<inlist.size(); i+=2) {
     outlist.add(inlist.get(i));
 }

There's also a pretty simple algorithm what will re-order the list in-place -- which you can write for yourself. Think about it -- there's a simple function to get the new index from the old index, as long as you know the list length.