Get the Indices of an Array After Sorting

Get the indices of an array after sorting?

Don't sort the array to start with. Sort the index array, passing in a comparator which compares values by using them as indexes into the array. So you end up with newIndex as the result of the sort, and it's trivial to go from there to the sorted array of actual items.

Admittedly that means sorting an array of integers in a custom way - which either means using an Integer[] and the standard Java library, or a 3rd party library which has an "IntComparator" interface which can be used in conjunction with a sort(int[], IntComparator) type of method.

EDIT: Okay, here's an example comparator. For the sake of simplicity I'll assume you only want to sort an "original" array of strings... and I won't bother with nullity testing.

public class ArrayIndexComparator implements Comparator<Integer>
{
private final String[] array;

public ArrayIndexComparator(String[] array)
{
this.array = array;
}

public Integer[] createIndexArray()
{
Integer[] indexes = new Integer[array.length];
for (int i = 0; i < array.length; i++)
{
indexes[i] = i; // Autoboxing
}
return indexes;
}

@Override
public int compare(Integer index1, Integer index2)
{
// Autounbox from Integer to int to use as array indexes
return array[index1].compareTo(array[index2]);
}
}

You'd use it like this:

String[] countries = { "France", "Spain", ... };
ArrayIndexComparator comparator = new ArrayIndexComparator(countries);
Integer[] indexes = comparator.createIndexArray();
Arrays.sort(indexes, comparator);
// Now the indexes are in appropriate order.

keeping track of the original indices of an array after sorting in C

There is also a method as follows under limited conditions.

#include <stdio.h>

int main(void){
int data[] ={ 5,4,1,2,3 }; //Without duplication, The number of limited range.
int size = sizeof(data)/sizeof(*data);
int keys[size];
int i;

printf("data :\n");
for(i=0;i<size;i++){
printf("%d ",data[i]);
}
for(i=0;i<size;i++){
keys[data[i]-1]=i;
}

printf("\n\ndata\tindex\n");
for(i=0;i<size;i++){
printf("%d\t%d\n", data[keys[i]], keys[i]);
}
return 0;
}
/* result sample
data :
5 4 1 2 3

data index
1 2
2 3
3 4
4 1
5 0
*/

How to sort an array of index @Kerrek is as proposed.

#include <stdio.h>
#include <stdlib.h>

int *array;

int cmp(const void *a, const void *b){
int ia = *(int *)a;
int ib = *(int *)b;
return array[ia] < array[ib] ? -1 : array[ia] > array[ib];
}

int main(void){
int data[] ={ 5,4,1,2,3 };
int size = sizeof(data)/sizeof(*data);
int index[size];//use malloc to large size array
int i;

for(i=0;i<size;i++){
index[i] = i;
}
array = data;
qsort(index, size, sizeof(*index), cmp);
printf("\n\ndata\tindex\n");
for(i=0;i<size;i++){
printf("%d\t%d\n", data[index[i]], index[i]);
}
return 0;
}

How do I get the index of sorted numbers from Arrays.sort in Java?

Write a custom comparator that sorts a list of indices, while comparing the double values in the original list.

Then create a new array, iterate over all indices and map the double values to the right location based on the index.

Integer[] indexes = IntStream.range(0, test.length).boxed().toArray(Integer[]::new);

// indexes contains [0, 1, 2, 3, 4].

Arrays.sort(indexes, Comparator.<Integer>comparingDouble(i -> test[i]).reversed());

// indexes is now [4, 0, 3, 1, 2].

// Now you can copy back into test:
test = IntStream.range(0, test.length).mapToObj(i -> test[i]).toArray(Double[]::new);

Ideone Demo

Keeping indexes of an elements in the array after sorting in Java

You're forgetting to sort the actual array also. If the arrivalTimes array isn't sorted, your condition will not act the way you expect.

int[] bSort(int[] arrivalTimes) {
int[] sequence = new int[arrivalTimes.length];
for (int i = 0; i < sequence.length; i++) {
sequence[i] = i;
}

for (int i = 0; i < arrivalTimes.length - 1; i++) {
for (int j = i + 1; j < arrivalTimes.length; j++) {
if (arrivalTimes[i] > arrivalTimes[j]) {
int temp = sequence[i];
sequence[i] = sequence[j];
sequence[j] = temp;

int temp2 = arrivalTimes[i];
arrivalTimes[i] = arrivalTimes[j];
arrivalTimes[j] = temp2;
}
}
}
return sequence;
}

This is an inefficient solution though. I suspect this is part of some algorithms assignment so I'll leave the optimisations up to you.

Get the indices of the array after sorting in golang

Make a wrapper for sort.IntSlice that remembers the indexes and swaps them when it swaps the values:

type Slice struct {
sort.IntSlice
idx []int
}

func (s Slice) Swap(i, j int) {
s.IntSlice.Swap(i, j)
s.idx[i], s.idx[j] = s.idx[j], s.idx[i]
}

Playground: http://play.golang.org/p/LnSLfe-fXk.

EDIT: As DaveC mentioned in the comments, you can actually wrap around sort.Interface to create a data structure for any sortable type:

type Slice struct {
sort.Interface
idx []int
}

func (s Slice) Swap(i, j int) {
s.Interface.Swap(i, j)
s.idx[i], s.idx[j] = s.idx[j], s.idx[i]
}

How to keep array indexvalue after sorting

If you want to sort by something nontrivial, pass a callback to sort.

input.sort(function(a,b) {
// b - a for descending order
return b.split(" ").length - a.split(" ").length;
});

How to store the original indices of array after sorting the array in ascending ordering

The issue is that you are sorting the original array_dist when you shouldn't be sorting this at all.

You should only sort the index_array based on the comparison of the array_dist values :

// Compare values at `array_dist`, using the index array 
if (array_dist[index_array[i]] > array_dist[index_array[j]])
{
// the indices need to be swapped
x = index_arr[i];
index_arr[i] = index_arr[j];
index_arr[j] = x;
}

Once you have this, then to print out the array_dist in sorted order:

for (int i = 0; i < 4344; ++i)
{
cout << index_arr[i] << " : "
<< array_dist[index_arr[i]] << endl;
}

You use the index_array as a subscript within the original array.

Javascript: Sort array and return an array of indices that indicates the position of the sorted elements with respect to the original elements

var test = ['b', 'c', 'd', 'a'];
var test_with_index = [];
for (var i in test) {
test_with_index.push([test[i], i]);
}
test_with_index.sort(function(left, right) {
return left[0] < right[0] ? -1 : 1;
});
var indexes = [];
test = [];
for (var j in test_with_index) {
test.push(test_with_index[j][0]);
indexes.push(test_with_index[j][1]);
}

Edit

You guys are right about for .. in. That will break if anybody munges the array prototype, which I observe annoyingly often. Here it is with that fixed, and wrapped up in a more usable function.

function sortWithIndeces(toSort) {
for (var i = 0; i < toSort.length; i++) {
toSort[i] = [toSort[i], i];
}
toSort.sort(function(left, right) {
return left[0] < right[0] ? -1 : 1;
});
toSort.sortIndices = [];
for (var j = 0; j < toSort.length; j++) {
toSort.sortIndices.push(toSort[j][1]);
toSort[j] = toSort[j][0];
}
return toSort;
}

var test = ['b', 'c', 'd', 'a'];
sortWithIndeces(test);
alert(test.sortIndices.join(","));


Related Topics



Leave a reply



Submit