Numero di confronti utilizzando l'ordinamento di unione

Question

Se si dispone di 5 numeri distinti, quanti confronti al massimo è necessario ordinare utilizzando l'ordinamento di unione?

Answer 1

trovo la domanda interessante, così ho deciso di esplorare a fondo (con un po 'di sperimentazione in Python).

Ho scaricato mergesort.py da here e l'ho modificato per aggiungere un argomento cmp per una funzione comparatore.Poi:

import collections 
import itertools 
import mergesort 
import sys 

class CountingComparator(object): 
    def __init__(self): 
    self.count = 0 
    def __call__(self, a, b): 
    self.count += 1 
    return cmp(a, b) 

ms_histo = collections.defaultdict(int) 

for perm in itertools.permutations(range(int(sys.argv[1]))): 
    cc = CountingComparator() 
    lperm = list(perm) 
    mergesort.mergesort(lperm, cmp=cc) 
    ms_histo[cc.count] += 1 

for c in sorted(ms_histo): 
    print "%d %2d" % (c, ms_histo[c]) 

Il risultante semplice istogramma (iniziando con una lunghezza di 4, come ho fatto per lo sviluppo e il debugging questo) è:

4 8 
5 16 

Per il problema come inviato, con una lunghezza di 5 invece di 4, ottengo:

5 4 
6 20 
7 48 
8 48 

e con una lunghezza di 6 (e di un formato più ampio ;-):

7 8 
8 56 
9 176 
10 288 
11 192 

Infine, con una lunghezza di 7 (formato e ancora più ampia ;-):

9 16 
10 128 
11 480 
12 1216 
13 1920 
14 1280 

Sicuramente qualche formula combinatoria perfettamente regolare annida qui, ma mi sto trovando difficile valutare cosa potrebbe essere, sia analiticamente o esaminando i numeri. Qualcuno ha dei suggerimenti?

Answer 2

Secondo Wikipedia: Nel peggiore dei casi, merge sort fa una quantità di confronti uguale o leggermente inferiore (n ⌈lg n⌉ - 2^⌈lg n⌉ + 1)

Answer 3

Quando unione -sortando due liste di lunghezza L1 e L2, suppongo che il peggiore dei casi di confronto sia L1 + L2-1.

• Inizialmente si hanno cinque elenchi di 1 lunghezza.
• È possibile unire due coppie di liste con 2 paragoni, con conseguente liste di lunghezza 2,2 e 1.
• Quindi è possibile unire una lunga lista 2 e 1 con al più un altro 1 + 2-1 = 2 confronti, ottenendo una lista lunga 2 e 3.
• Infine unisci queste liste al massimo 2 + 3-1 = 4 confronti.

Quindi credo che la risposta è 8.

Questa sequenza di numeri risultati in quanto sopra: [2], [4], [1], [3], [5] -> [ 2,4], [1,3], [5] -> [2,4], [1,3,5] -> [1,2,3,4,5]

Modifica:

Ecco un'implementazione ingenua di Erlang. Sulla base di questo, il numero di confronti è 5,6,7 o 8 per le permutazioni di 1,5.

-module(mergesort). 

-compile(export_all). 


test() -> 
    lists:sort([{sort(L),L} || L <- permutations()]). 

sort([]) -> {0, []}; 
sort([_] = L) -> {0, L}; 
sort(L) -> 
    {L1, L2} = lists:split(length(L) div 2, L), 
    {C1, SL1} = sort(L1), {C2, SL2} = sort(L2), 
    {C3, RL} = merge(SL1, SL2, [], 0), 
    {C1+C2+C3, RL}. 

merge([], L2, Merged, Comps) -> {Comps, Merged ++ L2}; 
merge(L1, [], Merged, Comps) -> {Comps, Merged ++ L1}; 
merge([H1|T1], [H2|_] = L2, Merged, Comps) when H1 < H2 -> merge(T1, L2, Merged ++[H1], Comps + 1); 
merge(L1, [H2|T2], Merged, Comps) -> merge(L1, T2, Merged ++[H2], Comps + 1). 


permutations() -> 
    L = lists:seq(1,5), 
    [[A,B,C,D,E] || A <- L, B <- L, C <- L, D <- L, E <- L, A =/= B, A =/= C, A =/= D, A =/= E, B =/= C, B =/= D, B =/= E, C =/= D, C =/= E, D =/= E]. 

Answer 4

Cosa vi impedisce di codifica di un merge sort, mantenendo un contatore per il numero di confronti in esso, e provarlo su tutte le permutazioni di [0,1,2,3,4]?

Answer 5

http://www.sorting-algorithms.com/

Answer 6

per soli cinque numeri distinti per ordinare, il numero massimo di confronti si può avere è 8 e il numero minimo di confronti è 7. Ecco perché: -

Supponiamo che la matrice è a, b, c, d, e

divide ricorsivamente: a, b, c, d, e

divide ricorsivamente: a, b & ced & e

divide ricorsivo: una & b & ced & e

Ora, fusione che richiederà comparison-

un & b: Confronto uno a formare una, b

a, b & c: due confronti per formare a, b , c

d & e: un confronto per formare d, e

a, b, c, d, e: quattro comparatore nel peggiore dei casi o tre confronti id d è l'elemento più grande di matrice per formare a, b, c, d, e

Quindi, il numero totale di confronti sarà otto nel caso peggiore e sette nel migliore dei casi.