Algoritmi - Nuovo algoritmo di ordinamento

Forum - Algoritmi - Nuovo algoritmo di ordinamento - Pagina 3

Pagine: [ 1 2 3 4 ]

pierotofy (Admin)
Guru^2

Messaggi: 6230
Iscritto: 04/12/2003

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

lorelapo (Ex-Member)
Expert

Messaggi: 355
Iscritto: 28/02/2007

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

lorelapo (Ex-Member)
Expert

Messaggi: 355
Iscritto: 28/02/2007

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

Hacker (Member)
Guru

Messaggi: 1014
Iscritto: 06/06/2006

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...

lorelapo (Ex-Member)
Expert

Messaggi: 355
Iscritto: 28/02/2007

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.

()
Newbie

Messaggi:
Iscritto:

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!