Algoritmo distributivo que divide elementos em buckets, ordena cada um, e concatena o resultado.
Bucket Sort é um algoritmo de ordenação que não compara elementos diretamente. Em vez disso, distribui os elementos em "baldes" baseado nos seus valores, ordena cada balde, e concatena tudo. A magia acontece quando os elementos estão bem distribuídos. Se cada bucket tem poucos elementos, ordenar cada um é rápido. O resultado final é quase linear. O algoritmo brilha para números de ponto flutuante entre 0 e 1 com distribuição uniforme. Fora desse cenário, pode degradar para O(n²) se todos os elementos caírem no mesmo bucket.
“Bucket Sort é O(n) quando os dados estão uniformemente distribuídos. É perfeito para floats entre 0 e 1.”
n é o número de elementos, k é o número de buckets. Linear quando bem distribuído.
Distribuição O(n). Ordenação de cada bucket O(n/k × log(n/k)), totalizando O(n) quando uniforme. Concatenação O(k).
Precisa de espaço para os n elementos distribuídos em k buckets.
Elementos uniformemente distribuídos entre os buckets.
Todos os elementos no mesmo bucket. Degrada para o sort interno.
| Algoritmo | Tempo | Espaco | Estavel | Melhor Para |
|---|---|---|---|---|
| Bucket Sort(atual) | O(n+k) | O(n+k) | Sim | Floats uniformemente distribuídos |
| Bubble Sort | O(n²) | O(1) | Sim | Arrays pequenos |
| Counting Sort | O(n+k) | O(k) | Sim | Inteiros em faixa conhecida |
| Radix Sort | O(d×n) | O(n+k) | Sim | Inteiros com número fixo de dígitos |
Pratique respondendo a perguntas comuns de entrevistas tecnicas. Clique em uma pergunta para iniciar uma sessao de pratica com IA.
1def bucket_sort(arr):Definição2 if len(arr) == 0:Caso Base3 return arr4 5 n = len(arr)Inicialização6 buckets = [[] for _ in range(n)]7 8 for num in arr:Distribuição9 index = min(int(num * n), n - 1)10 buckets[index].append(num)11 12 for bucket in buckets:Ordenação13 bucket.sort()14 15 result = []Concatenação16 for bucket in buckets:17 result.extend(bucket)18 19 return result20