[Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 19/07/2019, 18:21

Buonasera! Sto studiando il radix sort. Ho capito come funziona, ma non riesco a implementarlo. Per prima cosa ho trovato un modo per sapere quante volte un'algoritmo di ordinamento dovrà ordinare i numeri (unità, decine, centinaia ecc), ma non sò come implementare la parte che consiste nel prenderli, ordinarli e poi salvari per ripartire da quella configurazione per ordinare le cifre successive. Ho letto che bisogna farlo usando il counting sort, che io avevo implementato tempo fa in maniera semplice, ma ora ho trovato una soluzione che non conoscevo, vorrei capirla insieme a voi:
Codice:
#include <iostream>
using namespace std;
const int RANGE = 9;

void countingSort(int arr[],int n,int RANGE){
    int count[9]={0};
    int i;
    int out[n];
   
   
    for(i=0;i<n;i++)
    ++count[arr[i]];
   
    for(i=1;i<RANGE;i++)
    count[i]+=count[i-1];
   
   
   
    for(i=n-1;i>=0;i--){
        out[count[arr[i]]-1]=arr[i];
        --count[arr[i]];
    }
   
    for(i=0;i<n;i++)
    arr[i]=out[i];
   
   
   
}
void print(int arr[],int n)
{
    cout<<"array : ";
    for(int i=0;i<n;i++)
    cout<<arr[i]<<' ';
    cout<<endl;
}

int main() {
int arr[]={1, 4, 1, 2, 7, 5, 2};
    int n=sizeof(arr)/sizeof(arr[0]);
   
    print(arr,n);
   
    countingSort(arr,n,RANGE);
   
    print(arr,n);
   
return 0;
}


Vorrei che mi aiutaste a capire come funziona questo codice, poi devo riuscire a integrarlo nel radix sort. Grazie in anticipo!
ZfreS
Senior Member
Senior Member
 
Messaggio: 1778 di 1971
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Selection sort + radix sort

Messaggioda apatriarca » 20/07/2019, 01:35

Il codice che hai scritto da per scontato che il numero massimo inserito nell'array sia 9. Se passi un valore maggiore di 9 alla funzione questa andrà probabilmente in crash.

Per quanto riguarda il funzionamento del counting sort. Crei prima di tutto una tabella in cui conti il numero di volte che un particolare numero è presente nel tuo array. Per esempio, il tuo array porterebbe prima di tutto alla seguente tabella:
012345678
022011010

Un particolare valore nel tuo array andrà inserito nella posizione corrispondente alla somma di tutti i valori precedenti nella tabella. Per cui calcoliamo queste somme. Sommiamo ogni valore con quello precedente partendo da 1 fino al valore massimo ottenendo la tabella:
012345678
024456677

Questa tabella ci dice che gli elementi con valore uguale a 2 andranno scritti agli indici 2 e 3 (maggiori o uguali al valore precedente e minore di quello corrente). In pratica partiamo dall'ultimo elemento del nostro array, un 2, e lo scriviamo in posizione 3 (4 - 1). A questo punto diminuiamo questo valore a 3 in modo che la prossima volta che incontriamo un due troviamo scritto 3 nella tabela e scriviamo un 2 all'indice 2 (cioè 3 - 1).
apatriarca
Moderatore
Moderatore
 
Messaggio: 5272 di 5329
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 20/07/2019, 16:54

Scusa ma non ho capito questo: agli indici 2 e 3 dell'ultima tabella ci sono dei 4, non 2. Non so se sia un errore tuo o sbaglio io ad interpretare, ma quest'idea delle somme è tutt'altro che intuitiva. La mia implementazione è diversa, più naturale, forse meno efficiente. Per questo motivo volevo capire la classica implementazione del count sort.
ZfreS
Senior Member
Senior Member
 
Messaggio: 1779 di 1971
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Selection sort + radix sort

Messaggioda apatriarca » 20/07/2019, 17:15

Quale sarebbe la tua interpretazione del counting sort? È semplicemente quella di iterare sull'array e scrivere un certo numero di elementi con il valore desiderato? Se è così allora non funziona quando quello che vuoi ordinare non è limitato alla singola chiave. Supponi per esempio di star ordinando un gruppo di persone in base al loro punteggio in un qualche gioco. L'associazione tra il punteggio e la persona deve rimanere anche nell'array ordinato..

Considera per il momento l'elemento che ha valore 4. Vuoi sapere dove inserirlo nell'array ordinato usando la tabella iniziale. L'idea è quella di contare il numero di elementi di valore inferiore e quindi inserire il valore 4 nella posizione libera consecutiva. Ci sono 2 elementi con valore 1 e 2 con valore 2, per cui dovrai inserire il valore 4 all'indice 4. Questa idea funziona per il caso semplice in cui c'è un solo elemento con un particolare valore. Se ci sono più elementi con lo stesso valore devi capire in quale delle possibili posizioni dedicate a quel valore devi inserire il tuo elemento. La soluzione è quella di partire dalla fine dell'array e ogni volta che incontri un elemento con un valore, lo inserisci nell'ultima posizione disponibile per quel valore e decrementi il valore nella tabella in modo che il successivo elemento vada nella posizione precedente. In altre parole quella tabella contiene l'indice successivo all'ultimo elemento di quel valore da inserire nell'array di destinazione.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5273 di 5329
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 22/07/2019, 09:33

Nella mia implementazione ho semplicemente contato quante volte si presentava un numero in un array a parte allocato dinamicamente, poi andavo a mettere nell'array originale i numeri in questo modo: se per esempio ci fossero due elementi con valore 1 e tre con valore 2, andavo a mettere nell'array tante volte quell'elemento quante volte è stato contato quindi nelle prime due posizione dell'array originale ci andava l'1 e nelle successive tre posizioni i 2, fino alla fine dell'array. Direi che come idea sia più semplice. Comunque adesso ho capito come funziona. Ora ho bisogno di capire come funziona il radix sort. Si può riutilizzare il counting sort o bisogna implementare il bucket sort?
ZfreS
Senior Member
Senior Member
 
Messaggio: 1780 di 1971
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 31/07/2019, 10:53

Ok, tagliamo la testa al toro. Cerchiamo di capire come funziona questo codice del radix sort:
Codice:
#include <iostream>
using namespace std;


int getMax(int arr[], int size)
{
    int max = arr[0];
    for (int i = 1; i < size; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

void stampaArray(int arr[], int num_ele)
{
    for (int i = 0; i < num_ele; i++)
        cout << arr[i] << endl;
}

void radixSort(int arr[], int dim)
{
    int i = 0;
    int v[10];
    int contatore[10];
    int exp = 1;
    int max = getMax(arr, dim);
   
    while (max / exp > 0)
    {
        for (i = 0; i < 10; i++)
            contatore[i] = 0;

        for (i = 0; i < dim; i++)
            contatore[(arr[i] / exp) % 10]++;

        for (i = 1; i < dim; i++)
            contatore[i] = contatore[i - 1];

        for (i = dim - 1; i >= 0; i--)
        {
            v[contatore[(arr[i] / exp) % 10] - 1] = arr[i];
            contatore[(arr[i] / exp) % 10]--;
        }

        for (i = 0; i < dim; i++)
            arr[i] = v[i];

        exp = exp * 10;
    }
}

int main()
{
    int v[] { 127, 324, 173, 4, 38, 217, 134 }; 
    int size = sizeof(v) / sizeof(v[0]);
    radixSort(v, size);
    stampaArray(v, size);
   
    return 0;
}

IL while dovrebbe servire a scandire tutte le cifre dei numeri nell'array. Nel while il primo for azzera tutto l'array mentre l'ultimo copia gli elementi da un vettore all'altro. Ma non capisco cosa facciano gli altri tre for centrali. Potreste aiutarmi a capire per favore?
ZfreS
Senior Member
Senior Member
 
Messaggio: 1785 di 1971
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Selection sort + radix sort

Messaggioda apatriarca » 02/08/2019, 03:48

L'idea del radix sort è quello di considerare i numeri come una sequenza di "cifre" e di ordinare i numeri ordinando una cifra per volta. Ti mostro l'idea con un esempio. Supponiamo di voler ordinare i numeri da 0 a 99 ma di non voler usare un array di 100 valori. Consideriamo semplicemente le cifre decimali per comodità in questo caso.

Prendiamo i seguenti valori:
3522722971378509


Si inizia considerando la cifra meno significativa (quella delle unità in questo caso) e si passa poi a quelle più significative. Siccome il counting sort usato per l'ordinamento è stabile, cioè preserva l'ordine di elementi con la stessa chiave, alla fine avrai gli elementi ordinati correttamente nel nostro esempio hai i seguenti passaggi (prima riga sequenza di partenza, poi ordinamento in base alle unità e ordinamento in base alle decine):

3522722971378509
5022213352797789
2913222735507897


Nei computer le cifre sono spesso i byte che formano il numero intero (per cui base 256 in un certo senso) ma non è necessario e ho visto implementazioni che usavano invece ad esempio 11 bit. Al contrario del codice che hai scritto di solito non si calcola i limiti effettivi dei dati, ma si usa semplicemente quelli del tipo di dati che si sta usando. Quindi nel caso di interi a 32 bit e l'uso dei byte come cifre ci sono 4 passaggi del counting sort. Nota che questi ordinamenti sono principalmente utili con un grosso numero di valori. Con pochi valori altri algoritmi sono spesso più veloci.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5278 di 5329
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 02/08/2019, 10:35

Il codice che ho pubblicato prima del tuo post fa proprio questo, la mia difficoltà è nel capire cosa facessero questi cicli for:
Codice:
for (i = 0; i < dim; i++)
            contatore[(arr[i] / exp) % 10]++;

        for (i = 1; i < dim; i++)
            contatore[i] = contatore[i - 1];

        for (i = dim - 1; i >= 0; i--)
        {
            v[contatore[(arr[i] / exp) % 10] - 1] = arr[i];
            contatore[(arr[i] / exp) % 10]--;
ZfreS
Senior Member
Senior Member
 
Messaggio: 1786 di 1971
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Selection sort + radix sort

Messaggioda apatriarca » 02/08/2019, 15:05

contatore è la "tabella" del counting sort. Contiene cioè il numero di volte che una cifra compare nell'array. Inoltre arr[i]/exp)%10 è semplicemente una particolare cifra del numero. Il secondo ciclo è sbagliato in quanto, in modo simile al counting sort, è necessario sommare i valori. Devi quindi scrivere += al posto di uguale. L'ultimo ciclo inserisce i valori dell'array nell'array di destinazione come nel counting sort.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5279 di 5329
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 03/09/2019, 10:37

Scusate se riprendo la discussione dopo parecchio tempo, ma ora che ho più tempo ritorno sulla programmazione. Rileggendo tutto ho capito i cicli for, ma non capisco una cosa: perchè nel terzo ciclo si somma l'elemento i dell'array con il suo precedente. Vorrei capire perchè è necessario questo passaggio. Ho consultato molti siti, ma nessuno si soffermava a spiegare il perchè di questa "somma cumulativa".
ZfreS
Senior Member
Senior Member
 
Messaggio: 1794 di 1971
Iscritto il: 22/10/2016, 17:52

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti