Un tri dans une matrice

Version imprimable

06/04/2013, 18h32
-Syn.-

Un tri dans une matrice

Bonjour,

Je souhaite appliquer la méthode de Burrows Wheeler à un fichier texte ; il faut donc préalablement rentrer ce fichier dans une matrice, ce que j'ai réussi. Cependant, me voilà arrivé à une étape où je ne sais pas comment m'y prendre : il faudrait que je range par ordre alphabétique les diverses lignes de la matrice.
Pourriez-vous m'orienter pour que je réussisse à faire ce tri s'il vous plaît ? Après diverses recherches, celles-ci ont été peu fructueuses.

Exemple : Le fichier texte contient les caractères "TEXTUEL" ; après être entré dans ma matrice et commencé la méthode de B.W, j'obtiens :

Citation:

T E X T U E L
L T E X T U E
E L T E X T U
U E L T E X T
T U E L T E X
X T U E L T E
E X T U E L T

Je souhaiterais, après tri, obtenir ceci :

Citation:

E L T E X T U
E X T U E L T
L T E X T U E
T E X T U E L
T U E L T E X
U E L T E X T
X T U E L T E

Merci d'avance de votre aide.

Bonjour !

La première chose à savoir, c'est qu'on peut comparer des caractères et même des chaînes au moyen des comparateurs < et >.
Ce qui est alors comparé, c'est le rang des caractères dans la table ASCII, ce qui correspond à l'ordre alphabétique, sauf que majuscules et minuscules n'ont pas le même rang.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 program Comparer; {$APPTYPE CONSOLE} begin WriteLn('A'<'B'); // TRUE WriteLn('ABB'<'ABC'); // TRUE WriteLn('a'<'B'); // FALSE WriteLn(Ord('a')); // 97 WriteLn(Ord('B')); // 66 ReadLn; end.
Le plus simple serait peut-être de comparer des chaînes ; mais on peut aussi comparer les lignes d'un tableau caractère par caractère : on commence par la gauche, et dès qu'on a trouvé deux caractères différents, on sait du même coup laquelle des deux lignes est "plus grande" que l'autre.

Bonjour !

Merci de votre réponse,
J'ai cependant un petit problème, en effet je n'arrive à trier la matrice que sur un rang, c'est à dire que s'il trouve "ACB", il réussira à donner "ABC", cependant s'il trouve "CBA", il ne ressortira que "BCA" sans remettre le A à la bonne place.
Pourriez-vous m'aider pour obtenir le bon code s'il vous plait ?
Autre petite chose, je n'arrive pas à formuler le code lorsque deux lettres sont identiques, à s'intéresser à la 2eme, si l'on a la matrice suivante :
Code:

1 2 3 BCC BAC BCA
il faudrait obtenir
Code:

1 2 3 4 BAC BCA BCC
A l'heure actuelle, ma procédure du tri de la matrice est comme suit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 Procedure matri(var matrice : mat); Begin setlength(temp,nb_car); i := 0; for i := 0 to high(temp) do temp[i] := '0';; i:=0; j:=0; for i := 0 to high(matrice)-1 do begin if ord(matrice[i,0]) > ord(matrice[i+1,0]) then // B > A // begin writeln('passeparla'); for j := 0 to high(matrice) do begin temp[j] := matrice[i,j]; writeln('temp[',j,'] : ',temp[j], ' '); matrice[i,j] := matrice[i+1,j]; matrice[i+1,j] := temp[j]; end; end; if ord(matrice[i,0]) = ord(matrice[i+1,0]) then writeln('passeparici'); end; end;
Merci d'avance de votre aide

Difficile de corriger un code quand on n'en voit qu'un morceau. Il serait peut-être bon de le poster en entier.

Autrement, je conseillerais de bien distinguer deux problèmes, à savoir 1° la comparaison des lignes et 2° le tri de la matrice.

Je commencerais par m'occuper de la comparaison des lignes :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 program tri_matrice_1; {$APPTYPE CONSOLE} type tLigne = array[0..6]of char; tMatrice = array[0..6]of tLigne; const exLigne1: tLigne = ('a','b','c','d','e','f','g'); exLigne2: tLigne = ('a','a','a','a','a','a','a'); exLigne3: tLigne = ('t','e','x','t','u','e','l'); function CompareLignes(const aLigne1, aLigne2: tLigne): integer; var i: integer; begin i := 0; while (aLigne1[i] = aLigne2[i]) and (i < 6) do Inc(i); result := Ord(aLigne1[i]) - Ord(aLigne2[i]); end; begin WriteLn(CompareLignes(exLigne1, exLigne2)); // 1 ( Ord('b') - Ord('a') ) WriteLn(CompareLignes(exLigne2, exLigne3)); // -19 ( Ord('a') - Ord('t') ) ReadLn; end.
Une fois que ma fonction de comparaison est au point, je peux passer comme arguments les lignes d'une matrice :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 program tri_matrice_2; {$APPTYPE CONSOLE} type tLigne = array[0..6]of char; tMatrice = array[0..6]of tLigne; const exLigne1: tLigne = ('a','b','c','d','e','f','g'); function CompareLignes(const aLigne1, aLigne2: tLigne): integer; var i: integer; begin i := 0; while (aLigne1[i] = aLigne2[i]) and (i < 6) do Inc(i); result := Ord(aLigne1[i]) - Ord(aLigne2[i]); end; var matrice: tMatrice; i: integer; begin for i := 0 to 6 do matrice[i] := exLigne1; WriteLn(CompareLignes(matrice[0], matrice[1])); // 0 ( les lignes sont identiques ) ReadLn; end.
Ensuite je ferais une procédure qui permute deux lignes d'une matrice :

Code:

procedure Permute(var aMatrice: tMatrice; const indexLigne1, indexLigne2: integer);

Et pour finir, la procédure de tri.

La discussion paraissant abandonnée, je me permets de poster ma solution.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
program Exercice;
 
{$APPTYPE CONSOLE}
 
{ Trier par ordre alphabétique les lignes d'un tableau de caractères.
 
  Compilation FreePascal 2.6.2. }
 
type
  tLigne = array[0..6]of char;
  tTable = array[0..6]of tLigne;
 
const
  cTable: tTable = (
    ('T','E','X','T','U','E','L'),
    ('L','T','E','X','T','U','E'),
    ('E','L','T','E','X','T','U'),
    ('U','E','L','T','E','X','T'),
    ('T','U','E','L','T','E','X'),
    ('X','T','U','E','L','T','E'),
    ('E','X','T','U','E','L','T')
  );
 
function Compare(const aLigne1, aLigne2: tLigne): integer;
var
  i: integer;
begin
  i := 0;
  while (aLigne1[i] = aLigne2[i]) and (i < 6) do
    Inc(i);
  result := Ord(aLigne1[i]) - Ord(aLigne2[i]);
end;
 
procedure Permute(var aTable: tTable; const aIndex1, aIndex2: integer);
var
  ligne: tLigne;
begin
  ligne := aTable[aIndex2];
  aTable[aIndex2] := aTable[aIndex1];
  aTable[aIndex1] := ligne;
end;
 
procedure Trie(var aTable: tTable);
var
  ordre: boolean;
  i: integer;
begin
  repeat
    ordre := TRUE;
    for i:= 0 to 5 do
      if Compare(aTable[i], aTable[i+1]) > 0 then
      begin
        ordre := FALSE;
        Permute(aTable, i, i+1);
      end;
  until ordre;
end;
 
var
  table: tTable;
 
begin
  table := cTable;
 
  WriteLn(Compare(table[0], table[1]):2); //   8
  WriteLn(Compare(table[1], table[2]):2); //   7
  WriteLn(Compare(table[2], table[3]):2); // -16
  WriteLn(Compare(table[3], table[4]):2); //   1
  WriteLn(Compare(table[4], table[5]):2); //  -4
  WriteLn(Compare(table[5], table[6]):2); //  19
 
  Trie(table); WriteLn;
 
  WriteLn(Compare(table[0], table[1]):2); // -12
  WriteLn(Compare(table[1], table[2]):2); //  -7
  WriteLn(Compare(table[2], table[3]):2); //  -8 
  WriteLn(Compare(table[3], table[4]):2); // -16
  WriteLn(Compare(table[4], table[5]):2); //  -1
  WriteLn(Compare(table[5], table[6]):2); //  -3
 
  ReadLn;
end.

Une variante utilisant la fonction StrComp de l'unité SysUtils :

Code:

1
2
3
4
function Compare(const aLigne1, aLigne2: tLigne): integer;
begin
  result := StrComp(pChar(@aLigne1), pChar(@aLigne2));
end;

En remplaçant StrComp par StrIComp, on obtient une fonction qui ne tient pas compte de la différence entre minuscules et majuscules.