Ordenando matrices coincidentes en Java

Question

Digamos que tengo dos matrices (en Java),

int [] numbers; y int [] colores;

Cada ith elemento de números corresponde a su elemento ith en colores. Ej., Números = {4,2,1} colores = {0x11, 0x24, 0x01}; Significa que el número 4 es el color 0x11, el número 2 es 0x24, etc.

Quiero ordenar la matriz de números, pero aún la tengo para que cada elemento coincida con su par de colores.

Ej. números = {1,2,4}; colors = {0x01,0x24,0x11};

¿Cuál es la forma más limpia y sencilla de hacer esto? Las matrices tienen algunos miles de artículos, por lo que estar en su lugar sería lo mejor, pero no obligatorio. ¿Tendría sentido hacer un Arrays.sort() y un comparador personalizado? Es preferible usar las funciones de la biblioteca tanto como sea posible.

Nota: Sé que la "mejor" solución es hacer una clase para los dos elementos y usar un comparador personalizado. Esta pregunta tiene como objetivo preguntar a las personas la forma más rápida de codificar esto. Imagínese que está en una competencia de programación, no querría estar haciendo todas estas clases adicionales, clases anónimas para el comparador, etc. Mejor aún, olvide Java; ¿cómo lo codificaría en C?

Answer 1

Debe ordenar la matriz de colores por su elemento relativo en la matriz de números. Especifique un comparador que compare números y use eso como la comparación para la matriz de colores.

Answer 2

¿Por qué no presentar un objeto para representar un número y un color e implementar una función de comparación para eso?

Además, ¿realmente necesita una matriz, por qué no utilizar algo derivado de la Colección?

Answer 3

Parece que lo más limpio sería crear una clase de propiedad personalizada que implemente Comparable. Por ejemplo:

class Color implements Comparable { 
    private int number; 
    private int color; 

    // (snip ctor, setters, etc.) 

    public int getNumber() { 
    return number; 
    } 
    public int getColor() { 
    return color; 
    } 

    public int compareTo(Color other) { 
    if (this.getNumber() == other.getNumber) { 
     return 0; 
    } else if (this.getNumber() > other.getNumber) { 
     return 1; 
    } else { 
     return -1; 
    } 
    } 
} 

A continuación, se puede separar el algoritmo de ordenación de la lógica de pedido (se puede utilizar Collections.sort si se utiliza una lista en lugar de una matriz), y lo más importante, usted no tendrá que preocuparse de alguna manera, obtener dos matrices fuera de sincronización.

Answer 4

Si usted estaría dispuesto a destinar algo más de espacio, se podría generar otra matriz, lo llaman adicional, con elementos como este:

extra = [0,1,...,numbers.length-1] 

entonces se podría clasificar esta matriz la capacidad utilizando Arrays.sort () con un comparador personalizado (que, al comparar los elementos iyj realmente compara los números [extra [i]] y los números [extra [j]]). De esta manera, después de ordenar la matriz adicional, extra [0] contendría el índice del número más pequeño y, como los números y colores no se movieron, el color correspondiente.
Esto no es muy agradable, pero hace el trabajo, y realmente no puedo pensar en una manera más fácil de hacerlo.

Como nota al margen, en la competencia por lo general encuentran el C++ pares de plantilla y los mapas agradables indispensables;)

Answer 5

Se puede usar sort() con un comparador personalizada si se mantenía una tercera matriz con el índice, y ordenó eso, dejando los datos intactos.

Java ejemplo de código:

Integer[] idx = new Integer[numbers.length]; 
for(int i = 0 ; i < idx.length; i++) idx[i] = i;    
Arrays.sort(idx, new Comparator<Integer>() { 
    public int compare(Integer i1, Integer i2) {       
     return Double.compare(numbers[i1], numbers[i2]); 
    }     
}); 

// numbers[idx[i]] is the sorted number at index i 
// colors[idx[i]] is the sorted color at index i 

Tenga en cuenta que usted tiene que utilizar en lugar de Integerint o no se puede utilizar un comparador personalizado.

Answer 6

Me gusta la solución de @tovare. Hacer una matriz de punteros:

int ptr[] = { 1, 2, 3 }; 

y luego, cuando se ordena en los números, intercambia los valores de PTR en lugar de en los números. A continuación, acceda a través de la matriz ptr, como

for (int i = 0; i < ptr.length; i++) 
{ 
    printf("%d %d\n", numbers[ptr[i]], colors[ptr[i]]); 
} 

Actualización: bueno, parece que otros me han vencido. No XP para mi

Answer 7

¿Sería suficiente codificar su propio método de clasificación? Un simple bubblesort probablemente sea rápido de codificar (y acertar). No hay necesidad de clases adicionales o comparadores.

Answer 8

Un truco rápido sería combinar las dos matrices con cambios de bit. Haga una matriz de longs tal que los 32 bits más significativos sean el número y el 32 menos significativo sea el color. Use un método de clasificación y luego desempaquete.

Answer 9

La forma más sencilla de hacer esto en C sería bubblespoints + dos punteros. Por supuesto, el más rápido sería quicksort + dos punteros. Por supuesto, el segundo puntero mantiene la correlación entre las dos matrices.

Preferiría definir valores que están almacenados en dos matrices como una estructura, y usar la estructura en una sola matriz. Luego usa quicksort en él. puede escribir una versión genérica de ordenamiento, llamando a una función de comparación, que luego puede escribirse para cada estructura, pero ya sabe que :)

Answer 10

Un ejemplo que ilustra el uso de una tercera matriz de índices. No estoy seguro de si esta es la mejor implementación.

 
    import java.util.*;
 

public class Sort { 

    private static void printTable(String caption, Integer[] numbers, 
       Integer[] colors, Integer[] sortOrder){ 

     System.out.println(caption+ 
       "\nNo Num Color"+ 
       "\n----------------"); 

     for(int i=0;i<sortOrder.length;i++){ 
      System.out.printf("%x %d  %d\n", 
        i,numbers[sortOrder[i]],colors[sortOrder[i]]); 

     } 
    } 


    public static void main(String[] args) { 

     final Integer[] numbers = {1,4,3,4,2,6}; 
     final Integer[] colors = {0x50,0x34,0x00,0xfe,0xff,0xff}; 
     Integer[] sortOrder = new Integer[numbers.length]; 

     // Create index array. 
     for(int i=0; i<sortOrder.length; i++){ 
      sortOrder[i] = i; 
     } 
     printTable("\nNot sorted",numbers, colors, sortOrder); 

     Arrays.sort(sortOrder,new Comparator<Integer>() { 
      public int compare(Integer a, Integer b){ 
       return numbers[b]-numbers[a]; 
      }}); 
     printTable("\nSorted by numbers",numbers, colors, sortOrder); 

     Arrays.sort(sortOrder,new Comparator<Integer>() { 
      public int compare(Integer a, Integer b){ 
       return colors[b]-colors[a]; 
      }}); 
     printTable("\nSorted by colors",numbers, colors, sortOrder); 
    } 
} 
 

La salida debería tener este aspecto:

 

Not sorted 
No Num Color 
---------------- 
0 1  80 
1 4  52 
2 3  0 
3 4  254 
4 2  255 
5 6  255 

Sorted by numbers 
No Num Color 
---------------- 
0 6  255 
1 4  52 
2 4  254 
3 3  0 
4 2  255 
5 1  80 

Sorted by colors 
No Num Color 
---------------- 
0 6  255 
1 2  255 
2 4  254 
3 1  80 
4 4  52 
5 3  0 

Answer 11

se utiliza un crédito TreeMap

Answer 12

a @tovare para la mejor respuesta original.

Mi respuesta a continuación elimina la (ahora) autoboxing innecesaria a través de Maven dependencia {net.mintern : primitive : 1.2.2} de esta respuesta: https://stackoverflow.com/a/27095994/257299

int[] idx = new int[numbers.length]; 
for(int i = 0 ; i < idx.length; i++) idx[i] = i; 
final boolean isStableSort = false; 
Primitive.sort(idx, 
       (i1, i2) -> Double.compare(numbers[i1], numbers[i2]), 
       isStableSort); 

// numbers[idx[i]] is the sorted number at index i 
// colors[idx[i]] is the sorted color at index i 

Answer 13

supongo que desea la optimización del rendimiento al tratar de evitar el uso de matriz de objetos (que puede causar una dolorosa Evento GC). Desafortunadamente no hay una solución general, pensó. Pero, para su caso específico, en el que los números son diferentes unos de otros, es posible que solo se creen dos matrices.

/** 
* work only for array of different numbers 
*/ 
private void sortPairArray(int[] numbers, int[] colors) { 
    int[] tmpNumbers = Arrays.copyOf(numbers, numbers.length); 
    int[] tmpColors = Arrays.copyOf(colors, colors.length); 
    Arrays.sort(numbers); 
    for (int i = 0; i < tmpNumbers.length; i++) { 
     int number = tmpNumbers[i]; 
     int index = Arrays.binarySearch(numbers, number); // surely this will be found 
     colors[index] = tmpColors[i]; 
    } 
} 

Dos conjuntos ordenados se pueden sustituir por Int2IntOpenHashMap, que realiza funcione más rápido, pero el uso de memoria podrían ser el doble.