Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Nuovo algoritmo di ordinamento
Forum - Algoritmi - Nuovo algoritmo di ordinamento - Pagina 3

Pagine: [ 1 2 3 4 ] Precedente | Prossimo
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6223
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 0:46
Venerdì, 04/05/2007
Ingegnoso, una variante del Selection Sort che potrebbe funzionare, anche se ho riscontrato un errore nell'algoritmo.

Per capire il problema consideriamo un ipotetico array di 5 elementi:

0 - 1 - 2 - 3 - 4 (indice)
-----------------
8 - 2 - 3 - 5 - 6 (valore)
-----------------

Alla prima esecuzione della funzione ORDINA gli elementi 8 e 2 vengono risconosciuti rispettivamente come maggiore e minore all'interno dell'array. I loro indici sono pertanto 0 e 1. Avviene il primo scambio che mette il minore all'inizio dell'array:


0 - 1 - 2 - 3 - 4 (indice)
-----------------
2 - 8 - 3 - 5 - 6 (valore)
-----------------

Tuttavia al momento di sostituire il maggiore con la fine dell'array accade questo:


0 - 1 - 2 - 3 - 4 (indice)
-----------------
2 - 8 - 3 - 5 - 6 (valore)
-----------------

Abbiamo detto prima che l'indice del maggior elemento era 0 quindi il numero 2 viene spostato anzichè il numero 8. Risultando in:


0 - 1 - 2 - 3 - 4 (indice)
-----------------
6 - 8 - 3 - 5 - 2 (valore)
-----------------

A questo punto la funzione chiama in ricorsione se stessa restringendo i bordi dell'array non prendendo più in considerazione gli indici 0 e 4, ritornando un risultato errato.

Ultima modifica effettuata da pierotofy il 04/05/2007 alle 3:51


Il mio blog: https://piero.dev
PM
Avatar
lorelapo (Ex-Member)
Expert


Messaggi: 355
Iscritto: 28/02/2007

Segnala al moderatore
Postato alle 12:00
Sabato, 05/05/2007
Si lo sapevo, scusa se non ti ho risposto subito ma mi sono sentito male di nuovo a scuola e ho passato la notte all'ospedale. Pensavo bastasse "if(max!=inizio)" ma va modificato con "if(max==inizio)max->min;" così funziona ed è ancora abbastanza veloce.
//Posto la modifica, ma senza commenti fanno più confusione che altro

void SWAP(a,b)
aus->a;
a->b;
b->aus;
END SWAP

void ORDINA(vet[], inizio, fine)
if(inizio>=fine) RETURN;
i;
min->inizio;
max->fine;
for i->inizio; i<fine; i++
if(vet]i]>vet[max])max=i;
else if(vet]i]<vet[min])min=i;
end for
SWAP(@vet[min],@vet[inizio]);
if(max==inizio)max->min;
SWAP(@vet[max],@vet[fine]);
ORDINA(vet,inizio+1,fine-1);
RETURN;
END ORDINA

Ultima modifica effettuata da lorelapo il 05/05/2007 alle 12:05
PM
Avatar
lorelapo (Ex-Member)
Expert


Messaggi: 355
Iscritto: 28/02/2007

Segnala al moderatore
Postato alle 18:56
Martedì, 08/05/2007
Siccome io non conosco tutti i linguaggi del mondo e non conosco nemmeno tutti i più famosi e nemmeno tutti quelli che il sito supporta vorrei fare una richiesta di aiuto, tutti quelli che conoscono un lang diverso dal C potrebbero pubblicare una implementazione del mio algoritmo nel dato lang ?

ps: possibilmente il programma dovrebbe essere pubblicato con il nome Ord+nome del linguaggio es.
implementazione in Ruby = OrdRuby

PM
Avatar
Hacker (Member)
Guru


Messaggi: 1014
Iscritto: 06/06/2006

Segnala al moderatore
Postato alle 15:46
Giovedì, 10/05/2007
boh,dipende se i linguaggi lo permettono e quanto tempo c'è a disposizione per l'implementazione da parte del membro...

PM
Avatar
lorelapo (Ex-Member)
Expert


Messaggi: 355
Iscritto: 28/02/2007

Segnala al moderatore
Postato alle 14:55
Venerdì, 11/05/2007
Tutto il tempo dell'universo, basta che funzioni e penso che apparte i kinguaggi script, markup e concorrenti tutti dovrebbero poterlo implementare.

PM
Avatar
()
Newbie


Messaggi:
Iscritto:

Segnala al moderatore
Postato alle 14:45
Domenica, 12/10/2008
beh secondo me col selection-sort non centra molto visto che il selection-sort opera in modo diverso...al massimo ha qualche piccola somiglianza con il quick-sort ma rispetto a quest'ultimo è sicuramente peggiore...non voglio affligerti ancora di più di quanto non lo sei già ma il tuo algoritmo ha una complessità di circa "n al quadrato" (per precisione un O grande di n al quadrato) il che vuol dire che è uno dei peggiori che ci possa essere!

PM
Avatar
eddiewrc (Member)
Expert


Messaggi: 560
Iscritto: 30/04/2006

Segnala al moderatore
Postato alle 20:30
Domenica, 12/10/2008
beh dai confrontato con questo: http://it.wikipedia.org/wiki/Stupid_sort sembra anche efficiente!!! complessità O(n n!) :rotfl::D:rotfl::D:rotfl::D:rotfl::D:rotfl::D:k::rotfl::D:k:

PM
Avatar
Daf (Normal User)
Pro


Messaggi: 78
Iscritto: 27/06/2009

Segnala al moderatore
Postato alle 11:18
Lunedì, 29/06/2009
Io provo a implementarlo in pascal ma c'è una versione più leggibile:rofl: e magari in C++?
(se chiedo troppo solo in C ma con commenti)

PM
Pagine: [ 1 2 3 4 ] Precedente | Prossimo