Come faccio a capire il numero minimo di swap per ordinare un elenco sul posto?

Considera il problema di manipolare un elenco in uno stato diverso in cui conosci lo stato finale.

1. Trova ogni "sottografo incluso" più grande di uno (lo spiegherò più avanti).
2. Trova la somma delle lunghezze dei sottografi e sottrai il numero di sottografi.
3. Esiste la tua risposta per il numero di scambi.

Un "sottografo incluso" è un sottoinsieme minimo dell'intero in cui ogni elemento dell'elenco iniziale si trova anche nell'elenco finale.

Quindi se costruisci un sottografo con gli indici 4,5 e 9 dallo stato iniziale e hanno i valori 10, 20 e 30 allora perché sia un "sottografo incluso", dovresti riuscire a trovare i valori dallo stato finale con gli indici 4, 5 e 9 e quei valori dovrebbero essere 10, 20 e 30 (sebbene non necessariamente in questo ordine).

Considera questo:

a b c d f e
    |
    v
b a d f c e

Questo ovviamente richiederebbe 3 swap. (a < = > b, c < = > d, c < = > f)

Applicando l'algoritmo sopra, ha:

1. 3 "sottografi allegati", ([a, b], [c, d, f], [e])
2. 2 sottografi con più di un elemento ([a, b], [c, d, f])
3. Ci sono 5 elementi in tutti quei sottografi
4. 5 - 2 == la risposta.

Diventa un po 'più difficile quando vuoi fare il numero minimo di swap per ottenerlo nell'ordine ordinato, tuttavia, non è impossibile.

1. Trova l'indice di ordinamento ordinato di ogni elemento nell'elenco, se non vuoi spostare alcun dato, allora questo è n ^ 2 volte.
2. Trova i "sottografi allegati".
3. Scambia gli elementi nell'elenco per ottenere l'ordine corretto, ma scambia solo gli elementi all'interno dello stesso sottografo.

Quindi spero che tu possa vedere che non è impossibile fare il numero minimo di swap per arrivare all'ordine ordinato, ma non ne vale la pena, perché richiede un numero ridicolo di confronti. Basta usare heapsort.

Che ne dici di un ordinamento di selezione semplice?

1. Trova il minimo (A C D Q R Z E)
2. Scambia se min ()! = primo elemento
3. Ripeti con (C D Q R Z E)
4. Conta il numero di scambi.

Nel tuo esempio:

1. A C D sono già in ordine, quindi non è necessario lo scambio.
2. Primo scambio richiesto per mettere E in posizione (quindi la matrice diventa A C D E R Z Q)
3. Q è il minimo di R Z Q, di nuovo lo scambio per posizionarlo (quindi l'array diventa A C D E Q Z R)
4. R è il minimo di Z R, scambiare per mettere in atto. (infine la matrice diventa A C D E Q R Z).

... così semplice senza grafici:)

Che ne dici di questo: ogni volta che scambi due elementi agli indici i ej lo registri come una tupla (i, j) da qualche parte. Una volta che l'elenco è ordinato, fai fuori un libro di algebra astratta e leggi le permutazioni, in particolare le trasposizioni. C'è una decomposizione del ciclo canonico per le permutazioni e una volta che hai la decomposizione canonica puoi andare a capire come estrarre un insieme minimo di trasposizioni da esso. Sto pensando ad un algoritmo avido in cui espandi ogni ciclo in un numero minimo di trasposizioni e ci dovrebbe essere solo un modo per farlo, ma non sono sicuro se questo darà il numero minimo di trasposizioni nel complesso. La mia algebra astratta non è buona come in passato, quindi potresti provare a porre questa domanda anche sullo stack di teoria dei cs.

Non esattamente, è possibile utilizzare memoria aggiuntiva, ma è di dimensioni costanti. la complessità computazionale dipende dall'algoritmo utilizzato.