Array semi-ordinato

Array semi-ordinato

Messaggioda marco il ven 9 gen 2009, 16:55

Trovare un algoritmo lineare di ordinamento per ordinare un array di n interi in cui al più \sqrt n non sono nella corretta posizione.
The first rule of first order logic is you can't talk about first order logic
marco
 
Messaggi: 26
Iscritto il: mer 2 lug 2008, 16:27

Messaggioda MindFlyer il mar 21 apr 2009, 8:51

Per esempio, insertion sort.
"Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win."
Sun Tzu ~ The Art of War
Avatar utente
MindFlyer
 
Messaggi: 92
Iscritto il: ven 13 giu 2008, 18:09

Messaggioda MindFlyer il mar 21 apr 2009, 21:46

No scherzavo, insertion sort non funge in alcuni casi, quindi il problema è ancora ufficialmente aperto. :rolleyes:
A proposito, dove l'hai trovato?
"Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win."
Sun Tzu ~ The Art of War
Avatar utente
MindFlyer
 
Messaggi: 92
Iscritto il: ven 13 giu 2008, 18:09

Messaggioda MindFlyer il mer 22 apr 2009, 4:01

Ok, forse ci siamo. Non ho tempo di controllare che funzioni davvero, né di vedere se il metodo si può semplificare, ma ecco l'idea.

1) Partizioniamo il vettore negli O(\sqrt n) segmentini ordinati massimali, con costo O(n) operazioni, e creiamo un puntatore per ogni segmentino, che inizialmente punta al primo elemento del segmentino stesso.
2) Mettiamo in una coda con priorità gli indici dei segmentini, ordinati secondo il loro elemento minimo, con costo O(\sqrt n \log n) operazioni.
3) Siano i e j i primi due indici della coda. Prendiamo gli elementi del segmentino i-esimo (a partire dall'elemento puntato dal puntatore i-esimo) che sono minori dell'elemento puntato dal puntatore j-esimo, e mettiamoli nel vettore di output. Incrementiamo il puntatore i-esimo del numero di elementi inseriti.
4) Aggiorniamo la coda con priorità, spostando i in modo da mantenere l'ordine tra gli elementi indicati dai puntatori. Questo costa O(\sqrt n) operazioni.
5) Torniamo al punto 3, fino ad esaurimento scorte.

L'analisi dovrebbe essere questa: le varie invocazioni del passo 3 richiedono complessivamente O(n) operazioni, perché ogni elemento del vettore viene esaminato una volta sola, e per ogni elemento si fanno un numero costante di operazioni. Il passo 4 viene invocato O(\sqrt n) volte, perché vi sono al più due "salti" per ogni elemento non ordinato del vettore. Quindi anche il passo 4 richiede complessivamente O(n) operazioni.
"Victorious warriors win first and then go to war, while defeated warriors go to war first and then seek to win."
Sun Tzu ~ The Art of War
Avatar utente
MindFlyer
 
Messaggi: 92
Iscritto il: ven 13 giu 2008, 18:09


Torna a Algoritmi e strutture dati

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite