Gestire numeri decimali in algoritmo stile counting sort

di il
12 risposte

Gestire numeri decimali in algoritmo stile counting sort

Ciao ragazzi.Stavo pensando ad un algoritmo per l'ordinamento dei numeri e mi è venuta l'idea che ho scoperto poi essere alla base del counting sort.Io praticamente faccio questo:

-Scorro l'array originario ed inserisco i numeri positivi in un array di appoggio nelle posizioni relative al valore stesso dei numeri (es. Il numero 5 nella posizione 5).Faccio lo stesso con i numeri negativi rendendoli però positivi e mettendoli in un altro array di appoggio.
-Alla fine di questo processo ripasso da destra a sinistra l'array dei numeri negativi e li inserisco nell'array di uscita in posizioni successive partendo da zero e rendendoli nuovamente positivi.Faccio lo stesso con l'array dei numeri positivi scorrendolo però da sinistra verso destra ed inserendo i numeri nell'array di uscita partendo dall'ultima posizione più 1 così che si vanno ad affiancare ai numeri negativi inseriti in precedenza.


Ho anche sviluppato un meccanismo che gestisce i numeri doppioni o triploni ecc. che però non vi descrivo in quanto non è importante considerando cosa voglio chiedervi:Come posso fare ad inserire dei numeri decimali all'interno di questo algoritmo?Esiste un meccanismo per poterli gestire?

12 Risposte

  • Re: Gestire numeri decimali in algoritmo stile counting sort

    Primo problema: devi ordinare {9223372036854775808, 1}. Il tuo algoritmo lo supporta?

    La risposa non e' banale

    Nota: il numero grande NON E' messo li a caso!

    Per i numeri decimali: no, il tuo algoritmo non puo' funzionare.
    Immagina di ordinare {1e-300, 1}

    Ma ci sono sistemi alternativi

    Gli algoritmi di ordinamento SONO IMPORTANTISSIMI, e sono stati inventati un sacco di modi per fare l'ordinamento.
    Comprese strutture dati auto ordinanti (cioe' tu inserisci l'elemento nella struttura dati e questo viene automaticamente ordinato).

    Studia di piu'!
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    migliorabile ha scritto:


    Primo problema: devi ordinare {9223372036854775808, 1}. Il tuo algoritmo lo supporta?
    Diciamo che questo è lo stesso problema che c'è nel counting sort. Si può applicare solo su insiemi con un dominio molto limitato.

    Più che altro mi piacerebbe vedere la soluzione che gestisce i valori duplicati. Dubito che si possa inventare qualcosa di diverso dal counting sort.


    Per i numeri decimali, potresti usare al posto degli array di int (intendo i 2 array "di supporto") degli array di liste di float; in ogni lista metti tutti i float che hanno come parte intera l'indice dell'array contenente quella lista. Calcola però che se hai tanti float racchiusi in un dominio molto ristretto, le liste diventano lunghe e la complessità non è più lineare.
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    merecol ha scritto:


    Stavo pensando ad un algoritmo per l'ordinamento dei numeri e mi è venuta l'idea
    Direi che il problema di fondo è proprio questo. Gli algoritmi di ordinamento sono un problema studiato intensivamente dal punto di vista applicativo fin dalla fine del 1800, dai tempi in cui un certo Herman Hollerith (fondatore della "famosissima" Tabulating Business Machine, naturalmente, forse un po' meglio nota col nuovo assetto sociale assunto nel 1924: International Business Machines Company ), già amanuense nel censimento USA 1880, a fronte di tale anacronistica fatica si era fatto venire l'idea brillante di ordinare ed elaborare elettromeccanicamente delle schede perforate, che codificheranno i dati a partire dal successivo censimento (1890). Da allora in poi hanno lavorato al problema le più brillanti menti matematiche ed informatiche per oltre un secolo.

    Pertanto è bene non farsi venire alcuna "idea", se non quella di prendere in mano un buon manuale di algoritmica e studiarlo da cima a fondo. In questo modo sarebbe stato più facile scoprire le parentele immediate di counting e radix sort, come il pigeonhole e il bucket sort, per i quali esistono facili estensioni ai valori floating point. A maggior ragione quando si parte da un livello come questo, la probabilità di "inventare" qualcosa è parecchio inferiore rispetto alla famosa probabilità della cinquina al lotto.
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    Domandona MAW: ma da quando si utilizza il termine algoritmica?

    Mi suona cosi' male

    Un po' come avvocatessa, ministra, ecc ...

    Manco la Treccani contiene la definizione di algoritmica (ti propone algoritmico che mi suona normale )

    Quindi, il manuale di algoritmica dovrebbe essere invece (piu' correttamente) manuale di algoritmi
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    migliorabile ha scritto:


    Comprese strutture dati auto ordinanti (cioe' tu inserisci l'elemento nella struttura dati e questo viene automaticamente ordinato).
    Oddio... adesso... non esageriamo... non è che si ordinano automaticamente, è l'inserimento che lo fa.

    A dir la verità qualche anno fa avevo letto di metodi simil-analogici per sfruttare certe caratteristiche fisiche (essenzialmente applicazioni della legge di faraday-lenz) per ordinamenti (almeno teoricamente) o(kn): la fantasia su questo argomento è stata davvero molto ampia.
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    migliorabile ha scritto:


    Domandona MAW: ma da quando si utilizza il termine algoritmica?
    Il termine è tecnicamente valido sul duplice binario del calco e dell'analogia secondo la Crusca. Si tratta di uno dei pochissimi casi validi di reimportazione (da algorithmics), sovrapposto comunque alla modellazione analogica di un aggettivo sostantivato col suffisso "-ica", il quale, preceduto dalle più varie eufoniche singole o sillabiche, si fonda sempre su "tecnica" e sottintende comunque il greco t???? (tékne) contraddistinguendo numerosissime altre discipline, dalla burotica alla domotica, dalla cibernetica all'aritmetica, dalla retorica all'elettronica alla meccanica alla linguistica... mentre praticamente ogni altra translitterazione di anglicismi tecnici è realmente emetica all'orecchio del cultore della lingua del Sì, in questo caso si tratta di un non raro duplice rimbalzo (in questo caso si parte dalla storpiatura in latino tardo amanuense del nome del matematico persiano Abu Ja'far Mohammed ibn-Mûsâ al-Khwârizmî) latino->inglese->italiano rafforzato da una analogia.

    L'algoritmo è propriamente l'oggetto di studio dell'algoritmica, così come il meccanismo è oggetto di studio della meccanica (applicata), eccetera.

    Allo stesso modo, nella letteratura matematica si parla di combinatorica assai più spesso e volentieri che di "combinatoria", pur essendo quest'ultimo un validissimo latinismo, fin dai tempi del grande Gian-Carlo Rota, sempre per il medesimo tipo di analogia.


    In merito alle varie ondate di entusiasmo per annunci di supposte prestazioni strepitose inerenti algoritmi di ordinamento su architetture di calcolo non convenzionali, si veda anche questo post dell'anno 2006.
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    Quindi la conclusione è che sarebbe meglio studiare gli algoritmi già esistenti e non cercare di inventarne di nuovi:):):)Comunque era solo un esperimento che stavo facendo partendo da un'idea che mi era venuta in mente:)
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    dvaosta ha scritto:


    migliorabile ha scritto:


    Primo problema: devi ordinare {9223372036854775808, 1}. Il tuo algoritmo lo supporta?
    Diciamo che questo è lo stesso problema che c'è nel counting sort. Si può applicare solo su insiemi con un dominio molto limitato.

    Più che altro mi piacerebbe vedere la soluzione che gestisce i valori duplicati. Dubito che si possa inventare qualcosa di diverso dal counting sort.


    Per i numeri decimali, potresti usare al posto degli array di int (intendo i 2 array "di supporto") degli array di liste di float; in ogni lista metti tutti i float che hanno come parte intera l'indice dell'array contenente quella lista. Calcola però che se hai tanti float racchiusi in un dominio molto ristretto, le liste diventano lunghe e la complessità non è più lineare.
    Potresti spiegarmi meglio il metodo che hai descritto per i numeri decimali?Poi un'altra domanda:se io volessi eliminare dinamicamente le posizioni con valore "null" che inevitabilmente si vanno a creare nell'array come si potrebbe fare?
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    merecol ha scritto:


    dvaosta ha scritto:


    migliorabile ha scritto:


    Primo problema: devi ordinare {9223372036854775808, 1}. Il tuo algoritmo lo supporta?
    Diciamo che questo è lo stesso problema che c'è nel counting sort. Si può applicare solo su insiemi con un dominio molto limitato.

    Più che altro mi piacerebbe vedere la soluzione che gestisce i valori duplicati. Dubito che si possa inventare qualcosa di diverso dal counting sort.


    Per i numeri decimali, potresti usare al posto degli array di int (intendo i 2 array "di supporto") degli array di liste di float; in ogni lista metti tutti i float che hanno come parte intera l'indice dell'array contenente quella lista. Calcola però che se hai tanti float racchiusi in un dominio molto ristretto, le liste diventano lunghe e la complessità non è più lineare.
    Potresti spiegarmi meglio il metodo che hai descritto per i numeri decimali?
    Ogni cella dell'array contiene una lista di tutti i decimali che hanno come parte intera l'indice di quella cella, e tale lista è ordinata.
    Poi un'altra domanda:se io volessi eliminare dinamicamente le posizioni con valore "null" che inevitabilmente si vanno a creare nell'array come si potrebbe fare?
    Non lo puoi fare, se vuoi mantenere una complessità lineare. E' appunto il motivo per cui il counting sort ha problemi con domini ampi e/o sparsi.
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    Se invece non volessi mantenere la complessità lineare come si potrebbe fare?C'è un metodo?
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    Otterresti qualcosa tipo l'insertion sort ma con una lista di appoggio.

    Insomma, lascia stare. Ci sono cose molto più interessanti e importanti da studiare invece di perdere tempo a inventarti un algoritmo di ordinamento che tanto, se ha delle prestazioni ragionevoli, sicuramente è già stato scoperto da qualcun altro.
  • Re: Gestire numeri decimali in algoritmo stile counting sort

    dvaosta ha scritto:


    Otterresti qualcosa tipo l'insertion sort ma con una lista di appoggio.

    Insomma, lascia stare. Ci sono cose molto più interessanti e importanti da studiare invece di perdere tempo a inventarti un algoritmo di ordinamento che tanto, se ha delle prestazioni ragionevoli, sicuramente è già stato scoperto da qualcun altro.
    È solo un'esercitazione spinta dalla curiosità:):) Non voglio inventarne uno da zero,sarebbe molto pretenzioso:):):)Se hai tempo e voglia potresti spiegarmi il metodo che mi hai accennato?Comunque grazie mille per la pazienza e le risposte:)
Devi accedere o registrarti per scrivere nel forum
12 risposte