[Off] Ordenação de matrizes

Delphi

09/03/2005

Galera, gostaria q vcs me ajudassem na resolução desse problema.
Suponha q eu tenha uma matriz 5 x 5, como se segue:
1 1 1 1 3
2 2 2 2 2
3 3 3 3 5
4 4 4 4 1
5 5 5 5 4

Gostaria de elaborar um algoritmo pra ordenar essa matriz de acordo com a última coluna. No caso, o resultado seria:
4 4 4 4 1
2 2 2 2 2
1 1 1 1 3
5 5 5 5 4
3 3 3 3 5

Sugestões?

P.S. - não, Beppe, não é trabalho d faculdade :mrgreen:


Tnaires

Tnaires

Curtidas 0

Respostas

Tnaires

Tnaires

09/03/2005

Aê galera, consegui
Valeu


GOSTEI 0
Motta

Motta

09/03/2005

tnaires, este site tem uma lista completa de algoritmos, implementações referencias etc.

http://www.nist.gov/dads/

ele é meio ruim de procurar, mas é completo.


GOSTEI 0
Rômulo Barros

Rômulo Barros

09/03/2005

procedure TForm1.Button1Click(Sender: TObject);
Var
   Matriz : Array[1..5,1..5] Of Integer;
   J,
   I,
   Auxiliar : Integer;
   Trocou : Boolean;
begin
   Matriz[1,1] := 1;
   Matriz[1,2] := 1;
   Matriz[1,3] := 1;
   Matriz[1,4] := 1;
   Matriz[1,5] := 3;

   Matriz[2,1] := 2;
   Matriz[2,2] := 2;
   Matriz[2,3] := 2;
   Matriz[2,4] := 2;
   Matriz[2,5] := 2;

   Matriz[3,1] := 3;
   Matriz[3,2] := 3;
   Matriz[3,3] := 3;
   Matriz[3,4] := 3;
   Matriz[3,5] := 3;

   Matriz[4,1] := 4;
   Matriz[4,2] := 4;
   Matriz[4,3] := 4;
   Matriz[4,4] := 4;
   Matriz[4,5] := 1;

   Matriz[5,1] := 5;
   Matriz[5,2] := 5;
   Matriz[5,3] := 5;
   Matriz[5,4] := 5;
   Matriz[5,5] := 4;


   Repeat
       Trocou := False;
       For J := 1 To 4 Do
       Begin
           If(Matriz[J,5] > Matriz[J + 1,5])Then
           Begin
              Trocou := True;
              For I := 1 To 4 Do
              Begin
                 Auxiliar := Matriz[J,I];             // Aux guarda a maior
                 Matriz[J,I] := Matriz[J + 1,5] ;     // Maior recebe a menor
                 Matriz[J + 1,5] := Auxiliar;         // Menor recebe a maior
              End;
           End;
       End;
   Until(Not(Trocou));
   ShowMessage(´Ordenado com sucesso...´);
end;



GOSTEI 0
Tnaires

Tnaires

09/03/2005

Obrigado pessoal.
Motta, esse site já tá nos meus favoritos! :D
Undeclared identifier, obrigado! Foi desse jeito q eu fiz. Adaptei a ordenação da bolha. Tô tentando adaptar outro método d ordenação pra ver se sai mais rápido.
Abraços


GOSTEI 0
Beppe

Beppe

09/03/2005

Mas eu nem disse nada... :lol:

Seria Burrows-Wheeler o que está fazendo? Este é fixo 5x5, mas que parece, parece.

Vc pode adaptar o QuickSort que está em Classes.pas, vc precisa mudar a comparação para comparar de trás para frente(tem que implementar isso).


GOSTEI 0
Beppe

Beppe

09/03/2005

Opa, eu percebi uma coisa que acabei esquecendo de falar...eu percebi que o último elemento de cada linha é um diferente do outro. Se isto for uma regra, podemos ter um ganho real aqui. Basta percorrer as linhas X de (1 a N - 1), permutando X[1..5] com M[X[5], 1..5]. Se eu não me fiz entender diga que eu explico melhor.


GOSTEI 0
Tnaires

Tnaires

09/03/2005

Ei Beppe, desculpe a demora pra responder, mas eu fiquei doente e não fui trabalhar na quinta. E em casa não tenho PC, roubaram... :(
Mas eu nem disse nada... :lol:

Isso te lembra alguma coisa? :D
[url]http://forum.clubedelphi.net/viewtopic.php?t=49419&highlight=[/url]
O q estou fazendo é um dos problemas da [url=http://acm.uva.es/problemset]ACM[/url]. Na resolução, tive q usar esse recurso. No caso, como vc falou, os elementos da última coluna são diferentes em geral, mas pode acontecer d existirem números iguais. Sua otimização ainda serviria?
Valeu


GOSTEI 0
Beppe

Beppe

09/03/2005

Ei Beppe, desculpe a demora pra responder, mas eu fiquei doente...

Mesma coisa comigo quando mexo com esses contestos... :lol:

[quote:0bac20edca=´Beppe´]Mas eu nem disse nada... :lol:

Isso te lembra alguma coisa? :D
[url]http://forum.clubedelphi.net/viewtopic.php?t=49419&highlight=[/url][/quote:0bac20edca]
Lembra, lembra...mas é que dessa vez vc naum sismou... :lol:

O q estou fazendo é um dos problemas da [url=http://acm.uva.es/problemset]ACM[/url]. Na resolução, tive q usar esse recurso. No caso, como vc falou, os elementos da última coluna são diferentes em geral, mas pode acontecer d existirem números iguais. Sua otimização ainda serviria?

Quicksort sim, mas como a ordem da matrix é baixa, não sei se seria muito mais eficiente, mas creio que insertionsort se desse melhor que bubble neste caso.

Com ítems repetidos, o ´mapeamento´ da matriz desordenada p/ ordenada deixa de ser uma função bijetiva, então os índices não são mais diretos.


GOSTEI 0
POSTAR