how to sort (indexes) of an array to get the original array sorted from the smallest to the biggest value by using those indexes

Question

for example I have this array

int[] a = {6,10,16,11,7,12,3,9,8,5};

i want to sort its indexes like this

[6,9,0,4,8,7,1,3,5,2]

so I can use indexes to sort a from the smallest to the biggest value. in my code I got instead this

[6, 9, 4, 8, 7, 4, 5, 6, 6, 6] 

this is my code

int[] a = {6,10,16,11,7,12,3,9,8,5};
int[] indeks = indekssortering(a);
System.out.println(Arrays.toString(indeks));

public static int[] indekssortering(int[] a){
    int[] indeks = new int[a.length];
    int m = 0;
    boolean finnes = false;
    boolean nyVerdi = false;
    int n = 0;
    for (int j = 0; j < a.length; j++) {
        for (int i = m+1; i < a.length ; i++) {
            if(a[m] > a[i]){
                for (int k = 0; k < j; k++) {
                    if(indeks[k] == i) finnes = true; //check if the same position is saved before
                }
                if(!finnes){ // if not so its the next minimum value
                    m = i;
                } else {
                    nyVerdi = true; // if didnt find match then the value used to compare is the next minimum
                }
            }
            finnes = false;
        }
        indeks[j] = m;
        if(nyVerdi) n=n+1;
        nyVerdi = false;
        m=0+n;
    }
    return indeks;
}

I need help to make this code work or to find a better idea than this.

what I tried to do is. compare all values with the first values, get the smallest and save the position into the array (indeks). before save it, I made for loop to check if this position is been added before. and if there is no value bigger than the value used to compare that means its the next small value. i got some of them right and others wrong. I believe that I need to change this idea and find a better solution.

Answer 1

With java 8, you can use a lambda compare. Optionally, you can then do an inplace reorder of a[] and I[] according to I[].

package x;
import java.util.Arrays;
public class x {
    // although I[] needs to be of type Integer, a[] doesn't
    public static void main(String[] args) {
        int[] a = {6,10,16,11,7,12,3,9,8,5};
        // generate array of indices
        Integer[] I = new Integer [a.length];
        for(int i = 0; i < I.length; i++)
            I[i] = i;
        // sort I[] according to a[]
        Arrays.sort(I, (i, j) -> a[i]-a[j]);
        // display result
        for (int i = 0; i < a.length; i++)
            System.out.println(a[I[i]]);

        // optional inplace reorder a[] and I[] according to I[]
        // time complexity is O(n)
        for(int i = 0; i < I.length; i++){
            if(i != I[i]){
                int t = a[i];
                int j;
                int k = i;
                while(i != (j = I[k])){
                    a[k] = a[j];
                    I[k] = k;
                    k = j;
                }
                a[k] = t;
                I[k] = k;
            }
        }
        // display result
        System.out.println();
        for (int i = 0; i < a.length; i++)
            System.out.println(a[i]);
    }
}

Answer 2

You are essentially looking for a permutation of the array. Specifically, for a sorting permutation.

Unfortunately, the notation is somewhat ambiguous and confusing when referring to indices. The main difference is whether

sorted[indices[i]] = array[i]

or

sorted[i] = array[indices[i]]

should yield the sorted array. According to your question, you are looking for the latter.

This can be implemented in different ways, either by placing the elements into a List<Integer> and sorting this list using a comparator that refers to the original array, or by sorting a list of "pairs", each consisting of the value and its original index. (This approach was basically already shown by tdelev in his answer )

Here is an implementation that explicitly computes the index array, and applies it as a permutation to the input array:

import java.util.Arrays;
import java.util.Comparator;
import java.util.function.IntBinaryOperator;

public class SortingPermutations
{
    public static void main(String[] args)
    {
        int[] a = {6,10,16,11,7,12,3,9,8,5} ;
        int[] p = computeAscendingSortingPermutation(a);
        int[] s = applyPermutation(a, p);

        System.out.println("array       : " + Arrays.toString(a));
        System.out.println("permutation : " + Arrays.toString(p));
        System.out.println("sorted      : " + Arrays.toString(s));
    }

    /**
     * Compute the sorting permutation for the given array. This will return 
     * an array <code>p</code> so that <code>sorted[i] = array[p[i]]</code>
     * will result in an array where the values are sorted in ascending order.
     * 
     * @param array The array
     * @return The sorting permutation
     */
    private static int[] computeAscendingSortingPermutation(int array[])
    {
        return computeSortingPermutation(array, Integer::compare);
    }

    /**
     * Compute the sorting permutation for the given array. This will return 
     * an array <code>p</code> so that <code>sorted[i] = array[p[i]]</code>
     * will result in an array where the values are sorted according to
     * the given comparator
     * 
     * @param array The array
     * @param intComparator The comparator for the integer values
     * @return The sorting permutation
     */
    private static int[] computeSortingPermutation(
        int array[], IntBinaryOperator intComparator)
    {
        class Entry
        {
            int value;
            int index;
        }
        int n = array.length;
        Entry entries[] = new Entry[n];
        for (int i = 0; i < n; i++)
        {
            Entry e = new Entry();
            e.value = array[i];
            e.index = i;
            entries[i] = e;
        }
        Comparator<Entry> comparator = 
            (e0, e1) -> intComparator.applyAsInt(e0.value, e1.value);
        Arrays.sort(entries, comparator);
        int result[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            Entry e = entries[i];
            result[i] = e.index;
        }
        return result;
    }


    /**
     * Apply the given permutation to the given array, and return the result
     * as a new array. The result will be an array <code>r</code> where
     * <code>r[i] = array[permutation[i]]</code>
     * 
     * @param array The input array
     * @param permutation The permutation
     * @return The result array
     */
    private static int[] applyPermutation(int array[], int permutation[])
    {
        int n = array.length;
        int result[] = new int[n];
        for (int i=0; i<n; i++) 
        {
            result[i] = array[permutation[i]];
        }
        return result;
    }

}

The output is

array       : [6, 10, 16, 11, 7, 12, 3, 9, 8, 5]
permutation : [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]
sorted      : [3, 5, 6, 7, 8, 9, 10, 11, 12, 16]

as expected.

Answer 3

• Use a Map. Let key be the element and value be a queue of indices at which it occurred for that value.

• Sort the array. Now, poll for each element from it's queue stored in the map.

• Time Complexity: O(n * log(n))

• Space Complexity: O(n)

Code:

import java.util.*;
public class Solution {
    public static void main(String[] args){
        int[] a = new int[]{6,10,16,11,7,12,3,9,8,5};
        int[] result = new int[a.length];
        Map<Integer,Queue<Integer>> map = new HashMap<>();
        for(int i=0;i<a.length;++i){
            if(map.containsKey(a[i])){
                map.get(a[i]).offer(i);
            }else{
                Queue<Integer> q = new LinkedList<Integer>();
                q.offer(i);
                map.put(a[i],q);
            }
        }

        Arrays.sort(a);
        for(int i=0;i<result.length;++i){
            result[i] = map.get(a[i]).poll();
        }

        System.out.println(Arrays.toString(result));
    }
}

OUTPUT:

[6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

Answer 4

If a library for indexOf(int[], int) (like Guava) is available, you can get that very easily:

int[] a = { 6, 10, 16, 11, 7, 12, 3, 9, 8, 5 };
int[] b = Arrays.copyOf(a, a.length);
Arrays.sort(b);
Arrays.setAll(b, i -> indexOf(a, b[i])); // b = [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

If no library is available, here's an indexOf(int[], int) implementation:

public static int indexOf(int[] array, int search) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == search) {
            return i;
        }
    }
    return -1;
}

Answer 5

Here a classical bubble sort algorithm implementation modified to sort indexes

What you are looking for is actually any sorting algorithm which sorts int [] array. It's endless list of implementations all over the Internet. And then just change the comparison to array[result[i]] and swap values in result not in array itseft.

static int[] sort(int[] array) {
    final int size = array.length;

    final int[] result = new int[size];
    for (int i = 0; i < size; i++)
        result[i] = i;

    boolean sorted;
    do {
        sorted = true;
        int bubble = result[0];
        for (int i = 0; i < size - 1; i++) {
            if (array[bubble] > array[result[i + 1]]) {
                result[i] = result[i + 1];
                result[i + 1] = bubble;
                sorted = false;
            } else {
                bubble = result[i + 1];
            }
        }
    } while (!sorted);

    return result;
}

result arrays for your input data is [6, 9, 0, 4, 8, 7, 1, 3, 5, 2]

Answer 6

Here is a solutions without and with Java 8 Stream API.

import java.util.*;
import java.util.stream.IntStream;

public class SortIndices {

    static class Indexed {
        private final int number;
        private final int index;

        Indexed(int number, int index) {
            this.number = number;
            this.index = index;
        }

        public int getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }
    }

    static int[] indexesSorted(int[] input) {
        // Without using Stream API
        List<Indexed> indexed = new ArrayList<>();
        for(int i = 0; i < input.length; ++i) {
            indexed.add(new Indexed(input[i], i));
        }
        Collections.sort(indexed, Comparator.comparing(it -> it.number));
        int[] result = new int[indexed.size()];
        for(int i = 0; i < input.length; ++i) {
            result[i] = indexed.get(i).index;
        }
        return result;
        // Using Stream API
        /*return IntStream.range(0, input.length)
                .mapToObj(i -> new Indexed(input[i], i))
                .sorted(Comparator.comparing(it -> it.number))
                .mapToInt(it -> it.index)
                .toArray();*/
    }

    public static void main(String[] args) {
        int[] result = indexesSorted(new int[]{6, 10, 16, 11, 7, 12, 3, 9, 8, 5});
        System.out.println(Arrays.toString(result));
    }
}

If you can't use Java 8, use can implement Comparable interface on Indexed

    static class Indexed implements Comparable<Indexed> {
        private final int number;
        private final int index;

        Indexed(int number, int index) {
            this.number = number;
            this.index = index;
        }

        public int getNumber() {
            return number;
        }

        public int getIndex() {
            return index;
        }

        @Override
        public int compareTo(Indexed o) {
            return Integer.compare(number, o.number);
        }
    }

and then call Collections.sort without second argument.