Separazione stabile per due classi di elementi in un array

Considerare il seguente problema.Separazione stabile per due classi di elementi in un array

Viene fornita una matrice di elementi appartenenti a due classi: rossa o blu. Dobbiamo riorganizzare gli elementi dell'array in modo che tutti gli elementi blu vengano prima (e tutti gli elementi rossi seguono). Il riarrangiamento deve essere fatto in modo stabile, il che significa che l'ordine relativo degli elementi blu deve essere preservato (lo stesso vale per quelli rossi).

Esiste un algoritmo intelligente che eseguirà il suddetto riorganizzazione sul posto?

Una soluzione non a posto è, ovviamente, semplice.

Una soluzione sul posto ovvia sarebbe applicare qualsiasi algoritmo di ordinamento stabile all'array. Tuttavia, l'uso di un algoritmo di ordinamento a tutti gli effetti su un array sembra intuitivo come un eccessivo, soprattutto tenendo conto del fatto che stiamo trattando solo due classi di elementi.

Tutte le idee sono molto apprezzate.

fonte

2010-05-25 AnT

È possibile farlo nel tempo O (n) e nello spazio O (1) apparentemente. Il documento Stable minimum space partitioning in linear time di Jyrki Katajainen e Tomi Pasanen afferma di essere in grado di farlo.

Google per la classificazione 0-1 stabile.

fonte

2010-05-25 17:38:08

Grazie. Purtroppo, l'articolo è disponibile solo in abbonamento, ma almeno ora so che è 1) possibile, 2) non banale :) – AnT

È disponibile gratuitamente da CiteSeer: http://citeseerx.ist.psu.edu/ viewdoc/summary? doi = 10.1.1.25.5554 –

@Ants Aasma: Grazie per il collegamento. Ho aggiornato la risposta con questo. –

Non conosco l'algoritmo O (n) ma qui è un semplice algoritmo con complessità O (n * log (n)) nel caso peggiore. Forse sarà utile.

Tagliare gli zeri dall'inizio e quelli dalla fine, sono già al loro posto. Ora l'array appare come una sequenza seguita da una sequenza di zeri seguita da una sequenza di uno e così via: 1010101010

Scambiare la prima sequenza di quelli con la prima sequenza di zeri, la terza sequenza di quelli con la terza sequenza di zeri e così via. Diventerà: 0110011001

La quantità di sequenze è diventata circa il doppio. Ripetere la procedura sopra finché l'array non viene ordinato.

Per scambiare due sequenze adiacenti, invertire il primo, quindi il secondo, quindi invertirli entrambi.

fonte

2010-05-25 19:58:42 rem

Questo è O (n^2) nel peggiore dei casi: considera 0 1 (n/2 volte) 0 1 0 1 ... 0 1. Una semplice soluzione O (nlogn) deve avere una funzione di comparazione lessicografica su (colore , indice) e utilizzare qualsiasi metodo di ordinamento utilizzando tale funzione di confronto. –

No, la quantità di passaggi è O (log (n)) nel peggiore dei casi. Ecco un esempio: http://pastebin.com/NyekVWmv – rem

Non esiste un algoritmo di ordinamento O (n * log (n)) stabile sul posto. Di solito, l'ordinamento stabile in diverse librerie è implementato usando merge sort che richiede memoria aggiuntiva O (n), si veda ad esempio l'implementazione di GNOS C++ di stable_sort e Sun Java's Arrays.sort. – rem

Questo è chiamato partizionamento stabile in C++ e per questo esiste un algoritmo standard: std::stable_partition.

L'implementazione SGI ha un comportamento adattativo a seconda della quantità di memoria disponibile:

venga eseguito in O (N) se è possibile allocare O (N) spazio
venga eseguito in O (N log N) swap in place

Mi chiedo se quest'ultima soluzione in loco utilizza un algoritmo di ordinamento stabile dietro le quinte.

fonte

2010-05-26 07:21:46

Separazione stabile per due classi di elementi in un array

risposta

Problemi correlati