Bucket sort - formando o algoritmo

RuanCS · 23 de maio de 2016

Ola galera bom dia. Então, sou novo aqui e gostaria de tirar uma duvida com vocês.

Estou estudando Algoritmos na faculdade, sou novo na area de programação e algumas coisas estou entendendo, mas na hora de aplicar, fico confuso.

Enfim, o Tema do trabalho é bucket sort e eu queria formar um algoritmo simples de atribuição de valores de um vetor B com o seu tamanho formado pelo maior elemento do vetor A. Acho que é assim que funciona o bucket sort. Porém, não consigo fazer o mesmo. Tentei alguns procedures e functions mas declarar vetor no Pascalzim mas sempre dava erro de .

Program buckets ;
var
 
 VetA: array[1..10] of integer;
 VetB: array[1..10] of integer;
 ii,j, maior: integer;
 
Begin  
    maior:=0;
    ii:=0;    
 for ii:= 1 to 10 do
      begin
          writeln( 'escreva o ',ii ,' numero ');   // entrada de dados no vetor
         readln(VetA[ii]);
             if VetA[ii]> maior then  
             maior:= VetA[ii];
    end;     
    clrscr;      
      
      for j:= 1 to maior do
          VetB[j]:=j;
          

End.

A duvida é: com esse comando o meu vetor B fica com seu limite como o maior elemento do vetor A?
quem puder me ajudar, agradeço. Preciso entregar o trabalho até quarta :\

Na parte que informei sobre usar function foi justamente para formar um array de inteiros sem limite de tamanho até ser informado pelo usuario, porém aparecia a mensagem. "array nao declarada" ou algo assim...

Simon Viegas · 25 de maio de 2016

Olá.

Se possível, poste o enunciado do trabalho, pode ser que ajude...

Então, em relação a sua dúvida:

Em 23/05/2016 às 08:45, RuanCS disse:

A duvida é: com esse comando o meu vetor B fica com seu limite como o maior elemento do vetor A?
quem puder me ajudar, agradeço. Preciso entregar o trabalho até quarta :\

Se você definir que os dados de entrada vão de 1 a 10 (usuário vai digitar nessa faixa) vai sim... ex.: maior igual a 7... o vetor só vai ser utilizado até essa posição...logo tendo uma espécie de limite "lógico", ou seja, o vetor continuará com 10 posições e "gastando" memória para esse tamanho, mas limitado ao uso de "7". Para ficar mais claro, você poderia usar um "tamB" para armazenar o "tamanho de B".

Obs.: Creio que dá para configurar um "vetor de tamanho dinâmico", mas acho por hora não tem problema usar um ver "maior" e limitar seu tamanho durante o uso... essa parte dinâmica poderia ficar para depois.

Em relação ao Bucket Sort em si, creio que seja necessário se aprofundar mais... eu particularmente não conhecia. O que entendi é que de alguma forma, os elementos são separados de um "balde maior" em "baldes individuais" (bucket) seguindo alguma regra (ex.: em números de 0 a 100, poderia dividir em dezenas... um balde de 0 a 9, outro de 10 a 11 etc), daí os baldes são ordenadas individualmente por um método de ordenação qualquer, (que poderia ser o próprio Bucket Sort, nesse caso utilizando recursividade*) e posteriormente o conteúdos dos baldes é derramado, em ordem, um a um, no balde maior, resultando na ordenação completa.

Na internet, encontrei uma explicação que acho que pode ser útil: (no caso utilizando baldes que recebem apenas um valor, em vez de uma faixa)

Tem na wikipédia muito bem explicado.

Mas vai aí o jeito que eu aprendi.

Bucket sort é um algoritmo de ordenação na ordem O(n). Mas o problema dele é que ele aloca muita memória.

E exige um conheicmento prévio sobre o conjunto de entradas.

Ele funciona da seguinte maneira. É alocado um vetorzão do tamanho do máximo+1 do vetor que deseja se ordenar. E cada entrada é guardada no índice do vetorzão. E em seguida as entradas são passadas de volta para o vetor original.

Então por exemplo queremos ordenar o seguinte vetor:

7 9 3 5 2

Nesse caso devemos alocar um vetor de tamanho 10 (pois o máximo é 9).

As entradas do vetor original são passadas então para o vetorzão de modo que cada entrada fica em seu índice correspondente. O vetorzão vai ficar da seguinte maneira.

 _ _ 2 3 _ 5 _ 7 _ 9 

(O índices marcados como '_' são índices vazios e na programação deve-se colocar um valor que não será utilizado no vetor.)

Em seguida as entradas são repassadas para o vetor original percorrendo o vetorzão todo.

No caso de entradas repetidas deve-se alocar uma matriz no lugar de um vetorzão.

Cada índice do vetorzão é chamado de bucket. E pode-se utilizar intervalos ao invés de um bucket para cada número. Mas isso vai exigir a ordenação de cada bucket.

É como armazenar dados para um histograma.


Fonte: http://forum.baboo.com.br/index.php?/topic/666787-bucket-sort/

Não sei se ajudei muito.. mas foi o que consegui até o momento.

No aguardo.

RuanCS · 29 de maio de 2016

Opa amigo. Obrigada pela pré disposição e pela ajuda e sim, é complicado e eu também desconhecia esse método. Tive que resolver em C mesmo porque em pascal estava me dando dor de cabeça. Esse erro de Array me deu muita dor de cabeça e eu resolvi mudar, já que eu suspeitei ser uma limitação do próprio Pascalzim(vi casos na internet parecidos).
Mas obrigado por tudo. Foi bom que agora eu mergulhei de vez em C++