Ir ao conteúdo
  • Cadastre-se
RuanCS

Bucket sort - formando o algoritmo

Recommended Posts

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×