Bucket Sort

---

Index

Related

---

Bucket Sort

def boo(A,k):
	B = [[] for _ in range(k)] # creo k secchi    θ(k) = O(n)
	m = max(A) # θ(n)
	
	for x in A             #
		i = x * k // (m+1) # θ(n)
		B[i].append(x)     #
 
	for i in range(k): #
		B[i].sort()    # θ(?)
		
	C = []             #
	for i in range(k): # θ(n)
		C.extend(B[i]) #
 
	return C

Costo secondo for: ${\sum }_{i=0}^{k-1}\text{costo di ordinamento}(B[i])$

Quando

Il bucket sort funziona bene se il numeri sono equi distribuiti su tutto l’intervallo e se non ci sono molte ripetizioni