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.

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

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()

           radixSort(n, arr)

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

</syntaxhighlight>

Explicație

Acest cod implementează algoritmul de sortare radix (în baza unui număr întreg fixat) pe un set de numere întregi date prin fișierul "radixsort.in" și returnează numerele sortate prin fișierul "radixsort.out".

Funcția getMax găsește valoarea maximă din lista de intrare.

Funcția validateInput verifică dacă lista de intrare are dimensiunea corectă și dacă toate elementele sunt în intervalul [-999999999, 999999999].

Funcția countingSort sortează lista de intrare în funcție de un anumit exp (baza numărului fixat) utilizând sortarea prin numărare.

Funcția radixSort utilizează celelalte funcții pentru a sorta lista de intrare prin sortarea radix.

Codul deschide fișierul "radixsort.in", citește datele de intrare, verifică dacă datele de intrare sunt valide, sortează datele de intrare utilizând sortarea radix și scrie datele de ieșire sortate în fișierul "radixsort.out".