Sort an Integer Array and Store result with its index in Java

Question

hello guys i need to sort some elements of integer in an integer array and need to store the index of the sorted list

assume if the elements in array are

x[]= {10,20,40,70,80,50,30};

i need to get the index of the sorted order say in this case i need to get 4,3,5,2,6,0 (ascending) (array x starting from 0)

Maybe you can find the answer in this post: http://stackoverflow.com/questions/951848/java-array-sort-quick-way-to-get-a-sorted-list-of-indices-of-an-array — dexametason, Mar 30 '12 at 08:02

score 4 · Answer 1 · answered Mar 30 '12 at 08:05

A simple way (not algorithmically clever) would be to make a new list (or array) of objects from the existing list that contains the value and the index:

class ValueAndIndex implements Comparable<ValueAndIndex> {
    final int value;
    final int index;

    ValueAndIndex(int value, int index) {
        this.value = value;
        this.index = index;
    }

    @Override public int compareTo(ValueAndIndex other) {
       // compare on value;
        if (this.value < other.value) {
            return -1;
        } else if (this.value > other.value) {
            return 1;
        } else {
            return 0;
        }
    }
}

Now, create instances of this class in a list:

List<ValueAndIndex> secondaryList = new ArrayList<ValueAndIndex>(x.length);
for (int i = 0; i < x.length; ++i) {
    secondaryList.add(new ValueAndIndex(x[i], i));
}

Sort this list:

Collections.sort(secondaryList);

Now, the indices are still in this list:

int [] indexesInSortedOrder = new int[x.length];
for (int i = 0; i < secondaryList.size(); ++i) {
    indexesInSortedOrder[i] = secondaryList.get(i).index;
}

System.out.println(Arrays.toString(indexesInSortedOrder));

score 0 · Answer 2 · edited Jul 22 '18 at 17:48

public Map sortDecendingDFSGlobal() {
    Map<String, Object> multiValues = new HashMap<String, Object>();

    double[] dfs = this.global_dfs;
    int[] index = new int[dfs.length];

    for (int i = 0; i < dfs.length; i++) {
        index[i] = i;//for required indexing
    }
    for (int i = 0; i < dfs.length; i++) {
        //sorting dfsglobal in decending order
        double temp = dfs[i];
        double swap = dfs[i];
        int swapIndex = i;

        //keeping track of changing indexing during sorting of dfsglobal
        int indStart = index[i];
        int indSwap = index[i];
        int number = i;
        for (int j = i; j < dfs.length; j++) {
            if (temp < dfs[j]) {
                temp = dfs[j];
                swapIndex = j;

                indSwap = index[j];
                number = j;
            }
        }
        dfs[i] = temp;
        dfs[swapIndex] = swap;

        index[i] = indSwap;
        index[number] = indStart;
    }
    //again sorting the index matrix for exact indexing
    for (int i = 0; i < index.length - 1; i++) {
       for(int j = i; j < index.length - 1; j++ )
       {               

           if(dfs[j] == dfs[j + 1] && index[j] > index[j + 1])
           {
               int temp = index[j];
               index[j] = index[j+1];
               index[j + 1] = temp;
           }
       }
    }

    this.sortedDFS = dfs;
    this.arrIndex = index;

    multiValues.put("sorted", dfs);
    multiValues.put("index", index);
    return multiValues;
} //SortedDecendingDFSGlobal()

score 0 · Answer 3 · answered Mar 30 '12 at 08:00

0

you can create an array

y[] = {0,1,2,3,4,5,6};

And ith any sorting algorithm, when you switching moving two elements in array x, do the same in array y

answered Mar 30 '12 at 08:00

Alex Stybaev

4,623
3
30
44

score 0 · Accepted Answer · answered Mar 30 '12 at 08:06

0

Possible solution

 //sort the array intio a new array
 y[] = x;
 Arrays.sort(y); //sort ascending

 //final array of indexes
 int index_array[] = new int[7];

 //iteretate on x arrat
 for(int i=0; i<7; i++)
    //search the position of a value of the original x array into the sorted y array, store the position in the index array
    index_array[i] = arrays.binarySearch(x,y[i]);

answered Mar 30 '12 at 08:06

ab_dev86

1,952
16
21

1

This shouldn't be an accepted solution, it will fail for duplicate values and why limit only to the example array with length 7? – quinestor Jul 19 '13 at 09:37
This solution will not work. 1) Since both x and y point to same memory location, both will point to sorted array after calling Arrays.sorting. 2) Lets assume array x is not sorted. But still you cannot do binary search with un sorted array. – Renganathan V Oct 05 '17 at 02:59

score 0 · Answer 5 · answered Mar 31 '12 at 12:13

One way to do (what I understand) you need:

Determine the size n of the original array.
Create result array R and initialize its elements with 0 . . n-1
Finally implement one sort algorithm in the way that it sorts a copy(!) of your original array whilst also switching the elements in R

Example run:

    Copied  Result
    Array 
------------------
1.  2-3-1   0-1-2
2.  2-1-3   0-2-1
3.  1-2-3   2-0-1

Sort an Integer Array and Store result with its index in Java

5 Answers5