Sorting: Radix Sort

Algoritmi, discussioni sulle possibili implementazioni, matematica, fisica e tutti gli argomenti correlati alla programmazione
Rispondi
Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Sorting: Radix Sort

Messaggio da Barnack »

Salve, vorrei condividere con voi un codice che potrebbe tornarvi utile (ma anche no).
Tempo fa abbiamo affrontato la questione del sorting, poi ho visto due algoritmi apparentemente migliori del quicksort (che spero sia quello implementato dal sorting builtin di gm):
Radix Sort
Gravity Sort.

Ora, il gravity sort è superiperbellissimo, in pratica agita la bacchetta magica e ti ritrovi con l'array ordinato in un batter d'occhio. Però (1) non ho la più pallida idea di come funzioni, né l'ho capito, e (2) in giro si dice che questo fantomatico algoritmo sia implementabile unicamente via hardware... boh
Poi c'è il radix sort. L'ho osservato, l'ho capito, l'ho implementato... in gml!
Ora, alcune delucidazioni:
Il Radix Sort di fatto È più veloce del quicksort, e per di più da inizio a fine algoritmo non viene fatto nemmeno un singolo confronto. Sono solo una sequenza di accessi all'array da ordinare.
Dove sta la fregatura? Beh usa più ram. A quel punto, considerando che un codice blocca lo step, mi sono detto che in alcuni casi potrebbe convenire usare più ram per di contro terminare l'ordinamento più in fretta (ovvero favolette di insulsa ottimizzazione dato che nessuno metterà arrays di più di 10'000 elementi in gamemaker :asd: )

Comunque più che altro per curiosità l'ho implementato, ed ecco a voi il codice:
Spoiler

Codice: Seleziona tutto

/// array_sort_radix(array)
var array = argument0
                //print
                show_debug_message("Input unsorted array:")
                var str="";
                for(var i=0; i<array_length_1d(array); i++)
                    {
                    str+=string(string(array[i])+" ")
                    }
                show_debug_message(str)

var times = floor(log10(array[0]))+1
for(var i=1; i<array_length_1d(array); i++)
    {
    times = max(floor(log10(array[i]))+1, times)
    }
show_debug_message(times)
for(var i=0; i<times; i++)
    {
    array = array_sort_radix_sub(array, i)
    }
                //print
                show_debug_message("Sorted array:")
                var str="";
                for(var i=0; i<array_length_1d(array); i++)
                    {
                    str+=string(string(array[i])+" ")
                    }
                show_debug_message(str)
return(array)
Spoiler

Codice: Seleziona tutto

/// array_sort_radix_sub(array, digit)
//create support list
var support;
for(var i=0; i<10; i++)
    {
    support[i] = ds_queue_create()
    }

//position elements
var pow = power(10, argument1)
for(var i=0; i<array_length_1d(argument0); i++)
    {
    var place = floor((argument0[i]/pow)mod 10)
    ds_queue_enqueue(support[place], argument0[i])
    }
var count=0
for(var i=0; i<10; i++)
    {
    count += ds_queue_size(support[i])
    }
//show_debug_message("enqueued elements: "+string(count))
    
//extract elements
var ret, index=0;
for(var i=0; i<10; i++)
    {
    //repeat(ds_queue_size(support[i])) //works
    //for(var j=0; j<ds_queue_size(support[i]); j++)    //wtf why doesn't it work???
    while not ds_queue_empty(support[i]) //works
        {
        ret[index] = ds_queue_dequeue(support[i])
        index++
        }
    }
//show_debug_message("dequeued elements: "+string(index))

//destroy support list
for(var i=0; i<10; i++)
    {
    ds_queue_destroy(support[i])
    }
return(ret)
Si suppone che l'array passato contenga solo interi, non stringhe e che non sia vuoto. Il che tuttavia con gm non è molto limitante dato che anche un array di puntatori a istanza sarebbe comunque un array di interi ;)
Ho implementato la variante LSD (ovvero quella che inizia ad ordinare dalla cifra meno significativa), dato che sembra la più performante.

Per meglio comprendere l'algoritmo basta cercare "radix sort explained" su youtube, questo è solo uno dei tanti:
https://www.youtube.com/watch?v=xhr26ia4k38

I hope you enjoy!!!

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Avatar utente
cp94
Moderatore
Messaggi: 2789
Iscritto il: 04/07/2009, 19:18
Specialità: ddd
Località: Brescia
Contatta:

Re: Sorting: Radix Sort

Messaggio da cp94 »

Proprio in questo periodo stiamo studiando gli algoritmi di sorting all'università. Tra tutti quelli spiegati il Gravity sort è uno dei pochi che manca.
Da quel che ho capito però è irrealizzabile così come è stato pensato perchè richiederebbe una computazione di ogni elemento in parallelo per avere un tempo O(1)
Ogni oggetto dell'array 'cadrebbe' verso il basso, proprio come se ci fosse una gravità, e l'ordine finale è dato in base a quali elementi arrivano prima a terra.
Ho visto dei video a riguardo ma non ho capito molto :asd:
Games you should check out
Naemo
E T U S
Overgravity
Inside the Code

Immagine

Barnack
Membro attivo
Messaggi: 341
Iscritto il: 03/09/2013, 13:26
Specialità: Programmazione
Uso: GM:Studio 1.4 Pro
Contatta:

Re: Sorting: Radix Sort

Messaggio da Barnack »

Anche io ho fatto gli algoritmi di sotring all'uni, ma li abbiamo fatti tipo il primo mese...
Gravity sort, counter sort, radix sort, ovvero i tre più performanti del quicksort sono stati saltati.
Comunque ho parlato con il prof e siamo giunti alla conclusione che implementare via software il gravity sort non può avere soluzioni più efficienti di O(n^2). Tuttavia ho trovato notizie su internet riguardo a implementazioni via hardware non poi così irrealizzabili.
E non si parla di un cinesino con l'abaco che vive nel computer xD

Comunque già di per sé il funzionamento del radix sort è molto interessante

Utilizzo
GM: Studio Pro
C++ terminale
Batch
Jaschif

Spoiler
C++ WinApi / DirectX
C#



Rispondi

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti