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>