Editing 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 &les; n &les; 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".