[Algoritmi] Counting Sort modificato

[eusebi1]

L'algoritmo di Counting Sort utilizza nell'ultimo ciclo un vettore di supporto per contenere l'0utput generato. L'algoritmo è in place. Alcuni autori riportano un suo miglioramento in cui viene eliminato il vettore di output finale.

Qui il vettore b per capirci.
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/176_b.gif

Nonostante le mie ricerche non sono riuscito a trovare una sua versione.

Quanlcuno lo ha mai incontrato o ne ha una versione?

[hamming_burst]

E' abbastanza facile modificare il codice se si conosce il funzionamente di counting sort.
Anzi il codice che hai riportato sembra preso dal Cormen, che mi pare complichi qualche operazione, o cmq fa qualche trasformazione di conteggio in più.
vado un po' a memoria, ma penso se cerchi meglio trovi qualche altra versione, che cmq si basa sulla mera definizione di conteggio e che si lavora sugli interi.

counting sort(int[] A,int n,int k)

for int i=0 to k
    C[i] = 0
for int i=0 to n //conta le occorrenze
    C[A[i]]++

//scrive C[i] volte in A il valore i e decrementa
int j=0
for int i =0 to k {
    while(C[i]>0){
        A[j]=i
        C[i]--
        j++
   }
}

Prova, dovrebbe essere cmq corretto...

[eusebi1]

Si, mi chiedo però se è stabile. Ammettiamo non lo sia ( dubbio: In questo caso copiamo dei valori alla fine ha senso parlare di algoritmo stabile ) ne esiste una variante stabile? Ovvero esiste un counting sort stabile e in place ?

[hamming_burst]

"eusebi":Si, mi chiedo però se è stabile.

cosa intenti per "stabile"?
forse intendi che la complessità dipende dal valore intero massimo (sull'ordine della massima rappresentazione binaria) contenente nell'array A da ordinare?

Ovvero esiste un counting sort stabile e in place ?

quello che ti ho proposto è all'incirca in-place, infatti sovrasrive l'array A di input rispetto a quello che hai riportato che utilizza due array. Deve ovviamente esserci un array di appoggio C perchè se no dove memorizzi i conteggi?
Se no a cosa ti riferisci con stabile e in-place?

[eusebi1]

Sono d'accordo sul fatto che sia tra virgolette diciamo in place.
Stabile risulta un algoritmo che mantiene l'ordine dei fattori. Diventa rilevante per quelli che hanno valore uguale ovviamente.

Del tipo: 132 5(A)5(B) 7
resta 123 5(A)5(B) 7 e non diventa 123 5(B)5(A) 7

CountingSort nella prima versione ,con il vettore b in più, lo era e di qui la sua utilità in altri algoritmi
come radixsort. Nel caso del tuo ,che è in place, non so dire però.

[hamming_burst]

"eusebi":
Stabile risulta un algoritmo che mantiene l'ordine dei fattori. Diventa rilevante per quelli che hanno valore uguale ovviamente.

Il tuo esempio e discorso è poco chiaro.

cmq i due algoritmi sono equivalenti.

Se noti il tuo sottrai a C le varie occorrenze e poi le somma. nella versione che ho proposto somma a blocchi per tutto l'array A in varie passate.

[apatriarca]

Supponiamo di avere una lista di coppie (chiave, valore) e di volerle ordinare rispetto alla chiave. Supponiamo inoltre che ci possano essere più valori per una stessa chiave. Se si ordina questa lista con un algoritmo di ordinamento stabile l'ordine relativo tra coppie con la stessa chiave si mantiene mentre non è garantito nel caso di un algoritmo non stabile. Il counting sort, definito nel modo opportuno, è stabile.

Ecco un piccolo esempio di utilizzo di questa proprietà. Supponiamo di voler ordinare una lista di coppie (chiave, valore) prima rispetto alla chiave e poi rispetto al valore (in ordine lessicografico insomma). Un metodo è certamente quello di definire un ordinamento particolare che confronta prima la chiave e poi il valore, ma possiamo anche effettuare l'ordinamento in due tempi. Possiamo infatti ordinare per prima cosa rispetto ai valori e poi usare un algoritmo di ordinamento stabile e ordinare rispetto alle chiavi.

Altro esempio. Supponiamo di avere una lista di oggetti ordinati rispetto ad un valore che cambia nel tempo (con una frequenza abbastanza alta) e di visualizzarla in una GUI. Supponiamo che ci siano due oggetti dello stesso valore, il cui valore rimane costante per un po' di tempo. Se l'algoritmo di ordinamento usato è stabile, la posizione dei due oggetti rimane più o meno costante, in caso contrario potrebbero scambiarsi in continuazione rendendo difficile l'utilizzo della GUI.

[hamming_burst]

ok direi che ora mi è chiaro cosa si intende! (grazie apatriarca e ben tornato )
La versione che ho proposto, allora non saprei se mantiene tale stabilità, l'ho scritta un po' a memoria. Vedrò di recuperarmi il libro da cui studiai e vedere che dice...
Ma penso comunque di sì, perchè sono certo che gli algoritmi sono definiti equivalenti.

[eusebi1]

Grazie. Alla fine l'algoritmo proposto da hamming_burst mi pare il più naturale. Non so se ha senso parlare di stabilità in questo caso. Lo sarebbe se al posto dell'array di appoggio C[] avessimo un array di linked list ? Inseriremmo in ordine ed estrarremmo in ordine.