[Algoritmi] Selection sort + radix sort

Prima della somma comulativa hai che il vettore contiene il numero di valori uguali all'indice. Il numero di valori uguali o inferiori a tale indice sarà quindi uguale alla somma di tutti i valori che lo precedono. Per calcolarlo inizi a sommare il primo e secondo valore e scrivi il risultato nella seconda posizione. Sommi quindi il terzo e il nuovo secondo valore (uguale alla somma del primo e del secondo valore originario) insieme e lo scrivi nella terza posizione. Procedendo in questo modo vedi che sommi sempre il nuovo valore con la somma di tutti i precedenti ottenendo quindi il risultato richiesto per procedere con l'esercizio.

Ok, ho capito, ma poi una volta ottenuta la somma come la si deve sfruttare? Qual'è la proprietà matematica dietro questa strategia di fare la somma?

Le somme ti forniscono l'intervallo di indici all'interno del quale devi inserire i valori che appartengono ad un particolare bucket. Forse una animazione come quella che trovi alla link https://www.cs.usfca.edu/~galles/visualization/RadixSort.html può aiutarti meglio che una mia spiegazione.

L'animazione ha chiarito tutto, però vorrei dire che l'idea di fare le somme per ottenere l'intervallo degli indici non mi sembra un'idea molto intuitiva, come lo si può dedurre senza avrlo mai letto in un libro?