CODEWITHSUNDEEP
javasortingcollectionsarraylist
Klausos Klausos
Klausos Klausos

Reputation: 16050

Initial indexes of sorted elements of ArrayList

The following code implements sorting of nfit in ascending order.

public static void main(String[] args) {
    ArrayList<Double> nfit = new ArrayList<Double>();

    nfit.add(2.0);
    nfit.add(5.0);
    nfit.add(1.0);
    nfit.add(8.0);
    nfit.add(3.0);

    // Sort individuals in ascending order
    Collections.sort(nfit);

    System.out.print(nfit);

}

The output is:

[1.0, 2.0, 3.0, 5.0, 8.0]

My question is how to get initial indexes of sorted elements? In this example the answer to my question would be the following:

[2, 0, 4, 1, 3]

How can I get these indexes?

Upvotes: 5

Views: 8674

Answers (7)

Usmani Adnan
Usmani Adnan

Reputation: 1

If your list have duplicate values below code will work to get index of initial list

public static void main(String[] args) {
    ArrayList<Double> arr = new ArrayList<>(Arrays.asList(1.0, 2.0, 3.0, 1.0, 2.0, 5.0, 8.0));
    ArrayList<Double> arrr = new ArrayList<>(arr);
    int[] index = new int[arr.size()];

    Collections.sort(arrr);
    final double min = Double.MIN_VALUE;
    System.out.println(arr);
    System.out.println(arrr);

    for (int i = 0; i < arr.size(); i++) {
      index[i] = arr.indexOf(arrr.get(i));
      arr.set(arr.indexOf(arrr.get(i)), min);
      System.out.print(index[i] + " ");
    }
  }

Output on console:

[1.0, 2.0, 3.0, 1.0, 2.0, 5.0, 8.0]
[1.0, 1.0, 2.0, 2.0, 3.0, 5.0, 8.0]
0 3 1 4 2 5 6

Upvotes: 0

Justin
Justin

Reputation: 25337

Copy the ArrayList and sort, then use indexOf.

ArrayList<Double> nfit = new ArrayList<Double>();
nfit.add(2.0);
nfit.add(5.0);
nfit.add(1.0);
nfit.add(8.0);
nfit.add(3.0);
ArrayList<Double> nstore = new ArrayList<Double>(nfit); // may need to be new ArrayList(nfit)
Collections.sort(nfit);
int[] indexes = new int[nfit.size()];
for (int n = 0; n < nfit.size(); n++){
    indexes[n] = nstore.indexOf(nfit.get(n));
}
System.out.println(Arrays.toString(indexes));

If you wanted the indexes in an ArrayList,

Collections.sort(nstore);
for (int n = 0; n < nfit.size(); n++){
    nstore.add(n, nfit.indexOf(nstore.remove(n)));
}
Collections.sort(nfit);

That will result in one sorted ArrayList nfit, and one ArrayList of indexes nstore.

Edited: In the for loop 

for (int n = 0; n < nfit.size(); nfit++){
    nstore.add(n, nfit.indexOf(nstore.remove(n)));
}

The loop count must be iterated over n and not on nfit Find the corrected code:

for (int n = 0; n < nfit.size(); n++){
    nstore.add(n, nfit.indexOf(nstore.remove(n)));
}

Upvotes: 4

hmofrad
hmofrad

Reputation: 1912

Bubble sort is always your friend. You can use it to sort the array and at the same time keep track of original array indices. It will also work when you have multiple similar elements in your array.

import java.util.*;
import java.util.Arrays;
import java.util.Random;
public class BubbleSort {
    public static void main(String[] args) {
        Random rnd = new Random();
        int count = 5;
        ArrayList<Double> array = new ArrayList<Double>();
        int[] indices = new int[count];
        for(int i = 0; i < indices.length; i++) {
            array.add(rnd.nextDouble() * count);
            indices[i] = i;
        }
        ArrayList<Double> values = new ArrayList<Double>(array);
        bubbleSort(values, indices);
        System.out.println("Unsorted input array   :" + array);
        System.out.print("Sorted   input array   : ");
        for(int i = 0; i < array.size(); i++) {
            System.out.print(array.get(indices[i]) + " " );
        }
        System.out.println();
    }
    private static void bubbleSort(ArrayList<Double> values, int[] indices) {
        for(int k = 0; k < values.size(); k++) {
            for(int l = k + 1; l < values.size(); l++) {
                if(values.get(k) > values.get(l)) {
                    double temp_value = values.get(k);
                    values.set(k, values.get(l));
                    values.set(l, temp_value);
                    int temp_index = indices[k];
                    indices[k] = indices[l];
                    indices[l] = temp_index;
                }
            }
        }
    }
}

The reason I answered this question after this many years is that the accepted answer will fail if you have multiple elements with similar values because in indexes[n] = nstore.indexOf(nfit.get(n));, indexOf method is always returning the first occurrence of the specified element which results in an incorrect indices array while having similar elements in the input array.

Last, copy and paste the code in BubbleSort.java and then run javac BubbleSort.java && java BubbleSort to compile and see the results.

Upvotes: 0

user36536
user36536

Reputation: 1

The following implementation of mergesort implements a method 'indexSort' that does just that without messing with the input array. http://algs4.cs.princeton.edu/22mergesort/Merge.java.html http://algs4.cs.princeton.edu/code/javadoc/Merge.html#indexSort(java.lang.Comparable[])

Upvotes: 0

hamid
hamid

Reputation: 2079

Make a copy of theArrayList then sort the copy. After that use indexOf method passing element of sorted array and invoking on original ArrayList.

Upvotes: 1

WPrecht
WPrecht

Reputation: 1382

Two solutions: 1) if you are wedded to ArrayList, you'll need to use an Iterator to build the index list of the solution set. 2) Switch to a Map with the value and the order (which can be changed by sorting).

Upvotes: 0

BobTheBuilder
BobTheBuilder

Reputation: 19294

If the values are unique, you can use a Map<Double, Integer> to hold the value and initial order. You just need to sort the map keys and get the correspond value of each key.

Upvotes: 1

Related Questions