ordenar - sort java

Ordenar múltiples matrices simultáneamente "en su lugar"

Question

Tengo los siguientes 3 arrays:

int[] indexes = new int[]{0,2,8,5};
String[] sources = new String[]{"how", "are", "today", "you"};
String[] targets = new String[]{"I", "am", "thanks", "fine"};

Quiero ordenar las tres matrices basadas en los índices:

indexes -> {0,2,5,8}
sources -> {"how", "are", "you", "today"}
targets -> {"I", "am",  "fine",  "thanks"}

Puedo crear una nueva clase myClass con los tres elementos:

class myClass {
    int x;
    String source;
    String target;
}

Reasigne todo a myClass, luego ordene myClass usando x . Sin embargo, esto requeriría espacios adicionales. Me pregunto si es posible hacer in place clasificación? ¡Gracias!

Answer 1

Es posible, aunque no es tan fácil de lo que parece. Hay dos opciones:

1. escriba su propio algoritmo de clasificación donde la función de intercambio de dos elementos también intercambie los elementos de las otras matrices.

   AFAIK no hay manera de extender el Array.sort estándar de manera que intercambie arreglos adicionales.

2. Utilice una matriz de ayuda con el orden de clasificación.

   • En primer lugar, necesita inicializar la matriz auxiliar con el rango {0, 1 ... indexes.Length-1} .

   • Ahora ordena la matriz auxiliar utilizando un Comparator que compara los indexes[a] con los indexes[b] lugar de a a b . El resultado es una matriz auxiliar donde cada elemento tiene el índice del elemento de la matriz fuente de donde debe provenir su contenido, es decir, la secuencia de clasificación.

   • El último paso es el más complicado. Debe intercambiar los elementos en las matrices de origen según la secuencia de clasificación anterior .
     Para operar estrictamente en su lugar, establezca su índice de cur actual a 0
     Luego toma el elemento de la quinta parte de la matriz de ayuda. Llamémoslo from . Este es el índice del elemento que debe colocarse en la cur índice después de la finalización.
     Ahora necesitas hacer espacio en la cur índice para colocar los elementos del índice from allí. Cópialos en una ubicación temporal tmp .
     Ahora mueva los elementos del índice from al índice cur . El índice from ahora es libre de ser anulado.
     Establezca el elemento en la matriz auxiliar en la cur índice en algún valor no válido, por ejemplo, -1 .
     Establezca la cur índice actual para continuar desde arriba hasta que alcance un elemento en la matriz auxiliar que ya tiene un valor de índice no válido, es decir, su punto de partida. En este caso, almacene el contenido de tmp en el último índice. Ahora ha encontrado un bucle cerrado de índices rotados.
     Desafortunadamente, puede existir un número arbitrario de tales bucles, cada uno de tamaño arbitrario. Por lo tanto, debe buscar en la matriz de ayuda el siguiente valor de índice no válido y continuar nuevamente desde arriba hasta que se procesen todos los elementos de la matriz de ayuda. Ya que terminará en el punto de inicio después de cada bucle, es suficiente incrementar la curva a menos que encuentre una entrada no válida. Así que el algoritmo sigue siendo O (n) al procesar la matriz auxiliar. Todas las entradas antes de cur son necesariamente inválidas después de completar un ciclo.
     Si la cur aumenta más allá del tamaño de la matriz auxiliar, ya está hecho.

3. Existe una variación más fácil de la opción 2 cuando se le permite crear nuevas matrices de destino.
   En este caso, simplemente asigne las nuevas matrices de destino y complete su contenido de acuerdo con los índices en su matriz auxiliar.
   El inconveniente es que las asignaciones pueden ser bastante caras si las matrices son realmente grandes. Y por supuesto, ya no está en su lugar .

Algunas notas adicionales.

• Normalmente, el algoritmo de orden personalizado funciona mejor, ya que evita la asignación de la matriz temporal. Pero en algunos casos la situación cambia. El procesamiento de los bucles de rotación de elementos cíclicos utiliza un mínimo de operaciones de movimiento . Esto es O (n) en lugar de O (n log n) de algoritmos comunes de ordenación. Entonces, cuando el número de matrices por ordenar o el tamaño de las matrices crece, el método # 2 tiene una ventaja porque utiliza menos operaciones de intercambio.

• Un modelo de datos que requiere un algoritmo de clasificación como este está en su mayor parte interrumpido por diseño. Por supuesto, como siempre, hay algunos casos en los que no puedes evitar esto.

Answer 2

Este ejemplo requiere la creación de una matriz de índices Integer, pero las matrices que se ordenarán se reordenarán en su lugar de acuerdo con array1, y las matrices pueden ser de cualquier tipo (primitivas u objetos) que permitan la indexación.

public static void main(String[] args) {
    int array1[]={5,1,9,3,8}; 
    int array2[]={2,0,3,6,1};
    int array3[]={3,1,4,5,9};
    // generate array of indices
    Integer[] I = new Integer [array1.length];
    for(int i = 0; i < I.length; i++)
        I[i] = i;
    // sort array of indices according to array1
    Arrays.sort(I, (i, j) -> array1[i]-array1[j]);
    // reorder array1 ... array3 in place using sorted indices
    // also reorder indices back to 0 to length-1
    // time complexity is O(n)
    for(int i = 0; i < I.length; i++){
        if(i != I[i]){
            int t1 = array1[i];
            int t2 = array2[i];
            int t3 = array3[i];
            int j;
            int k = i;
            while(i != (j = I[k])){
                array1[k] = array1[j];
                array2[k] = array2[j];
                array3[k] = array3[j];
                I[k] = k;
                k = j;
            }
            array1[k] = t1;
            array2[k] = t2;
            array3[k] = t3;
            I[k] = k;
        }
    }
    // display result
    for (int i = 0; i < array1.length; i++) {
        System.out.println("array1 " + array1[i] +
           " array2 " + array2[i] +
           " array3 " + array3[i]);
    }
}

Answer 3

Me pregunto si mi enfoque es válido.

    public class rakesh{

    public static void sort_myClass(myClass myClasses[]){
        for(int i=0; i<myClasses.length; i++){
            for(int j=0; j<myClasses.length-i-1; j++){
                if(myClasses[j].x >myClasses[j+1].x){
                    myClass temp_myClass = new myClass(myClasses[j+1]);
                    myClasses[j+1] = new myClass(myClasses[j]);
                    myClasses[j] = new myClass(temp_myClass);
                }
            }
        }
    }

    public static class myClass{
        int x;
        String source;
        String target;
        myClass(int x,String source,String target){
          this.x = x;
          this.source = source;
          this.target = target;
        }
        myClass(myClass super_myClass){
            this.x = super_myClass.x;
            this.source = super_myClass.source;
            this.target = super_myClass.target;
        }
    }

    public static void main(String args[]) {
        myClass myClass1 = new myClass(0,"how","I");
        myClass myClass2 = new myClass(2,"are","am");
        myClass myClass3 = new myClass(8,"today","thanks");
        myClass myClass4 = new myClass(5,"you","fine");
        myClass[] myClasses = {myClass1, myClass2, myClass3, myClass4};

        sort_myClass(myClasses);

        for(myClass myClass_dummy : myClasses){
            System.out.print(myClass_dummy.x + " ");
        }
        System.out.print("/n");
        for(myClass myClass_dummy : myClasses){
            System.out.print(myClass_dummy.source + " ");
        }
        System.out.print("/n");
        for(myClass myClass_dummy : myClasses){
            System.out.print(myClass_dummy.target + " ");
        }
    }


}

Si encuentra algún error o tiene alguna sugerencia, deje un comentario para que pueda realizar las modificaciones necesarias.

Salida

0 2 5 8
cómo estás hoy
estoy bien gracias
Proceso terminado con código de salida 0

Answer 4

Otra solución usando Collection (aumentar el uso de memoria):

Vamos a crear un mapa ordenado que simplemente será una asignación entre el índice correcto y la posición original:

public static TreeMap<Integer, Integer> sortIndex(int[] array){
    TreeMap<Integer, Integer> tree = new TreeMap<>();
    for(int i=0; i < array.length; ++i) {
        tree.put(array[i], i);
    }   
    return tree;
}

Prueba :

int[] indexes = new int[] { 0, 1, 3, 2, 4, 5 };
TreeMap<Integer, Integer> map = sortIndex(indexes);

map.keySet().stream().forEach(System.out::print); //012345
map.values().stream().forEach(System.out::print); //013245

Tenemos los índices ordenados (en la clave) y el orden del índice original como valores.

No, podemos usar esto simplemente para ordenar la matriz, seré drástico y usaré un Stream para mapear y recopilar en una List .

public static List<String> sortInPlace(String[] array, TreeMap<Integer, Integer> map) {
    return map.values().stream().map(i -> array[i]).collect(Collectors.toList());
}

Prueba :

String[] sources = "to be not or to be".split(" ");

int[] indexes = new int[] { 0, 1, 3, 2, 4, 5 };
TreeMap<Integer, Integer> map = sortIndex(indexes);

List<String> result = sortInPlace(sources, map);
System.out.println(result);

[Ser o no ser]

¿Por qué usé una List ? Principalmente para simplificar el reordenamiento, si intentamos ordenar los arreglos originales, será complicado porque necesitamos eliminar la clave / par opuestos.

2 -> 3
3 -> 2

Sin un poco de limpieza, solo intercambiaremos las celdas dos veces ... para que no haya cambios.

Si queremos reducir un poco el uso de la memoria, podemos crear otra matriz en lugar de usar la secuencia y copiar los valores por valores iterando el mapa. Esto sería posible hacer con múltiples matrices en paralelo también.

Answer 5

Puedo sugerirle que use un TreeMap o algo similar, usando su entero como clave.

static Map<Integer, myClass> map = new TreeMap<>();

Por lo tanto, cuando desee recuperar lo ordenado, solo tiene que hacer un bucle for o lo que prefiera.

for (int i : map.keyset()){
    System.out.println("x: "+map.get(i).x+"/nsource: "+map.get(i).source+"/ntarget: "+map.get(i).target);
}

Answer 6

También puedes lograr en tu camino también.

Aquí creé una ArrayList myArr y la myArr Basándome en el valor del índice y luego la volví a convertir en la matriz. Si está satisfecho con ArrayList, solo puede eliminar la conversión o desea que la Matriz sea de utilidad.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

public class  {
    public static void main(String[] args) {
        int[] indexes = new int[]{0,2,8,5};
        String[] sources = new String[]{"how", "are", "today", "you"};
        String[] targets = new String[]{"I", "am", "thanks", "fine"};
        ArrayList<myClass> myArr=new ArrayList<>();
        for(int i=0;i<indexes.length;i++) {
            myArr.add(new myClass(indexes[i], sources[i], targets[i]));
        }
        //Collections.sort(myArr,new compareIndex()); 
        // Just for readability of code 
        Collections.sort(myArr, (mC1, mC2) -> mC1.getX() - mC2.getX());

       //Conversion Part
       for (int i=0;i<myArr.size();i++){
           indexes[i]=myArr.get(i).getX();
           sources[i]=myArr.get(i).getSource();
           targets[i]=myArr.get(i).getTarget();
       }

        System.out.println(Arrays.toString(indexes));
        System.out.println(Arrays.toString(sources));
        System.out.println(Arrays.toString(targets));

    }
}
class myClass {
    private Integer x;
    private String source;
    private String target;
    public myClass(Integer x,String source,String target){
        this.x=x;
        this.source=source;
        this.target=target;
    }

    public Integer getX() {
        return x;
    }

    public String getSource() {
        return source;
    }

    public String getTarget() {
        return target;
    }
}

Answer 7

Tengo otra solución para tu pregunta:

private void reOrder(int[] indexes, String[] sources, String[] targets){
        int[] reIndexs = new int[indexes.length]; // contain index of item from MIN to MAX
        String[] reSources = new String[indexes.length]; // array sources after re-order follow reIndexs
        String[] reTargets = new String[indexes.length]; // array targets after re-order follow reIndexs
        for (int i=0; i < (indexes.length - 1); i++){
            if (i == (indexes.length - 2)){
                if (indexes[i] > indexes[i+1]){
                    reIndexs[i] = i+1;
                    reIndexs[i+1] = i;
                }else
                {
                    reIndexs[i] = i;
                    reIndexs[i+1] = i+1;
                }
            }else
            {
                for (int j=(i+1); j < indexes.length; j++){
                    if (indexes[i] > indexes[j]){
                        reIndexs[i] = j;
                    }else {
                        reIndexs[i] = i;
                    }
                }
            }
        }

        // Re-order sources array and targets array
        for (int index = 0; index < reIndexs.length; index++){
            reSources[index] = sources[reIndexs[index]];
            reTargets[index] = targets[reIndexs[index]];
        }

        // Print to view result
        System.out.println( Arrays.toString(reIndexs));
        System.out.println( Arrays.toString(reSources));
        System.out.println( Arrays.toString(reTargets));
    }

Answer 8

Todo depende del tamaño de tus arreglos. Esta solución utilizará la primera matriz para realizar la clasificación, pero realizará la permutación en múltiples matrices.
Por lo tanto, esto podría tener algunos problemas de rendimiento si el algoritmo de clasificación utilizado necesitara mucha permutación.

Aquí, tomé un algoritmo de clasificación básico en el que he agregado algunas acciones que puedo hacer durante el intercambio de dos celdas. Esto permite utilizar algunos lambda para intercambiar varias matrices al mismo tiempo en función de una matriz.

public static void sortArray( int[] array, BiConsumer<Integer, Integer>... actions ) {
    int tmp;
    for ( int i = 0, length = array.length; i < length; ++i ) {
        tmp = array[i];
        for ( int j = i + 1; j < length; ++j ) {
            if ( tmp > array[j] ) {
                array[i] = array[j];
                array[j] = tmp;
                tmp = array[i];

                // Swap the other arrays
                for ( BiConsumer<Integer, Integer> cons : actions ){
                    cons.accept( i,  j);
                }
            }
        }
    }
}

Vamos a crear un método genérico para intercambiar las celdas que podemos pasar como BiConsumer lambda (solo funciona para matrices no primitivas):

public static <T> void swapCell( T[] array, int from, int to ) {
    T tmp = array[from];
    array[from] = array[to];
    array[to] = tmp;
}

Eso permite usar para ordenar los arreglos como:

public static void main( String[] args ) throws ParseException {
    int[] indexes = new int[] { 0, 2, 8, 5 };
    String[] sources = new String[] { "how", "are", "today", "you" };
    String[] targets = new String[] { "I", "am", "thanks", "fine" };

    sortArray( indexes,
            ( i, j ) -> swapCell( sources, i, j ),
            ( i, j ) -> swapCell( targets, i, j ) );

    System.out.println( Arrays.toString( indexes ) );
    System.out.println( Arrays.toString( sources ) );
    System.out.println( Arrays.toString( targets ) );
}

[0, 2, 5, 8]
[cómo estás hoy]
[Estoy bien gracias]

Esta solución no requiere (mucha) más memoria que la que ya se utiliza, ya que no se requiere una matriz o Collection adicional.

El uso de BiConsumer<>... proporciona una solución genérica, esto también podría aceptar un Object[]... pero esto ya no funcionaría para la matriz de primitivos. Esto tiene una leve pérdida de rendimiento, por supuesto, por lo que, según la necesidad, se puede eliminar.

Para crear una solución completa, primero definamos una interfaz que también se usará como una fábrica:

interface Sorter {
    void sort(int[] array, BiConsumer<Integer, Integer>... actions);

    static void sortArrays(int[] array, BiConsumer<Integer, Integer>... actions){
        // call the implemented Sorter
    }
}

Luego, implemente una selección simple con la misma lógica que antes, para cada permutación en la matriz original, ejecutamos BiConsumer :

class SelectionSorter implements Sorter {
    public void sort(int[] array, BiConsumer<Integer, Integer>... actions) {
        int index;
        int value;
        int tmp;
        for (int i = 0, length = array.length; i < length; ++i) {
            index = i;
            value = array[i];
            for (int j = i + 1; j < length; ++j) {
                if (value > array[j]) {
                    index = j;
                    value = array[j];
                }
            }

            if (index != i) {
                tmp = array[i];
                array[i] = array[index];
                array[index] = tmp;

                // Swap the other arrays
                for (BiConsumer<Integer, Integer> cons : actions) {
                    cons.accept(i, index);
                }
            }
        }
    }
}

Deje también crear un clasificador de burbujas:

class BubbleSorter implements Sorter {
    public void sort(int[] array, BiConsumer<Integer, Integer>... actions) {
        int tmp;

        boolean swapped;
        do {
            swapped = false;
            for (int i = 1, length = array.length; i < length; ++i) {
                if (array[i - 1] > array[i]) {
                    tmp = array[i];
                    array[i] = array[i - 1];
                    array[i - 1] = tmp;

                    // Swap the other arrays
                    for (BiConsumer<Integer, Integer> cons : actions) {
                        cons.accept(i, i - 1);
                    }

                    swapped = true;
                }
            }
        } while (swapped);
    }
}

Ahora, podemos simplemente llamar a uno u otro basado en una condición simple, la longitud:

static void sortArrays(int[] array, BiConsumer<Integer, Integer>... actions){
    if(array.length < 1000){
        new BubbleSorter().sort(array, actions);
    } else {
        new SelectionSorter().sort(array, actions);
    }
}

De esa manera, podemos llamar a nuestro clasificador simplemente con

Sorter.sortArrays(indexes, 
    (i, j) -> swapCell(sources, i, j), 
    (i, j) -> swapCell(targets, i, j)
);

Caso de prueba completo en ideone (límite de tamaño debido al tiempo de espera)

Answer 9

Tres formas de hacer esto

1. Usando Comparator (necesita Java 8 más)

import java.io.*;
import java.util.*;

class Test {

public static String[] sortWithIndex (String[] strArr, int[] intIndex )
    {
     if (! isSorted(intIndex)){
        final List<String> stringList = Arrays.asList(strArr);
        Collections.sort(stringList, Comparator.comparing(s -> intIndex[stringList.indexOf(s)]));
        return stringList.toArray(new String[stringList.size()]);
       }
     else
        return strArr;
    }

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        };
    }
    return true;
}       


// Driver program to test function.
    public static void main(String args[])
    {
        int[] indexes = new int[]{0,2,8,5};
        String[] sources = new String[]{"how", "are", "today", "you"};
        String[] targets = new String[]{"I", "am", "thanks", "fine"};   
        String[] sortedSources = sortWithIndex(sources,indexes);
        String[] sortedTargets = sortWithIndex(targets,indexes);
        Arrays.sort(indexes);
        System.out.println("Sorted Sources " + Arrays.toString(sortedSources) + " Sorted Targets " + Arrays.toString(sortedTargets)  + " Sorted Indexes " + Arrays.toString(indexes));
    }
}

Salida

Sorted Sources [how, are, you, today] Sorted Targets [I, am, fine, thanks] Sorted Indexes [0, 2, 5, 8]

2. Usando Lambda (necesita Java 8 más)

import java.io.*;
import java.util.*;

public class Test {

public static String[] sortWithIndex (String[] strArr, int[] intIndex )
    {

  if (! isSorted(intIndex)) {
        final List<String> stringList = Arrays.asList(strArr);
        Collections.sort(stringList, (left, right) -> intIndex[stringList.indexOf(left)] - intIndex[stringList.indexOf(right)]);
        return stringList.toArray(new String[stringList.size()]);
  }
  else 
    return strArr;
    }

public static boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i + 1] < arr[i]) {
            return false;
        };
    }
    return true;
}  

// Driver program to test function.
public static void main(String args[])
{
    int[] indexes = new int[]{0,2,5,8};
    String[] sources = new String[]{"how", "are", "today", "you"};
    String[] targets = new String[]{"I", "am", "thanks", "fine"};   
    String[] sortedSources = sortWithIndex(sources,indexes);
    String[] sortedTargets = sortWithIndex(targets,indexes);
    Arrays.sort(indexes);
    System.out.println("Sorted Sources " + Arrays.toString(sortedSources) + " Sorted Targets " + Arrays.toString(sortedTargets)  + " Sorted Indexes " + Arrays.toString(indexes));
}

}

3. Usar listas y mapas y evitar llamadas múltiples (como en la segunda solución anterior) al método para ordenar matrices individuales

import java.util.*;
import java.lang.*;
import java.io.*;

public class Test{

    public static <T extends Comparable<T>> void sortWithIndex( final List<T> key, List<?>... lists){
        // input validation
        if(key == null || lists == null)
            throw new NullPointerException("Key cannot be null.");

        for(List<?> list : lists)
            if(list.size() != key.size())
                throw new IllegalArgumentException("All lists should be of the same size");

        // Lists are size 0 or 1, nothing to sort
        if(key.size() < 2)
            return;

        // Create a List of indices
        List<Integer> indices = new ArrayList<Integer>();
        for(int i = 0; i < key.size(); i++)
            indices.add(i);

        // Sort the indices list based on the key
        Collections.sort(indices, new Comparator<Integer>(){
            @Override public int compare(Integer i, Integer j) {
                return key.get(i).compareTo(key.get(j));
            }
        });

        Map<Integer, Integer> swapMap = new HashMap<Integer, Integer>(indices.size());
        List<Integer> swapFrom = new ArrayList<Integer>(indices.size()),
                      swapTo   = new ArrayList<Integer>(indices.size());

        // create a mapping that allows sorting of the List by N swaps.
        for(int i = 0; i < key.size(); i++){
            int k = indices.get(i);
            while(i != k && swapMap.containsKey(k))
                k = swapMap.get(k);

            swapFrom.add(i);
            swapTo.add(k);
            swapMap.put(i, k);
        }

        // use the swap order to sort each list by swapping elements
        for(List<?> list : lists)
            for(int i = 0; i < list.size(); i++)
                Collections.swap(list, swapFrom.get(i), swapTo.get(i));
    }

    public static void main (String[] args) throws java.lang.Exception{

      List<Integer> index = Arrays.asList(0,2,8,5);
      List<String> sources = Arrays.asList("how", "are", "today", "you");
      // List Types do not need to be the same
      List<String> targets  = Arrays.asList("I", "am", "thanks", "fine");

      sortWithIndex(index, index, sources, targets);

      System.out.println("Sorted Sources " + sources + " Sorted Targets " + targets  + " Sorted Indexes " + index);


    }
}

Salida

Sorted Sources [how, are, you, today] Sorted Targets [I, am, fine, thanks] Sorted Indexes [0, 2, 5, 8]

Answer 10

sin asignar valores en clase, puede lograrlo con el siguiente código:

    Integer[] indexes = new Integer[]{0,2,8,5};
    String[] sources = new String[]{"how", "are", "today", "you"};
    String[] targets = new String[]{"I", "am", "thanks", "fine"};
    Integer[] sortedArrya = Arrays.copyOf(indexes, indexes.length);
    Arrays.sort(sortedArrya);
    String[] sortedSourses = new String[sources.length];
    String[] sortedTargets = new String[targets.length];
    for (int i = 0; i < sortedArrya.length; i++) {
        int intValus = sortedArrya[i];
        int inx = Arrays.asList(indexes).indexOf(intValus);
        sortedSourses[i] = sources[+inx];
        sortedTargets[i] = targets[+inx];
    }
    System.out.println(sortedArrya);
    System.out.println(sortedSourses);
    System.out.println(sortedTargets);