Pseudocodice

Lezione 4 di 9 del corso Ordinamento Radix - Serie DSA di Coddy.

countingSortByDigit(array, exp):
   n = length(array)
   output = array of size n
   count = array of 10 zeros
   for each x in array:                 # tally each digit
      count[(x / exp) % 10] += 1
   for d from 1 to 9:                   # running totals -> positions
      count[d] += count[d - 1]
   for k from n-1 down to 0:            # place from the back (stable)
      d = (array[k] / exp) % 10
      count[d] -= 1
      output[count[d]] = array[k]
   return output

radixSort(array):
   max = largest value in array
   exp = 1
   while max / exp > 0:
      array = countingSortByDigit(array, exp)
      exp = exp * 10

exp è il valore posizionale: 1 per le unità, 10 per le decine, 100 per le centinaia. (x / exp) % 10 estrae quella cifra.
countingSortByDigit è un ordinamento stabile su una singola cifra: conta quante volte compare ogni cifra, trasforma questi conteggi in posizioni, quindi posiziona gli elementi dal fondo verso l’inizio per preservare l’ordine.
radixSort esegue semplicemente questo passaggio una volta per ogni cifra, fermandosi quando exp supera il numero più grande.

Provalo tu

Questa lezione non include una sfida di codice.