matriz java para ordenar: forma rápida de obtener una lista ordenada de los índices de una matriz

Question

El problema: Consder los siguientes flotadores []:

d[i] =  1.7 -0.3 2.1 0.5 

Lo que yo quiero es un array de int [] que representa el orden de la matriz original con índices.

s[i] =  1 3 0 2 
d[s[i]] = -0.3 0.5 1.7 2.1 

Por supuesto que se podría hacer con un comparador de costumbre, un conjunto ordenado de objetos personalizados, o simplemente ordenar la matriz y luego la búsqueda de los índices de la matriz original (estremecimiento).

Lo que de hecho estoy buscando es el equivalente para el segundo argumento de devolución de Matlab's sort function.

¿Hay una manera fácil de hacerlo (< 5 LOC)? ¿Puede haber una solución que no necesite asignar un nuevo objeto para cada elemento?

---

Actualización:

Gracias por sus respuestas. Desafortunadamente, nada de lo que se ha propuesto hasta ahora se asemeja a la solución simple y eficiente que estaba esperando. Por lo tanto, abrí un hilo en el foro de comentarios de JDK, proponiendo la adición de una nueva función de biblioteca de clases para abordar el problema. Veamos qué piensa Sun/Oracle sobre el problema.

http://forums.java.net/jive/thread.jspa?threadID=62657&tstart=0

Answer 1

Me adaptar el algoritmo de ordenación rápida para realizar la operación de cambio de múltiples arreglos al mismo tiempo: la matriz índice y la matriz de valores.Por ejemplo (basado en este quicksort):

public static void quicksort(float[] main, int[] index) { 
    quicksort(main, index, 0, index.length - 1); 
} 

// quicksort a[left] to a[right] 
public static void quicksort(float[] a, int[] index, int left, int right) { 
    if (right <= left) return; 
    int i = partition(a, index, left, right); 
    quicksort(a, index, left, i-1); 
    quicksort(a, index, i+1, right); 
} 

// partition a[left] to a[right], assumes left < right 
private static int partition(float[] a, int[] index, 
int left, int right) { 
    int i = left - 1; 
    int j = right; 
    while (true) { 
     while (less(a[++i], a[right]))  // find item on left to swap 
      ;        // a[right] acts as sentinel 
     while (less(a[right], a[--j]))  // find item on right to swap 
      if (j == left) break;   // don't go out-of-bounds 
     if (i >= j) break;     // check if pointers cross 
     exch(a, index, i, j);    // swap two elements into place 
    } 
    exch(a, index, i, right);    // swap with partition element 
    return i; 
} 

// is x < y ? 
private static boolean less(float x, float y) { 
    return (x < y); 
} 

// exchange a[i] and a[j] 
private static void exch(float[] a, int[] index, int i, int j) { 
    float swap = a[i]; 
    a[i] = a[j]; 
    a[j] = swap; 
    int b = index[i]; 
    index[i] = index[j]; 
    index[j] = b; 
} 

Answer 2

supongo que la forma más fácil de hacerlo es índice de la matriz como se crea. Necesitarás clave, pares de valores. Si el índice es una estructura separada, entonces no puedo ver cómo podría hacerlo sin otros objetos (interesado en ver, aunque)

Answer 3

Crear una TreeMap de los valores de los índices

float[] array = new float[]{}; 
    Map<Float, Integer> map = new TreeMap<Float, Integer>(); 
    for (int i = 0; i < array.length; ++i) { 
     map.put(array[i], i); 
    } 
    Collection<Integer> indices = map.values(); 

índices serán los ordenados por los flotadores a los que apuntan, la matriz original está intacta. La conversión de Collection<Integer> a int[] se deja como un ejercicio si es realmente necesario.

EDIT: Como se señala en los comentarios, este enfoque no funciona si hay valores duplicados en la matriz flotante. Esto se puede solucionar convirtiendo el Map<Float, Integer> en Map<Float, List<Integer>>, aunque esto complicará ligeramente el interior del bucle for y la generación de la colección final.

Answer 4

Con Functional Java:

import static fj.data.Array.array; 
import static fj.pre.Ord.*; 
import fj.P2; 

array(d).toStream().zipIndex().sort(p2Ord(doubleOrd, intOrd)) 
    .map(P2.<Double, Integer>__2()).toArray(); 

Answer 5

convertir la entrada a una clase par como la de abajo y luego resolver esto utilizando Arrays.sort(). Arrays.sort() garantiza que el orden original se conserve para valores iguales como lo hace Matlab. Luego debe convertir el resultado ordenado a las matrices separadas.

class SortPair implements Comparable<SortPair> 
{ 
    private int originalIndex; 
    private double value; 

    public SortPair(double value, int originalIndex) 
    { 
    this.value = value; 
    this.originalIndex = originalIndex; 
    } 

    @Override public int compareTo(SortPair o) 
    { 
    return Double.compare(value, o.getValue()); 
    } 

    public int getOriginalIndex() 
    { 
    return originalIndex; 
    } 

    public double getValue() 
    { 
    return value; 
    } 

}

Answer 6

El caso más general de Jherico's answer que permite valores duplicados sería la siguiente:

// Assuming you've got: float[] array; defined already 

TreeMap<Float, List<Integer>> map = new TreeMap<Float, List<Integer>>(); 
for(int i = 0; i < array.length; i++) { 
    List<Integer> ind = map.get(array[i]); 
    if(ind == null){ 
     ind = new ArrayList<Integer>(); 
     map.put(array[i], ind); 
    } 
    ind.add(i); 
} 

// Now flatten the list 
List<Integer> indices = new ArrayList<Integer>(); 
for(List<Integer> arr : map.values()) { 
    indices.addAll(arr); 
} 

Answer 7

solución simple para crear una matriz indexador: ordenar el indizador comparando la valores de datos:

final Integer[] idx = { 0, 1, 2, 3 }; 
final float[] data = { 1.7f, -0.3f, 2.1f, 0.5f }; 

Arrays.sort(idx, new Comparator<Integer>() { 
    @Override public int compare(final Integer o1, final Integer o2) { 
     return Float.compare(data[o1], data[o2]); 
    } 
}); 

Answer 8

Otra solución no simple. Aquí hay una versión de orden de fusión que es stable y no modifica la matriz fuente, aunque la fusión requiere memoria extra.

public static int[] sortedIndices(double[] x) { 
    int[] ix = new int[x.length]; 
    int[] scratch = new int[x.length]; 
    for (int i = 0; i < ix.length; i++) { 
     ix[i] = i; 
    } 
    mergeSortIndexed(x, ix, scratch, 0, x.length - 1); 
    return ix; 
} 

private static void mergeSortIndexed(double[] x, int[] ix, int[] scratch, int lo, int hi) { 
    if (lo == hi) 
     return; 
    int mid = (lo + hi + 1)/2; 
    mergeSortIndexed(x, ix, scratch, lo, mid - 1); 
    mergeSortIndexed(x, ix, scratch, mid, hi); 
    mergeIndexed(x, ix, scratch, lo, mid - 1, mid, hi); 
} 

private static void mergeIndexed(double[] x, int[] ix, int[] scratch, int lo1, int hi1, int lo2, int hi2) { 
    int i = 0; 
    int i1 = lo1; 
    int i2 = lo2; 
    int n1 = hi1 - lo1 + 1; 
    while (i1 <= hi1 && i2 <= hi2) { 
     if (x[ix[i1]] <= x[ix[i2]]) 
      scratch[i++] = ix[i1++]; 
     else 
      scratch[i++] = ix[i2++]; 
    } 
    while (i1 <= hi1) 
     scratch[i++] = ix[i1++]; 
    while (i2 <= hi2) 
     scratch[i++] = ix[i2++]; 
    for (int j = lo1; j <= hi1; j++) 
     ix[j] = scratch[j - lo1]; 
    for (int j = lo2; j <= hi2; j++) 
     ix[j] = scratch[(j - lo2 + n1)]; 
} 

Answer 9

La mejor solución sería a lo largo de las líneas de qsort de C, que le permite especificar las funciones para comparar y de intercambio, así qsort no tiene que ser consciente del tipo o de la organización de los datos que están siendo ordenados. Aquí hay uno que puedes probar. Como Java no tiene funciones, use la clase interna Array para envolver la matriz o colección que se va a ordenar. Luego envuelve eso en un IndexArray y ordena. El resultado de getIndex() en IndexArray será una matriz de índices como se describe en JavaDoc.

public class QuickSortArray { 

public interface Array { 
    int cmp(int aindex, int bindex); 
    void swap(int aindex, int bindex); 
    int length(); 
} 

public static void quicksort(Array a) { 
    quicksort(a, 0, a.length() - 1); 
} 

public static void quicksort(Array a, int left, int right) { 
    if (right <= left) return; 
    int i = partition(a, left, right); 
    quicksort(a, left, i-1); 
    quicksort(a, i+1, right); 
} 

public static boolean isSorted(Array a) { 
    for (int i = 1, n = a.length(); i < n; i++) { 
     if (a.cmp(i-1, i) > 0) 
      return false; 
    } 
    return true; 
} 

private static int mid(Array a, int left, int right) { 
    // "sort" three elements and take the middle one 
    int i = left; 
    int j = (left + right)/2; 
    int k = right; 
    // order the first two 
    int cmp = a.cmp(i, j); 
    if (cmp > 0) { 
     int tmp = j; 
     j = i; 
     i = tmp; 
    } 
    // bubble the third down 
    cmp = a.cmp(j, k); 
    if (cmp > 0) { 
     cmp = a.cmp(i, k); 
     if (cmp > 0) 
      return i; 
     return k; 
    } 
    return j; 
} 

private static int partition(Array a, int left, int right) { 
    int mid = mid(a, left, right); 
    a.swap(right, mid); 
    int i = left - 1; 
    int j = right; 

    while (true) { 
     while (a.cmp(++i, right) < 0) 
      ; 
     while (a.cmp(right, --j) < 0) 
      if (j == left) break; 
     if (i >= j) break; 
     a.swap(i, j); 
    } 
    a.swap(i, right); 
    return i; 
} 

public static class IndexArray implements Array { 
    int[] index; 
    Array a; 

    public IndexArray(Array a) { 
     this.a = a; 
     index = new int[a.length()]; 
     for (int i = 0; i < a.length(); i++) 
      index[i] = i; 
    } 

    /** 
    * Return the index after the IndexArray is sorted. 
    * The nested Array is unsorted. Assume the name of 
    * its underlying array is a. The returned index array 
    * is such that a[index[i-1]] <= a[index[i]] for all i 
    * in 1..a.length-1. 
    */ 
    public int[] index() { 
     int i = 0; 
     int j = index.length - 1; 
     while (i < j) { 
      int tmp = index[i]; 
      index[i++] = index[j]; 
      index[j--] = tmp; 
     } 
     int[] tmp = index; 
     index = null; 
     return tmp; 
    } 

    @Override 
    public int cmp(int aindex, int bindex) { 
     return a.cmp(index[aindex], index[bindex]); 
    } 

    @Override 
    public void swap(int aindex, int bindex) { 
     int tmp = index[aindex]; 
     index[aindex] = index[bindex]; 
     index[bindex] = tmp; 
    } 

    @Override 
    public int length() { 
     return a.length(); 
    } 

} 

Answer 10

//Here index array(of length equal to length of d array) contains the numbers from 0 to length of d array 
     public static Integer [] SortWithIndex(float[] data, Integer [] index) 
    { 
    int len = data.length; 
    float temp1[] = new float[len]; 
    int temp2[] = new int[len]; 



     for (int i = 0; i <len; i++) { 


       for (int j = i + 1; j < len; j++) { 


        if(data[i]>data[j]) 
        { 
        temp1[i] = data[i]; 
        data[i] = data[j]; 
        data[j] = temp1[i]; 



        temp2[i] = index[i]; 
        index[i] = index[j]; 
        index[j] = temp2[i]; 

        } 
        } 

     } 

     return index; 

    } 

Answer 11

public static int[] indexSort(final double[] v, boolean keepUnsorted) { 
    final Integer[] II = new Integer[v.length]; 
    for (int i = 0; i < v.length; i++) II[i] = i; 
    Arrays.sort(II, new Comparator<Integer>() { 
     @Override 
     public int compare(Integer o1, Integer o2) { 
      return Double.compare(v[o1],v[o2]); 
     } 
    }); 
    int[] ii = new int[v.length]; 
    for (int i = 0; i < v.length; i++) ii[i] = II[i]; 
    if (!keepUnsorted) { 
     double[] clon = v.clone(); 
     for (int i = 0; i < v.length; i++) v[i] = clon[II[i]]; 
    } 
    return ii; 
} 

Answer 12

me gustaría hacer algo como esto:

public class SortedArray<T extends Comparable<T>> { 
    private final T[] tArray; 
    private final ArrayList<Entry> entries; 

    public class Entry implements Comparable<Entry> { 
     public int index; 

     public Entry(int index) { 
      super(); 
      this.index = index; 
     } 

     @Override 
     public int compareTo(Entry o) { 
      return tArray[index].compareTo(tArray[o.index]); 
     } 
    } 

    public SortedArray(T[] array) { 
     tArray = array; 
     entries = new ArrayList<Entry>(array.length); 
     for (int i = 0; i < array.length; i++) { 
      entries.add(new Entry(i)); 
     } 
     Collections.sort(entries); 
    } 

    public T getSorted(int i) { 
     return tArray[entries.get(i).index]; 

    } 

    public T get(int i) { 
     return tArray[i]; 
    } 
} 

Answer 13

A continuación se muestra un método basado en la ordenación por inserción

public static int[] insertionSort(float[] arr){ 
    int[] indices = new int[arr.length]; 
     indices[0] = 0; 
     for(int i=1;i<arr.length;i++){ 
      int j=i; 
      for(;j>=1 && arr[j]<arr[j-1];j--){ 
        float temp = arr[j]; 
        arr[j] = arr[j-1]; 
        indices[j]=indices[j-1]; 
        arr[j-1] = temp; 
      } 
      indices[j]=i; 
     } 
     return indices;//indices of sorted elements 
} 

Answer 14

Uso de Java 8 funciones (sin biblioteca adicional), forma concisa de lograrlo.

int[] a = {1,6,2,7,8} 
int[] sortedIndices = IntStream.range(0, a.length) 
       .boxed().sorted((i, j) -> a[i] - a[j]) 
       .mapToInt(ele -> ele).toArray(); 

Answer 15

Me gustaría utilizar esto porque es muy rápido. Pero lo uso para int, puede cambiarlo para flotar.

private static void mergeSort(int[]array,int[] indexes,int start,int end){ 
    if(start>=end)return; 
    int middle = (end-start)/2+start; 
    mergeSort(array,indexes,start,middle); 
    mergeSort(array,indexes,middle+1,end); 
    merge(array,indexes,start,middle,end); 
} 
private static void merge(int[]array,int[] indexes,int start,int middle,int end){ 
    int len1 = middle-start+1; 
    int len2 = end - middle; 
    int leftArray[] = new int[len1]; 
    int leftIndex[] = new int[len1]; 
    int rightArray[] = new int[len2]; 
    int rightIndex[] = new int[len2]; 
    for(int i=0;i<len1;++i)leftArray[i] = array[i+start]; 
    for(int i=0;i<len1;++i)leftIndex[i] = indexes[i+start]; 
    for(int i=0;i<len2;++i)rightArray[i] = array[i+middle+1]; 
    for(int i=0;i<len2;++i)rightIndex[i] = indexes[i+middle+1]; 
    //merge 
    int i=0,j=0,k=start; 
    while(i<len1&&j<len2){ 
     if(leftArray[i]<rightArray[j]){ 
      array[k] = leftArray[i]; 
      indexes[k] = leftIndex[i]; 
      ++i; 
     } 
     else{ 
      array[k] = rightArray[j]; 
      indexes[k] = rightIndex[j]; 
      ++j; 
     } 
     ++k; 
    } 
    while(i<len1){ 
     array[k] = leftArray[i]; 
     indexes[k] = leftIndex[i]; 
     ++i;++k; 
    } 
    while(j<len2){ 
     array[k] = rightArray[j]; 
     indexes[k] = rightIndex[j]; 
     ++j;++k; 
    } 
}