Algoritmo di ordinamento in grado di gestire alcuni errori

5

Supponiamo di voler ordinare la tua collezione di film, dai preferiti agli odiati. Applica le regole di un algoritmo di ordinamento ponendo molte domande sul modulo: "Mi sono piaciuti A o B di più?"

Ora è ordinato, giusto? Logicamente, è stata posta ogni domanda necessaria per dimostrare che quando l'indice (A) < indice (B), A > B. Ma puoi dimostrare che questo è falso per almeno una coppia A e B. Sicuramente, l'algoritmo avrebbe dovuto fare più domande.

L'opinione è difficile da definire e, se un confronto è disattivato, l'intera operazione di ordinamento potrebbe risultare in qualche modo fuori luogo.

Quale algoritmo di ordinamento sceglieresti per garantire che l'elenco ordinato non sia influenzato troppo da un cattivo confronto?

    
posta Hypershadsy 17.11.2015 - 02:56
fonte

1 risposta

5

La cosa fondamentale qui è evitare di fare lo stesso confronto più di una volta. E c'è un tipo che soddisfa davvero quei criteri in un modo che è fattibile per un ordinamento umano della loro collezione di film.

Unisci l'ordinamento .

Con l'ordinamento di fusione, si suddivide in modo ricorsivo la dimensione del set su 2 (o 1). E poi ordina ognuno di questi. Ora, prendi due insiemi di 2 (l'algoritmo attuale lo prende fino a set di 1, ma lo stiamo facendo a mano e così puoi evitare quel livello di esattezza), e quindi confronti il primo elemento di ciascuno, di quelli. Se hai 3 6 e 2 4 - hai già confrontato 3 e 6 , non li confronti di nuovo. Il set risultante diventa quindi 2 3 4 6 e quindi continui a unire con il prossimo set di quattro.

Dalla pagina di Wikipedia:

Lachiavequiècheconogniconfronto,nonsistarivalutandoiconfrontiprecedenti.Quindi,sedecidicheilSottomarinoGiallotipiacepiùdell'HardDaysNightunavolta,nonlovaluterestieallafinenonfinirannotroppolontanol'unodall'altro.

Ilproblemaconmoltialtritipièchetustaichiedendocontinuamente"mi piace più di Babbo Natale conquista i marziani" ogni volta con un assortimento selezione / inserimento / bolla. E altri tipi diventano troppo complicati per essere in grado di ragionare.

Un modo per testare ciò che farebbe per alcuni post del blog molto interessanti è implementare i diversi tipi di te stesso e sovrascrivere > o compareTo nella lingua scelta. In questo metodo, aggiungi un po 'di casualità ad esso, ad esempio, +/- 10% del valore. o +/- 1% del valore.

Quindi, ordina i numeri 1 .. 100 100x e guarda fino a che punto esce fuori ogni metodo di ordinamento.

    
risposta data 17.11.2015 - 03:29
fonte

Leggi altre domande sui tag