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, 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 &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
; 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".