Re: [Algoritmi] Selection sort + radix sort

Messaggioda apatriarca » 03/09/2019, 17:48

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.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5290 di 5347
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 04/09/2019, 11:12

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?
ZfreS
Senior Member
Senior Member
 
Messaggio: 1797 di 1992
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Selection sort + radix sort

Messaggioda apatriarca » 05/09/2019, 00:53

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.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5292 di 5347
Iscritto il: 08/12/2008, 20:37
Località: Londra

Re: [Algoritmi] Selection sort + radix sort

Messaggioda ZfreS » 05/09/2019, 11:01

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?
ZfreS
Senior Member
Senior Member
 
Messaggio: 1800 di 1992
Iscritto il: 22/10/2016, 17:52

Precedente

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti