bucket sort

Bucket sort
Bucket sort, ou bin sort, é um algoritmo de ordenação que funciona dividindo um vetor em um número finito de recipientes. Cada recipiente é então ordenado individualmente, seja usando um algoritmo de ordenação diferente, ou usando o algoritmo bucket sort recursivamente. O bucket sort tem complexidade linear (Θ(n)) quando o vetor a ser ordenado contém valores que são uniformemente distribuídos.
Bucket sort funciona do seguinte modo:
1. Inicialize um vetor de “baldes”, inicialmente vazios.
2. Vá para o vetor original, incluindo cada elemento em um balde.
3. Ordene todos os baldes não vazios.
4. Coloque os elementos dos baldes que não estão vazios no vetor original.

Vetor desordenado, antes do bucket sort

Vetor ordenado , depois do bucket sort

Algoritmo

inicio

funcao bucker_sort (fvetor[] : inteiro, n: inteiro) /// declaração das variáveis da função i,j : inteiro cont[n] : inteiro

para i de 1 ate n faca cont[i] = 0 /// zera o vetor auxiliar fimpara

para i de 1 ate n faca (cont[fvetor[i]])=(cont[fvetor[i]])+1 /// fimpara

para cont[i] de 1 ate 0 faca (cont[i]=cont[i]-1) fvetor[j=j+1]=i fimpara

fimfuncao

inicio /// declaração das variaveis vetor[100] : inteiro num, i : inteiro

escreva(" digite a quantidade de numeros :") leia(num) /// coleta quantos números terão o vetor escreva("digite os elementos para serem ordenados") para i de 1 ate num faca leia(vetor[i]) /// coleta os números que serão salvos no vetor que deverão ser ordenados fimpara

escreva("vetor antes de ser ordenados") para i de 1 ate num faca escreva(vetor[i]) /// imprimi na tela os números do vetor digitados fimpara

escreva("vetor depois de ser ordenados")