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

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]) + ' ')

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".