Quicksort no memo

Delphi

24/06/2004

Estou fazendo uma procura em um memo, para efeito de aprendizado,,,,quero fazer um quicksort, tipo que nunca vi isso, me pediram algo, aí pensei algo parecido, depois me falaram que o que tinha pensado , era quicksort, mas não pensei exatamente igual,senão eu tinha feito,,,,sendo assim vo manda o codigo que fia ate agora, quando vc procura um numero que menor que a primeira divisao que é efetuada pelo codigo onde se inicia a procura o dado requerido, lee acha o numero blz, mas qundo é pra cima da primeira divisao,,,,ele não acha,,,da tipo um loop,,,,,olha se vcs acham o erro, mecha no meu codigo,,,,, :roll:

procedure TForm10.Button1Click(Sender: TObject);
var

valor : integer;
tnumeros : integer;
divisao : integer;
total : integer;

begin

valor := (StrToint(edit1.Text)); //Recebe o valor procurado

tnumeros:= memo11.Lines.Count -1;

begin
if (tnumeros mod 2 ) = 0 then
//fazer nada
else
tnumeros := tnumeros+1;
end;

total := tnumeros;

divisao := total div 2;

ShowMessage(´Dividiu´);

while IntToStr(valor) <> Memo12.Lines[divisao] do
begin

if valor > StrToInt(Memo12.Lines[divisao]) then
begin
total := total-divisao;
divisao := ( (total)div 2 );
Showmessage(´dividiu ´);
end

else
begin
total := total-divisao;
divisao := (total)div 2;
// ShowMessage (´dividiu ´+IntToStr(divisao)+IntToStr(total));
end;

end;//End while

ShowMessage (( Memo12.Lines.Strings[divisao]))

end;


Deryck

Deryck

Curtidas 0

Respostas

Bferreira

Bferreira

24/06/2004

Colega,

Desculpe, mas não entendi bem o que vc esta querendo fazer.

Vc deseja fazer uma consulta de um valor qualquer no memo? O quer simplismente ordenar os valores que estão no memo.
O QuickSort é um algoritmo de ordenação, Se quizer posso te explicar o funcionamento del.

Vou dar uma olhada no seu código, e ver o q da pra fazer.

Agora coso queira fazer a consulta de um valor no memo, vc vai ter q usar outro algoritmo para busca em texto, tais como Rabinkarp, Boyer Moore e outros.

T+


GOSTEI 0
Deryck

Deryck

24/06/2004

Colega, Desculpe, mas não entendi bem o que vc esta querendo fazer. Vc deseja fazer uma consulta de um valor qualquer no memo? O quer simplismente ordenar os valores que estão no memo. O QuickSort é um algoritmo de ordenação, Se quizer posso te explicar o funcionamento del. Vou dar uma olhada no seu código, e ver o q da pra fazer. Agora coso queira fazer a consulta de um valor no memo, vc vai ter q usar outro algoritmo para busca em texto, tais como Rabinkarp, Boyer Moore e outros. Cara o lance é o seguinte, sao gerados numeros aleatorios em um memo, e estes são ordenados em outro, sendo assim, logo depois de ordená-los, quero fazer uma procura , de um numero qualquer, estou usando este metodo que te passei o codigo, so que , vamso supor ,foram gerados 10 numeros, eu divido 10 por dois , comparo pra ver se o valor , é maior ou menor que 5(valor que ta na linha 5 do memo)(metade), se for menor (Ele acha po numeor blz), e qndo é maior que 5, o algortimo não busca o numero que quero busca , da loop, queria saber onde estou errando, pois não posso sair muito fora do que te mandei, o cara quer que eu faça no dedão mesmo! T+



GOSTEI 0
Beppe

Beppe

24/06/2004

É busca binária o que está fazendo. São bem diferentes em propósito, mas o princípio é o mesmo.

O problema é que, quando vc descobre que o item estará numa posição acima do que [i:62b4c5014d]divisao[/i:62b4c5014d], vc não descarta da busca os item menores.


GOSTEI 0
Deryck

Deryck

24/06/2004

É busca binária o que está fazendo. São bem diferentes em propósito, mas o princípio é o mesmo. O problema é que, quando vc descobre que o item estará numa posição acima do que [i:dd26c7c19a]divisao[/i:dd26c7c19a], vc não descarta da busca os item menores.




Mas como vou fazer isso? Isso , que eu não estou conseguindo fazer!


GOSTEI 0
Beppe

Beppe

24/06/2004

Procura por busca binária aqui no fórum ou na Internet que vc acha.


GOSTEI 0
Bferreira

Bferreira

24/06/2004

Procura por busca binária aqui no fórum ou na Internet que vc acha.


Realmente o q vc esta querendo fazer é a busca binária, só que ela tem a desvantagem de obriga-lo a ordenar o vetor primeiro para depois fazer a consulta, existem outros algoritmos como o q citei, q faz o busca sem precisar de ordenação.

eu tenho o código de uma busca binária que implementei, mas ela está em C vou passar para pascal e te mandar.

T+


GOSTEI 0
Beppe

Beppe

24/06/2004

Realmente o q vc esta querendo fazer é a busca binária, só que ela tem a desvantagem de obriga-lo a ordenar o vetor primeiro para depois fazer a consulta, existem outros algoritmos como o q citei, q faz o busca sem precisar de ordenação.

Ele disse que os dados já estariam ordenados, por isso citei busca binária.

Há um problema com o algoritmos de busca de padrões para este caso: eles trabalham(originalmente) sobre arrays unidimensionais. Ele citou um ´memo´, que é um array bidimensional do tipo ´jagged´. Estes algoritmos precisam ser modificados para aceitar o tipo de entrada que ele falou.

deryck, talvez devesse substituir o memo por um array of Integers, ou ainda set of 0..255, se cada número ocupar até um byte.


GOSTEI 0
Bferreira

Bferreira

24/06/2004

[quote:b4205402d2=´bferreira´]Realmente o q vc esta querendo fazer é a busca binária, só que ela tem a desvantagem de obriga-lo a ordenar o vetor primeiro para depois fazer a consulta, existem outros algoritmos como o q citei, q faz o busca sem precisar de ordenação.

Ele disse que os dados já estariam ordenados, por isso citei busca binária.

Há um problema com o algoritmos de busca de padrões para este caso: eles trabalham(originalmente) sobre arrays unidimensionais. Ele citou um ´memo´, que é um array bidimensional do tipo ´jagged´. Estes algoritmos precisam ser modificados para aceitar o tipo de entrada que ele falou.

deryck, talvez devesse substituir o memo por um array of Integers, ou ainda set of 0..255, se cada número ocupar até um byte.[/quote:b4205402d2]

Realmente ele vai ter q fazer algumas adaptações no algoritmo, mas nada muito complicado.
Aki na faculdade tive q adaptar o Rabin Karp para fazer a busca em um arquivo de texto, e funcionou perfeitamente.
Acho q no Memo ele poder usar o mesmo princípio, além do que a busca binária para o memo tbm necessita de adaptações.


GOSTEI 0
Beppe

Beppe

24/06/2004

Como o memo eh um array de linhas, busca binária rola sem problemas.

O problema que me referi na busca de padrões é este:

1 234 389 34236


ao pesquisar 89, o algoritmo retorna Achou(3, 2), embora naum há o número 89.


GOSTEI 0
Bferreira

Bferreira

24/06/2004

Como o memo eh um array de linhas, busca binária rola sem problemas. O problema que me referi na busca de padrões é este: [quote:fd551b9742]1 234 389 34236


ao pesquisar 89, o algoritmo retorna Achou(3, 2), embora naum há o número 89.[/quote:fd551b9742]

É realmente, para q isso não ocorra é necessário fazer algumas adaptações.

A busca binária funiona normalmente com o memo?
Não sei direito, pq quando implementei a mesma eu testei só em um vetor simples.
Eu tenho o fonte dele aqui, mas esta em C++, vou passar ele para o delphi e testar.

Valeu

T+


GOSTEI 0
Bferreira

Bferreira

24/06/2004

Fiz algumas alterações no seu código e agora esta funcionando bem
aconselho a vc alterar o nome das variáveis pois pode te confundir, tentei manter os nomes q vc usou.
Qualquer dúvida poste ai q te esplico, deixei o codigo bem comentado.

Espero ter ajudado :)

T+

procedure TForm1.Button1Click(Sender: TObject);
var
   valor : integer;//valor q se quer encontrar
   tnumeros : integer; // ultima linha do memo
   divisao : integer; // posição central do memo(meio)
   total: integer; // posição inicial do memo
   teste: integer; //controle do memo1
begin
  teste:=0;
  valor := (StrToint(edit1.Text)); //Recebe o valor procurado
  tnumeros:= memo12.Lines.Count -1;
 { if (tnumeros mod 2 ) = 0 then ->comentei essa parte pois não ha necessidade da mesma
     //fazer nada
  else               k
    tnumeros := tnumeros+1;}
  total := 0;
  divisao := (total+tnumeros) div 2; //pegando a posicao central
  {usando busca binaria
    divide o vetor em dois se o procurado for maior procura dele em diante
    se o procurado for igual ao meio encontrou
    se o procurado for menor que o meio procura do procura do inicio ate o meio
    cada vez q procura ele divide em dois até o meio ser igual ao procurado
  }

  while IntToStr(valor) <> Memo12.Lines[divisao] do //enquanto não encontrar
    //se teste ultrapassar o tamanho do memo não encontrou
    if teste > memo12.Lines.Count -1 then
      begin
        showmessage(´Valor não encontrado´);
        Break;
      end
    else
    begin //se o valor estiver na segunda metade do memo
      if valor > StrToInt(Memo12.Lines[divisao]) then
        begin // procura da metade em diante e recalcula o meio
          total := divisao+1;
          divisao := ( (total+tnumeros) div 2 );
        end
      else
         begin // se estiver na primeira metade
            // procura na primeira metade recalculando a pos do meio
            tnumeros := tnumeros-divisao;
            divisao := (total+tnumeros)div 2;
         end;
         teste:=teste+1;
  end;//End while
    // quando sair quer dizer q encontrou mas antes temos q testar
    // se o teste não ultrapassou o valor do memo
    // se não ultrapassou então encontrou :)
     if teste < memo12.Lines.Count -1 then
         showmessage(´Esta na linha ´+ IntToStr(divisao+1));
end;



GOSTEI 0
POSTAR