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

1. 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())

1. Apelarea funcției de sortare

sorted_numbers = bucket_sort(numbers, d)

1. Scrierea rezultatului în fișierul de ieșire

with open("bucketsortout.txt", "w") as outfile:

   outfile.write(" ".join(map(str, sorted_numbers)))

</syntaxhighlight>