ejemplo - sort list java 7

Ordenando matrices coincidentes en Java

Question

Digamos que tengo dos matrices (en Java),

int [] números; 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.

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

¿Cuál es la forma más limpia y simple 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

¿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 necesitas una matriz, por qué no utilizar algo derivado de la Colección?

Answer 2

¿Sería suficiente codificar tu 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 3

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 4

Me gusta la solución de @vavare. Haz una matriz de puntero:

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

y luego cuando ordena los números, cambie los valores en ptr en lugar de en números. Luego 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: está bien, parece que otros me han vencido en esto. No XP para mi

Answer 5

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;
    }
  }
}

Luego puede separar su algoritmo de clasificación de la lógica de ordenamiento (puede usar Collections.sort si usa una lista en lugar de una matriz), y lo más importante, no tendrá que preocuparse de que de alguna manera consiga que dos arreglos se desincronicen.

Answer 6

Si está dispuesto a asignar un espacio extra, puede generar otra matriz, llamarla extra, con elementos como este:

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

Luego, puede ordenar esta matriz extra usando Arrays.sort () con un comparador personalizado (que, al comparar los elementos i y j 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 bueno, 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 normalmente encuentro que los pares de plantillas C ++ y buenos mapas son indispensables;)

Answer 7

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 8

La forma más sencilla de hacer esto en C sería bubblespoints + punteros dobles. 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 género, llamando a una función de comparación, que luego puede escribirse para cada estructura, pero ya lo sabe :)

Answer 9

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 verse así:

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 10

Usa un TreeMap

Answer 11

Puede usar sort () con un comparador personalizado si mantuvo una tercera matriz con el índice, y ordenó eso, dejando los datos intactos.

Ejemplo de código Java:

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 debe usar Integer lugar de int o no puede usar un comparador personalizado.

Answer 12

Crédito a @tovare por la mejor respuesta original.

Mi respuesta a continuación elimina el autoboxing (ahora) innecesario a través de la dependencia de Maven {net.mintern: primitive: 1.2.2} de esta respuesta: https://.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 intentar evitar el uso de una matriz de objetos (lo que puede causar un evento GC doloroso). Desafortunadamente no hay una solución general, pensó. Pero, para su caso específico, en el que los números son diferentes entre sí, 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 matrices ordenadas pueden reemplazarse por Int2IntOpenHashMap , que realiza una ejecución más rápida, pero el uso de la memoria podría ser el doble.