View source for 2720 - Bucket Sort

== Enunț ==
Metoda Bucket Sort constă în distribuirea elementelor în mai multe grupe, numite “bucket-uri”. Apoi fiecare bucket este sortat individual folosind un algoritm de sortare oarecare.

== Cerința ==
Se dă un şir cu n numere naturale ce trebuie sortat în funcţie de d. Dacă d este 1, şirul se va sorta descrescător, iar dacă este 0, se va sorta crescător.

== Date de intrare ==
Fișierul de intrare bucketsortin.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații, iar pe a treia linie se va afla d.

== Date de ieșire ==
Fișierul de ieșire bucketsortout.txt va conține pe prima linie şirul sortat în funcţie de d.

== Restricții și precizări ==

* n ≤ 10.000
* toate numerele ≤ 100.000.000
* d=0 pentru 50% din teste
* d=1 pentru 50% din teste

== Exemplu 1: ==
'''bucketsort.in'''

5

10 90 5 6 101

0

'''bucketsort.out'''

5 6 10 90 101 

== Explicație ==
Deoarece d este 0, şirul se sortează crescător

== Exemplu 2: ==
'''bucketsort.in'''

5

10 90 5 6 101

1

'''bucketsort.out'''

101 90 10 6 5 

== Explicație ==
Deoarece d este 1, şirul se sortează descrescător

== Rezolvare ==
<syntaxhighlight lang="python">
def validate_input(n, numbers, d):
    if n > 10000:
        return False
    if any(num > 100000000 for num in numbers):
        return False
    if d not in [0, 1]:
        return False
    return True

def bucket_sort(arr, d):
    n = len(arr)
    buckets = [list() for _ in range(10)]

    max_val = max(arr)
    exp = 1

    while max_val // exp > 0:
        for i in range(n):
            index = arr[i] // exp % 10
            buckets[index].append(arr[i])

        arr = []
        for bucket in buckets:
            if d == 1:
                arr = bucket + arr
            else:
                arr.extend(bucket)

            bucket.clear()

        exp *= 10

    return arr

# Citirea datelor din fișierul de intrare
with open("bucketsortin.txt", "r") as infile:
    n = int(infile.readline().strip())
    numbers = list(map(int, infile.readline().split()))
    d = int(infile.readline().strip())
# Apelarea funcției de sortare
sorted_numbers = bucket_sort(numbers, d)

# Scrierea rezultatului în fișierul de ieșire
with open("bucketsortout.txt", "w") as outfile:
    outfile.write(" ".join(map(str, sorted_numbers)))
</syntaxhighlight>