Java: ordinamento inverso senza mantenere l'ordine

Question

Aggiorna : in effetti, l'unica soluzione accettabile per questo problema sarebbe ordinare l'array in ordine crescente e quindi invertirlo.

Sia S la seguente sequenza di eventi:

Event | Time
  A   | 0:00
  B   | 0:01
  C   | 0:01
  D   | 0:02

Ho un semplice comparatore per ordinare S , che ordina gli elementi in base al valore tempo .

public int compare(Event e1, Event e2) {

    // Reverse sorting. 
    // _sortOrder is set outside this method.
    if(SORT_DESCENDING.equals(_sortOrder))
        return e2.getTime() - e1.getTime(); /* time is long */

    return e1.getTime() - e2.getTime();
}

Il problema è: quando l'ordinamento è crescente, S è ordinato correttamente: A, B, C, D.

Ma quando uso l'ordinamento inverso, S diventa D, B, C, A:

Event | Time
  D   | 0:02
  B   | 0:01 /* B and C should be reversed */
  C   | 0:01
  A   | 0:00

Ciò accade perché l'algoritmo di ordinamento predefinito mantiene l'ordine originale per gli elementi con lo stesso valore time .

Quindi, come posso ordinarlo al contrario senza mantenere l'ordine originale?

Nota: so che posso ordinare S in ordine crescente e semplicemente ripristinarlo, ma sfortunatamente questa non è un'opzione nel mio caso.

Answer 1

L'algoritmo di ordinamento è corretto: 0,01 è 0,01. A meno che non ci sia qualcosa che non ci stai dicendo. Se tuttavia desideri l'esatto ordine inverso di un ordinamento crescente, ordinali in ordine crescente e usa Collections.reverse () . Con questo intendo:

List<SomeObject> list = ...;
Collections.sort(list, myComparator);
Collections.reverse(list);

che ti darà esattamente quello che vuoi.

Ma se l'inversione non è un'opzione, rimangono solo due opzioni:

1. Renderlo in modo che nessun elemento possa essere " uguale a " ;. Includere un altro campo o aggiungerne uno sintetico (come l'indice corrente o la chiave primaria se è un numero). Questo ti darà un ordine riproducibile, coerente e speculare; o
2. Implementa il tuo algoritmo di ordinamento. Questo non è raccomandato in quanto è semplicemente troppo soggetto a errori.

Ora, prima di dire che non puoi invertire (perché?), lascia che ti chieda come stai ordinando? se stai usando Collections.sort () considera il codice sorgente (Java 6u10):

public static <T extends Comparable<? super T>> void sort(List<T> list) {
Object[] a = list.toArray();
Arrays.sort(a);
ListIterator<T> i = list.listIterator();
for (int j=0; j<a.length; j++) {
    i.next();
    i.set((T)a[j]);
}
}

Quindi copia la raccolta in una matrice, ordina quella matrice e quindi la utilizza per riordinare la raccolta.

Sei sicuro di non poterti permettere un'inversione?

Answer 2

Cosa stai usando per ordinare? La mia ipotesi è che sia qualcosa che garantisca che è un ordinamento stabile - e ne hai due valori uguali, per quanto riguarda il confronto.

Esistono ulteriori ordini che puoi imporre in questo caso? Puoi facilmente dire quale evento verrebbe per primo nell'ordine crescente? In tal caso, usa anche questo confronto originale, quindi l'ordine decrescente inizierà a funzionare in modo naturale.

MODIFICA: poiché i tuoi dati non contengono ulteriori informazioni sugli ordini, non sarei sorpreso se fossero restituiti in ordini diversi quando hai eseguito nuovamente la stessa query in Oracle. Tuttavia, se ti preoccupi solo dell'ordine in questo caso particolare, ti suggerisco di aggiungere un campo in più nella tua rappresentazione in memoria Java per memorizzare l'indice originale nell'elenco caricato - mentre leggi i dati, tieni traccia di quanti hai letto e assegnato il campo di conseguenza. Quindi puoi usarlo quando ordini.

Answer 3

Mi manca qualcosa o non potresti semplicemente usare il nome dell'evento (o qualunque sia A, B, C e D) come chiave di ordinamento secondaria? Estendi il tuo comparatore a qualcosa del tipo:

public int compare(Event e1, Event e2) {
    int cmp = e1.getTime() - e2.getTime(); // compare times
    if (cmp == 0)  // if times are equal, compare names instead
        cmp = e1.getName().compareTo(e2.getName());
    return SORT_DESCENDING.equals(_sortOrder)? -cmp : cmp;
}

Answer 4

Penso che ciò che vuoi veramente sia un criterio di ordinamento secondario, in modo tale che tu possa ordinare gli oggetti anche se i criteri di ordinamento primario li considerano uguali. Nel tuo esempio, i criteri primari sarebbero il tempo e il secondario sarebbe Evento. In questo modo, non devi fare affidamento sul fatto che gli articoli siano in un certo ordine prima di eseguire l'ordinamento, il che rende le cose molto più facili.

Se davvero non hai un criterio secondario, probabilmente avresti bisogno di esaminare algoritmi di ordinamento stabili e instabili, come menzionato da Jon Skeet.

Answer 5

Un altro modo ma non risolvere il problema:

List<SomeObject> list = ...;
Collections.sort(list, Collections.<SomeObject>reverseOrder());

Answer 6

Perché è 0:01 più piccolo / più grande di 0:01 o perché dovrebbe essere ordinato in un modo molto speciale se sono entrambi uguali?

Non stai cercando un ordinamento inverso, stai cercando un ordinamento inverso, mi dispiace. :)

Answer 7

L'ordinamento sembra corretto, basta confrontare i nomi se e1.getTime () == e2.getTime ().

Answer 8

A seconda della rapidità con cui si confrontano due elementi rispetto a scambiarli, potresti semplicemente fare un ordinamento stabile decrescente, quindi invertire solo tutte le regioni di "uguale". elementi.