Scelta di algoritmo di ordinamento per array di 24 elementi

[Fire-Dragon-DoL]

Allora, essendo universitario ho imparato varie cose riguardo gli algoritmi di ordinamento... ora so benissimo che il quick sort teoricamente è il migliore, ma non è il caso in cui io debba usarlo... infatti avendo un array di soli 24 elementi, è logico che quel tipo di algoritmo sia troppo pesante per cosi pochi dati. Detto questo, vorrei quindi scegliere un algoritmo migliore per ordinare il tutto...

 

Attualmente sono indeciso fra shell sort, insertion sort, merge sort (questo mi sta particolarmente antipatico)... anche il selection sort non dovrebbe andar male, comunque vi dico le prerogative per la scelta dell'algoritmo:

-L'array è di soli 24 elementi, massimo (potrebbe essere di meno...mai minore di 2, per forza :P )

-L'array sarà quasi sempre ordinato, tranne la prima volta(e pazienza perchè è a inizio battaglia) il resto delle volte giusto l'ultimo elemento (il 24esimo) dovrebbe essere in disordine (probabilmente dovrà tornare alla posizione 1)

 

Detto questo, ricordo che c'era un algoritmo che aveva il suo caso peggiore quando l'array era totalmente ordinato al contrario (questo potrebbe essere un buon algoritmo quindi?), poi invece ce ne era uno il cui caso peggiore era quando è già ordinato, considerato che io avrò una variazione di massimo 1 elemento nell'ordinamento (circa ovviamente), è probabile che questo non vada bene (l'array sarà sempre ordinato al 90%)... se avete suggerimenti quindi, sono ben accetti

[giver]

Visto che il grosso dell'array viene ordinato all'inizio e resta abbastanza invariato come composizione, invece di fare mioarray.push(nuovo_elemento_in_coda) e rieseguire l'ordinamento, si potrebbe fare direttamente mioarray.insert(posizione, nuovo_elemento) dopo aver stabilito posizione tramite ricerca binaria/dicotomica che, vista la dimensione massima dell'array, dovrebbe richiedere nel peggiore dei casi 5 passaggi.

Per il sorting iniziale puoi benissimo usare la funzione incorporata nel ruby mioarray.sort! (che equivale a mioarray = mioarray.sort), specificando il criterio di ordinamento se diverso da quello tradizionale . . .

[Fire-Dragon-DoL]

Visto che il grosso dell'array viene ordinato all'inizio e resta abbastanza invariato come composizione, invece di fare mioarray.push(nuovo_elemento_in_coda) e rieseguire l'ordinamento, si potrebbe fare direttamente mioarray.insert(posizione, nuovo_elemento) dopo aver stabilito posizione tramite ricerca binaria/dicotomica che, vista la dimensione massima dell'array, dovrebbe richiedere nel peggiore dei casi 5 passaggi.

Per il sorting iniziale puoi benissimo usare la funzione incorporata nel ruby mioarray.sort! (che equivale a mioarray = mioarray.sort), specificando il criterio di ordinamento se diverso da quello tradizionale . . .

Grazie mille del suggerimento, stavo pensando pure che una "coda" non sarebbe male (visto che il primo elemento va alla fine, sarebbe logica)...però l'accesso è lento e temo che a me serva accedervi spesso (per ilt argeting, questo array contiene la lista dei pg)

[Tio]

Uhm, ma se è solo di 24 elementi non ti conviene semplicemente usare l'ordinamento normale (non mi viene il nome ora)?

Tutti gli altri magari hanno tempi migliori, ma le differenze si notano solamente se hai liste da numeri mooolto alti.

Avevo fatto qualche mese fa delle analisi sui tempi di computazione su vari tipi di lista con qualsiasi algoritmo di ordinamento, e tutti quelli con meno di 100 elementi non impiegavano più di 0 secondi ;)

[Fire-Dragon-DoL]

Uhm, ma se è solo di 24 elementi non ti conviene semplicemente usare l'ordinamento normale (non mi viene il nome ora)?

Tutti gli altri magari hanno tempi migliori, ma le differenze si notano solamente se hai liste da numeri mooolto alti.

Avevo fatto qualche mese fa delle analisi sui tempi di computazione su vari tipi di lista con qualsiasi algoritmo di ordinamento, e tutti quelli con meno di 100 elementi non impiegavano più di 0 secondi ;)

 

AH!

Perfetto questo è interessante, perchè ero indeciso se sacrificare un pò di velocità in cambio di sicurezza (un sort a ogni fine turno) oppure fare come ha suggerito giver... ma in questa situazione preferisco un pò piu di sicurezza allora

[Darklink92]

Mi è venuto in mente un algoritmo, ma è un po incasinato, dipende se vuoi ordinarli per maggiore o minore, ma il funzionamento e sempre quello.

si fa un ciclo i che va da 0 a N(dimensione array) e un altro ciclo che va da V a N.

V all'inizio vale 0, si fa il ciclo dove si trova il piu grande tra v e n, e lo si mette nella cella v, poi v e i aumentano di 1.

penso che funzioni...

[Fire-Dragon-DoL]

Mi è venuto in mente un algoritmo, ma è un po incasinato, dipende se vuoi ordinarli per maggiore o minore, ma il funzionamento e sempre quello.

si fa un ciclo i che va da 0 a N(dimensione array) e un altro ciclo che va da V a N.

V all'inizio vale 0, si fa il ciclo dove si trova il piu grande tra v e n, e lo si mette nella cella v, poi v e i aumentano di 1.

penso che funzioni...

 

ma di algoritmi ne esistono tanti, ovviamente mi affido a quelli gia esistenti perchè sono quelli studiati maggiormente... inutile creare algoritmi propri ammenoche non siamo studiosi di algoritmi esperti (almeno per l'ordinamento di array)

 

quello che dici te somiglia molto al selection sort...comunque ti ringrazio del suggerimento, anche se penso che userò il metodo "sort" visto che effettivamente il mio array è molto compresso (24 elementi...)

Edited April 13, 2009 by Fire-Dragon-DoL

[Tio]

A questo punto, se proprio vuoi avere una computazione molto buona in ogni caso, ti consiglio di usare merge sort, visto che ha un tempo di n*logn in ogni caso ed è anche di facile implementazione.. poi non se la tua lista inizialmente è inversamente ordinata o totalmente casuale, ma in ogni caso dovrebbe essere la cosa migliore ;)

[Fire-Dragon-DoL]

A questo punto, se proprio vuoi avere una computazione molto buona in ogni caso, ti consiglio di usare merge sort, visto che ha un tempo di n*logn in ogni caso ed è anche di facile implementazione.. poi non se la tua lista inizialmente è inversamente ordinata o totalmente casuale, ma in ogni caso dovrebbe essere la cosa migliore ;)

 

Ah era il merge...perfetto si è quello giusto... il migliore su tanti elementi è il quick, ma la mia lista è quasi sempre ordinata e di pochi elementi...ritengo che il merge (quello che odio di piu) sia la migliore opzione allora...aspe il merge di facile implementazione?mi sa che ti stai confondendo con gli altri... select, insert e bubble sono molto piu corti del merge eh xD

 

Grazie a tutti dei suggerimenti sono apposto qui :P

[Tio]

Ah era il merge...perfetto si è quello giusto... il migliore su tanti elementi è il quick, ma la mia lista è quasi sempre ordinata e di pochi elementi...ritengo che il merge (quello che odio di piu) sia la migliore opzione allora...aspe il merge di facile implementazione?mi sa che ti stai confondendo con gli altri... select, insert e bubble sono molto piu corti del merge eh xD

 

Grazie a tutti dei suggerimenti sono apposto qui :P

Beh, che io ricordi non era tanto complicato da implementare (poi io l'ho usato solamente all'interno dell'esame di strutture dati): erano due funzioni e una ventina di righe di codice non troppo complicato da capire, se capisci il ragionamento che c'è dietro (divide et impera).. serve un po' di pratica con la ricorsione principalmente.

Ad ogni modo, a livello di tempi di computazione è sicuramente il migliore (volendo c'è anche radixsort, ma secondo me è molto più incasinato, oltre al fatto che serve se vuoi ordinare una lista secondo più campi chiave).

 

Però ripeto, se non vuoi impazzire con l'implementazione, puoi partire tranquillamente con quello per selezione o inserzione.. 24 elementi non sono niente: gli effetti si sentono solamente all'interno di liste da almeno oltre 500 elementi ^^

[Fire-Dragon-DoL]

Beh, che io ricordi non era tanto complicato da implementare (poi io l'ho usato solamente all'interno dell'esame di strutture dati): erano due funzioni e una ventina di righe di codice non troppo complicato da capire, se capisci il ragionamento che c'è dietro (divide et impera).. serve un po' di pratica con la ricorsione principalmente.

Ad ogni modo, a livello di tempi di computazione è sicuramente il migliore (volendo c'è anche radixsort, ma secondo me è molto più incasinato, oltre al fatto che serve se vuoi ordinare una lista secondo più campi chiave).

 

Però ripeto, se non vuoi impazzire con l'implementazione, puoi partire tranquillamente con quello per selezione o inserzione.. 24 elementi non sono niente: gli effetti si sentono solamente all'interno di liste da almeno oltre 500 elementi ^^

 

infatti...ma l'implementazione l'ho fatta (in C però) ed è piu lungo di 20 righe (il bubble saranno 15-16...non è sicuramente 20 righe l'implementazione del merge) la teoria grazie al cielo la so

 

comunque guardati il quick sort... è il piu efficace in assoluto con una complessità media di logn (il merge non ha complessità media di logn, il quick è l'unico ad averla)

 

Tra l'altro mi sorge il dubbio che tu abbia citato le capacità del quick sort e non del merge sort... è quello che ha complessità media di logn, è quello che se l'array è totalmente rigirato ha il suo caso peggiore (se è ordinato al contrario intendo)...sei sicuro di non esserti confuso? Li ho trovati su wikipedia, per questo te lo sto dicendo...il problema è che avevo letto da qualche parte che per array brevi i piu efficaci erano insertion/selection mi sa (o lo shell sort)

[Tio]

sì sì, sono abbastanza sicuro (pure io ho controllato su wikipedia, altrimenti mai che mi ricordo il tempo di computazione di tutti gli algoritmi di ordinamento XD)

come puoi vedere dalle tabelle:

quicksort: http://it.wikipedia.org/wiki/Quicksort

caso migliore: n*log, caso peggiore: n^2 (e se non sbaglio il caso peggiore si ha quando la lista è già ordinata)

 

mergesort: http://it.wikipedia.org/wiki/Merge_sort

qualsiasi caso: n*logn

[Fire-Dragon-DoL]

si solo che leggendo appare scritto "Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto. È stato ideato da Charles Antony Richard Hoare nel 1961."

 

quicksort:

 

Struttura dati 	VariabileCaso pessimo temporalmente 	Θ(n^2)Caso ottimo temporalmente 	Θ(nlogn)Caso medio temporalmente 	Θ(nlogn) confrontiCaso pessimo spazialmente 	Dipende dalle implementazioniOttimale 	Spesso

 

caso peggiore (array rivoltato al contrario, questo me lo ricordo io) è n^2

 

caso medio nlogn

 

caso ottimale nlogn

 

mergesort:

Struttura dati 	ArrayCaso pessimo temporalmente 	Θ(nlogn)Caso ottimo temporalmente 	Θ(nlogn)Caso medio temporalmente 	Θ(nlogn)Caso pessimo spazialmente 	Θ(n)Ottimale 	In alcuni casi

 

cambia il caso pessimo (l'array rivoltato al contrario) che è minore...ma è una cosa che non si verifica nella mia situazione

 

suppongo si aun problema delle volte che si verifica il caso medio...comunque ho risolto leggendo questo:

 

"Pur avendo complessità quadratica, per array piccoli è solitamente l'algoritmo di ordinamento più veloce. Un algoritmo simile all'Insertion Sort ma dalla complessità minore è lo Shell sort. Tuttavia, anche lo shell sort non è in grado di competere con la combinazione dell'insertion sort con un algoritmo di tipo divide et impera, quale il quick sort o il merge sort."

 

insertion sort quindi, che è decisamente corto da creare :P

[Sylaer]

Non ho capito perché perdi tutto questo tempo per cercare l'argoritmo di ordinamento per un'array che sai che avrà al massimo 24 elementi. Capirei se avesse 40000 elementi, ma con 24 anche un'algoritmo esponenziale te lo esegue in meno 1 secondo e a meno che tu non esegua il sorting ogni frame anche se te lo eseguisse in un secondo non sarebbe un problema.

Comunque ti conviene usare il sorting dell'array standard del ruby che sicuramente è stato ottimizzato, se invece ti piace fare tutto da te ti consiglio o il quicksort che va bene per tutto o il selection sort che è il più facile da implementare. Con un array di 24 elementi uno vale l'altro.

 

Ah... mi sembra che il caso peggiore del quicksort non sia l'array ordinato al contrario, anzi mi sa che è uno dei casi migliori perché in una passata lo ordina tutto.

[Fire-Dragon-DoL]

Non ho capito perché perdi tutto questo tempo per cercare l'argoritmo di ordinamento per un'array che sai che avrà al massimo 24 elementi. Capirei se avesse 40000 elementi, ma con 24 anche un'algoritmo esponenziale te lo esegue in meno 1 secondo e a meno che tu non esegua il sorting ogni frame anche se te lo eseguisse in un secondo non sarebbe un problema.

Comunque ti conviene usare il sorting dell'array standard del ruby che sicuramente è stato ottimizzato, se invece ti piace fare tutto da te ti consiglio o il quicksort che va bene per tutto o il selection sort che è il più facile da implementare. Con un array di 24 elementi uno vale l'altro.

 

Ah... mi sembra che il caso peggiore del quicksort non sia l'array ordinato al contrario, anzi mi sa che è uno dei casi migliori perché in una passata lo ordina tutto.

 

Il sort interno di ruby è stato ottimizzato, ma generalmente viene scelto il quicksort a questo fine (tra l'altro è un array di puntatori ad oggetti), per quello volevo mettere su l'insertion sort...a parere di wikipedia è quello che funziona meglio su array piccoli...il tempo non lo sto perdendo perchè mentre posto sul forum continuo il progetto (ho scritto altre 7 pagine di organizzazione...sto a quota 11, ora devo organizzare la grafica e poi il database, che sono ancora deciso come creare)

 

Comunque ero interessato a ottimizzarlo al massimo perchè purtroppo verrà chiamato veramente spesso (si, anche ogni frame ci potrebbe essere il rischio...mi serve per aggiornare le barrette degli atb che possono variare mentre aumentano) quindi l'ottimizzazione massima è quasi indispensabile ^^

 

tra l'altro sempre da wikipedia

"l'insertion sort è efficiente se l'input è già abbastanza ordinato."

Edited April 13, 2009 by Fire-Dragon-DoL

[Sylaer]

Scusa se te lo chiedo, ma cosa vuoi fare esattemente?

[Fire-Dragon-DoL]

Scusa se te lo chiedo, ma cosa vuoi fare esattemente?

 

una barra laterale per visualizzare l'atb (24 pg in battaglia, non chiedermi come che non voglio andare troppo affondo per non dire le cose troppo in giro...comunque se hai giocato a ff12 dovresti intuire come posso far giocare 12 pg :P ) ovviamente 24 comprende pure i mostri (12 giocatori)... verrà visualizzata di lato come quella di ffx, ma sarà un vero e proprio atb (come quello di ff7)... ovviamente alcuni pg avranno la barra che si muove piu veloce di altri...quindi ogni "frame" (supponendo che faccio che ogni frame l'atb si incrementa di uno, ma potrei farlo ogni 2-3 frame) se alcuni pg aumentano di piu pixel invece che di 1 ovviamente supereranno altri nella barra... il risultato sarà che inizialmente è disordinata ma in breve tenederà ad essere sempre ordinata... o comunque gran parte di essa

 

ecco perchè devo sortare spesso ed ecco perchè sono 24 elementi :P

[Sylaer]

Vuoi fare un'array dove ogni "atb step", cioè ogni volta che viene aggiornata l'atb, ti ordina gli elementi nell'array (che sono i pg) a seconda di quanto è piena la barra dell'atb dell'elemento, giusto?

Ma per cosa ti serve?

Se vuoi sapere quali pg hanno l'atb piena basta che tu faccia un controllo quando fai lo "atb step" e se risulta che l'atb ha raggiunto una certa soglia o processi subito l'azione del pg o metti il pg in un array che poi verrà processato dopo.

[Fire-Dragon-DoL]

Vuoi fare un'array dove ogni "atb step", cioè ogni volta che viene aggiornata l'atb, ti ordina gli elementi nell'array (che sono i pg) a seconda di quanto è piena la barra dell'atb dell'elemento, giusto?

Ma per cosa ti serve?

Se vuoi sapere quali pg hanno l'atb piena basta che tu faccia un controllo quando fai lo "atb step" e se risulta che l'atb ha raggiunto una certa soglia o processi subito l'azione del pg o metti il pg in un array che poi verrà processato dopo.

 

Non ti preoccupare non è la prima volta che programmo so cosa intendi, ma io voglio ottenere tutt'altra cosa...questo mi serve per ottenere un effetto grafico...immagina di avere una lista di questo tipo

 

 

1)--------------

2)-----------

3)------

4)----

 

Ora il 3 supera il 2 perchè accellera piu veloce, quindi si scambiano di posizione

 

tutto ciò durante il progress dell'atb...per ottenere un effetto grafico di spostamento della barra...ed avere la lista sempre ordinata :P