Andrada378 at 22:43, 3 January 2024

2024-01-03T22:43:20Z

← Older revision		Revision as of 22:43, 3 January 2024
Line 1:		Line 1:
			== 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.		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~~'''''~~		== 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.		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~~'''''~~		== 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.
	Fișierul de intrare ~~bucketsort~~.in 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 bucketsort.out 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~~		== Date de ieșire ==
			Fișierul de ieșire bucketsortout.txt va conține pe prima linie şirul sortat în funcţie de d.

	d=~~1 pentru 50% din teste~~		== Restricții și precizări ==

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

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

	5		5
Line 33:		Line 27:
	0		0

	bucketsort.out		'''bucketsort.out'''

	5 6 10 90 101		5 6 10 90 101

	~~'''''~~Explicație~~'''''~~		== Explicație ==

	Deoarece d este 0, şirul se sortează crescător		Deoarece d este 0, şirul se sortează crescător

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

	5		5
Line 51:		Line 43:
	1		1

	bucketsort.out		'''bucketsort.out'''

	101 90 10 6 5		101 90 10 6 5

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

	~~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

	~~'''''Rezolvare'''''<syntaxhighlight lang="python">~~
	def bucket_sort(arr, d):		def bucket_sort(arr, d):
	n = len(arr)		n = len(arr)
	buckets = [list() for _ in range(10)]		buckets = [list() for _ in range(10)]

	~~# Determinăm valoarea maximă din listă pentru a determina numărul de cifre~~
	max_val = max(arr)		max_val = max(arr)
	exp = 1		exp = 1
Line 76:		Line 76:
	for bucket in buckets:		for bucket in buckets:
	if d == 1:		if d == 1:
	arr = bucket + arr ~~# adăugăm la început pentru sortare descrescătoare~~		arr = bucket + arr
	else:		else:
	arr.extend(bucket) ~~# adăugăm la sfârșit pentru sortare crescătoare~~		arr.extend(bucket)

	bucket.clear()		bucket.clear()
Line 91:		Line 91:
	numbers = list(map(int, infile.readline().split()))		numbers = list(map(int, infile.readline().split()))
	d = int(infile.readline().strip())		d = int(infile.readline().strip())

	# Apelarea funcției de sortare		# Apelarea funcției de sortare
	sorted_numbers = bucket_sort(numbers, d)		sorted_numbers = bucket_sort(numbers, d)

Andrada378: Pagină nouă: 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 bucketsort.in conține pe prima linie numărul n, iar pe a...

2023-12-28T14:34:30Z

Pagină nouă: 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 bucketsort.in conține pe prima linie numărul n, iar pe a...

New page

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 bucketsort.in 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 bucketsort.out 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 bucket_sort(arr, d):
n = len(arr)
buckets = [list() for _ in range(10)]

# Determinăm valoarea maximă din listă pentru a determina numărul de cifre
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 # adăugăm la început pentru sortare descrescătoare
else:
arr.extend(bucket) # adăugăm la sfârșit pentru sortare crescătoare

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>

2720 - Bucket Sort - Revision history

Andrada378 at 22:43, 3 January 2024