2700 - RadixSort

Cerința

Fiind dat un șir cu n elemente, nu neapărat distincte, se cere sortarea crescătoare a acestuia folosind metoda Radix Sort.

Date de intrare

Fișierul de intrare radixsort.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire radixsort.out va conține pe prima linie n numere naturale, anume șirul sortat, iar în consolă se va scrie un mesaj de validare al input-ului "Input valid!". În caz contrar, pe consolă se va afișa mesajul "Input invalid!".

Restricții și precizări

• 2 ⩽ n ⩽ 1.000.000;
• numerele de pe a doua linie a fișierului de intrare vor avea maximum 9 cifre.

Exemplu

radixsort.in

8

170 20 45 75 90 802 24 2

radixsort.out

2 20 24 45 75 90 170 802

Ieșire consolă

Input valid

Rezolvare

<syntaxhighlight lang="python"> import math

def getMax(n, arr):

   maxX = arr[0]
   for i in range(1, n):
       if arr[i] > maxX:
           maxX = arr[i]
   return maxX

def validateInput(n, arr):

   if n < 2 or n > 1000000:
       return False

   for i in range(n):
       if abs(arr[i]) > 999999999:
           return False

   return True

def countingSort(n, exp, arr, output):

   count = [0] * 32

   for i in range(n):
       count[(arr[i]//exp)%32] += 1

   for i in range(1, 32):
       count[i] += count[i - 1]

   for i in range(n - 1, -1, -1):
       output[count[(arr[i]//exp)%32] - 1] = arr[i]
       count[(arr[i]//exp)%32] -= 1

   for i in range(n):
       arr[i] = output[i]

def radixSort(n, arr):

   m = getMax(n, arr)

   output = [0] * n

   exp = 1
   while m // exp > 0:
       countingSort(n, exp, arr, output)
       exp *= 32

if __name__ == '__main__':

   with open("radixsort.in", "r") as fin:
       with open("radixsort.out", "w") as fout:
           n = int(fin.readline())
           arr = list(map(int, fin.readline().split()))

           if not validateInput(n, arr):
               print("Input invalid!")
               exit()
           else:
               print("Input valid!")

           radixSort(n, arr)

           for i in range(n):
               fout.write(str(arr[i]) + ' ')

</syntaxhighlight>

Explicație

Acest cod implementează algoritmul de sortare radix sort pe o listă de întregi.

Funcția `getMax(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`, și returnează cel mai mare element din listă.

Funcția `validateInput(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`, și returnează `True` dacă input-ul este valid (adică `n` este între 2 și 1000000 și toți elementele din listă au valori absolute mai mici decât 999999999) și `False` altfel.

Funcția `countingSort(n, exp, arr, output)` primește ca parametrii un număr întreg `n`, un număr întreg `exp`, o listă de `n` întregi `arr` și o listă de `n` întregi `output`. Implementează algoritmul de sortare counting sort pentru o cifră specifică (dată de `exp`), în baza 32. Folosește un array `count` de dimensiune 32 pentru a număra de câte ori apare fiecare cifră și apoi reordonează lista `arr` în ordinea specificată de cifra respectivă.

Funcția `radixSort(n, arr)` primește ca parametrii un număr întreg `n` și o listă de `n` întregi `arr`. Implementează algoritmul de sortare radix sort, iterând prin fiecare cifră a numerelor și apelând funcția `countingSort` pentru fiecare cifră în parte, începând cu cifra cea mai puțin semnificativă.

Funcția `__main__` citește input-ul din fișierul "radixsort.in", validează input-ul folosind funcția `validateInput`, sortează lista de numere folosind `radixSort`, și afișează rezultatul în fișierul "radixsort.out".