[C++] Ordinamento di complessità O(n)

[ramy89]

Se io ho un array di 100 con elementi che hanno valori che vanno da 0 a 100, però disordinati (es.: 9,99,51,.... fino a coprire tutti i valori), posso ordinarlo così:

int v[100];  // vetore da ordinare
int aux[100]; // vettore ausiliario
....
for(i=0;i<100;i++)
    aux[v[i]]=v[i];

Però solo in questo caso, perchè i valori sono consecutivi.E inoltre se i valori sono troppo grandi si consuma troppa memoria.

Ora mi sto scervellando per capire se si può avere un algoritmo di ordinamento con complessità O(n) anche se i valori non sono consecutivi.
Ad esempio se ho un array di 100 elementi con valori compresi tra -1000 e +1000,senza ripetizioni,posso fare così:

int v[1000];   // vettore da ordinare
...
int aux[2000];     // vettore ausiliario
int *p;
p=&aux[1000];
for(i=0;i<100;i++)
    p[v[i]]=v[i];

Però si può farlo solo per casi banali come questi, e comunque occupando tanta memoria.E inoltre una volta avuto il vettore aux di 2000 elementi, non so da dove iniziare a leggere i valori.
Mi chiedevo se è possibile ora, avendo il vettore aux, capire quali valori stampare usando un algoritmo con complessità O(n).

[LeaderGL]

Mi spiace ma se non sbaglio è matematicamente dimostrato che il limite è O(nlog n).
Il tuo algoritmo non è in grado di ordinare numeri reali, stringhe, etc. In quel modo puoi ordinare solo gli interi.

[MItaly]

Originariamente inviato da LeaderGL
Mi spiace ma se non sbaglio è matematicamente dimostrato che il limite è O(nlog n).

No. Quel limite è matematicamente dimostrato per gli algoritmi di ordinamento a confronto, classe a cui questo non appartiene.

Comunque, per capire che elementi vengono dall'array di partenza e quali invece non sono stati toccati puoi o usare un array separato di bool per segnarti quali valori sono stati effettivamente scritti, oppure scegliere un valore particolare (ad esempio INT_MAX) a cui inizializzare l'array di destinazione, in modo da poter individuare subito gli elementi che non sono stati toccati.

[ramy89]

Ah si, poi pensandoci bene ci sono riuscito.
Ho creato un array di interi,questo array (index, puntato da in) contiene 0 se a quell' indice non è associato nessun valore, 1 se a quell' indice è associato 1 valore, 2 se gli sono associato 2 valori ... con l' array di bool non si potevano contare le ripetizioni.
Quindi se index[0] vale 0, non c'è un elemento che vale 0 nell' array.Se index[10] vale 2, ci sono due elementi uguali a 10 nell' array.Scandisco tuto il vettore index e riscrivo i valori nel nuovo array.
Per ovviare al fatto che certi valori sono negativi, il puntatore a punta a un certo elemento dell' array aux.
Supponiamo che a punta a &aux[10] e chiamo a[-5], allora mi sto riferendo all' elemento aux[5].

Supponiamo che voglio ordinare la sequenza:{-9, 10, 2 , 4, 8, 8}, allora:
in[-9]=1;
in[10]=1;
in[2]=1;
in[4]=1;
in[8]=2;
con in=&index[9];


Insomma la funzione è questa:

void ordina(int *v,int n,int max, int min)
{
    int *index,*aux,*in,*a,i,k=0;
    aux=(int*)calloc((max-min),sizeof(int));
    index=(int*)calloc((max-min),sizeof(int));
    in=index;
    a=aux;
    if(min<0)
        for(i=0;i<abs(min);i++)
        {
            in++;
            a++;
        }
    for(i=0;i<n;i++)
    {
        a[v[i]]=v[i];
        in[v[i]]++;
    }
    for(i=0;i<(max-min);i++)
    {
        if(index[i]>0)
        {
            do
            {
                index[i]--;
                v[k++]=aux[i];
            }while(index[i]>0);
        }
    }
    free(index);
    free(aux);
}

Che è O(n+(max-min)), quindi se max-min è trascurabile rispetto a n, direi che è O(n).
n è la dimensione, max il massimo numero presente nell' array, min il minimo valore presente nell' array (anche negativo).
Ho concluso che è buono solo se n>>(max-min).

[LeaderGL]

Originariamente inviato da MItaly
No. Quel limite è matematicamente dimostrato per gli algoritmi di ordinamento a confronto, classe a cui questo non appartiene.

Hai ragione, avevo capito si parlasse di algoritmi di ordinamento "generici" e non di un sottoinsieme ben specifico.

[ramy89]

Ho corretto il codice:

void ordina(int *v,int n,int max, int min)
{
    int *index,*in,*a,i,k=0;
    if(min>0)
    {
        min=0;
        max++;
    }
    index=(int*)calloc((max-min),sizeof(int));
    in=index;
    if(min<0)
        for(i=0;i<abs(min);i++)
            in++;
    for(i=0;i<n;i++)
        in[v[i]]++;
    for(i=0;i<(max-min);i++)
    {
        if(index[i]>0)
        {
            do
            {
                index[i]--;
                v[k++]=i-min;
            }while(index[i]>0);
        }
    }
    free(index);
}