Tri polyphase.

INTRODUCTION

Tout ensemble de données ne peut être trié en mémoire. Il arrive en effet que la quantité d'information à traiter dépasse les disponibilités en mémoire. Il faut recourir dans ce cas à des tris sur disque pour lesquels deux options sont possibles:
TRI POLYPHASE

Soit un fichier F de 8 nombres à trier:

3 1 4 5 2 9 6 7

Celui est décomposé en deux fichiers F1 et F2 en distribuant le contenu mais pas de manière quelconque! Il faut en effet que les nombres d'éléments des fichiers créés soient des nombres consécutifs de la suite de Fibonacci (1-1, 1-2, 2-3, 3-5, 5-8, 8-13, ..., x-y, y-(x+y), ...). Si le nombre d'éléments du fichier initial ne permet pas sa décomposition en respectant le critère défini ci-dessus, un des fichiers est complété par des éléments "bidon" (à définir suivant les cas).
Remarque:La manière de distribuer n'a pas d'importance. Seul compte le nombre d'éléments dans chaque fichier créé.

fichier F1
3 4 9 6 7

fichier F2
1 5 2

On compare ensuite le premier élément de F1 au premier élément de F2 et on les recopie dans l'ordre sur un fichier (F si il peut être détruit, sinon sur F3), on fait ensuite de même avec les deuxièmes éléments de F1 et F2, puis les troisièmes, les quatrièmes, ...

fichier F3
1 3 4 5 2 9

Mais le fichier F1 n'est pas épuisé, il reste en effet les nombres 6 et 7 qui n'ont pas été utilisés. On les recopie sur le fichier F2 qui a été "vidé". On se retrouve donc avec:

fichier F2
6 7

et le fichier F1 qui est vide.
On travaille ensuite sur le premier élément de F2 et le premier couple de F3 (ces 2 nombres sont triés): 1 est plus petit que 6, on l'écrit sur le fichier vide F1, on compare ensuite 3 à 6. On écrit 3 et comme la série d'éléments triés de F2 est terminée, on écrit 6. On obtient ainsi un premier groupe de 3 éléments triés. On attaque ensuite les comparaisons du deuxième couple de F3 (4 et 5) avec 7. On obtient un deuxième triple de nombres triés écrits sur F1 et il reste les nombres 2 et 9 de F3 qui n'ont pas été utilisés et qui sont recopiés sur le fichier F2 qui a été complètement utilisé et qu'on peut considérer comme vide.

fichier F1
1 3 6 4 5 7

fichier F2
2 9

Comme les éléments non utilisés de F3 ont été recopiés, F3 peut être considéré comme vide.
On travaille ensuite sur le premier couple de F2 (ils sont triés) et le premier triple de F1 (ils sont aussi triés): 2 est plus grand que 1, on écrit 1 sur le fichier vide F1, on compare ensuite 2 à 3. On écrit 2 puis on compare 9 à 3. On écrit 3 et on compare 9 à 6. On, écrit 6 et comme la série d'éléments triés de F1 est terminée, on écrit 9. On obtient ainsi un premier groupe de 4 éléments triés.
Il reste les nombres 4, 5 et 7 de F1 qui sont triés mais n'ont pas été utilisés. Ils sont recopiés sur le fichier F1 qui a été complètement utilisé et qu'on peut considérer comme vide.

fichier F3
1 2 3 6 9

fichier F1
4 5 7

On travaille maintenant sur les 5 éléments de F3 (ils sont triés) et les 3 nombres de F1 (ils sont aussi triés): 1 est plus petit que 4, on écrit 1 sur le fichier vide F2, on compare ensuite 2 à 4. On écrit 2. On compare 3 à 4. On écrit 3. On compare 6 à 4. On écrit 4. On compare 6 à 5. On écrit 5. On compare 6 à 7. On écrit 6. On compare 9 à 7. On écrit 7 et comme on a terminé les éléments de F2, on recopie 9. Et le fichier est trié!

fichier F2
1 2 3 4 5 6 7 9

Dernier problème et il est de taille: comment marquer la fin des groupes triés (indiquée par un changement de couleur dans la présentation ci-dessus). Si vous connaissez le contexte, le problème est plus simple. Si vous désirez par exemple trier des noms, il est évident que personne ne s'appellera (chez nous en tout cas) "zzzzz" (en ASCII, les minuscules suivent les majuscules). Si vous manipulez des âges d'êtres humains, il est évident que 255 (pour rester dans un stockage sur un octet) ne sera jamais atteint.

Notre tri devient alors:

Soit un fichier F de 6 nombres à trier:

3 4 5 2 9 6

Distribuons F sur F1 et F2 et insérons un 255 après chaque élément pour indiquer que dans l'état actuel du traitement, nous disposons de groupes de 1 élément (trié). Nous compléterons le fichier incomplet par des 255 pour en arriver à

fichier F1
3 255 5 255 2 255 6 255 255 255

fichier F2
4 255 2 255 9 255

On compare maintenant les éléments de F1 et de F2 jusqu'au moment où on rencontre deux fois 255 qui indique la fin du groupe trié. On compare donc d'abord 3 à 4. On écrit 3 et on lit 255 qu'on compare à 4. On écrit 4 et on lit 255. On est en fin des 2 groupes et notre groupe trié est terminé. On l'indique en écrivant 255. On fait de même avec 5 et 2, 6 et 9.

fichier F3
3 4 255 2 5 255 6 9 255

Mais le fichier F1 n'est pas épuisé, il reste en effet les nombres 255 et 255 qui n'ont pas été utilisés. On les recopie sur le fichier F2 qui a été "vidé". On se retrouve donc avec:

fichier F2
255 255

et le fichier F1 qui est vide.
On travaille maintenant sur F3 et F2 et on écrit sur F1. On compare 3 à 255. On écrit 3. On compare 4 à 255. On écrit 4. On compare 255 à 255. Comme on est en fin des 2 groupes triés, on écrit le marqueur de fin de groupe à savoir 255. On compare ensuite 2 à 255. On écrit 2. On compare 5 à 255. On écrit 5. On compare 255 à 255.Comme on est en fin des 2 groupes triés, on écrit le marqueur de fin de groupe à savoir 255. Le fichier F2 a été totalement utilisé. On réécrit sur F2 la partie non utilisée de F3. On obtient:

fichier F1
3 4 255 2 5 255

fichier F2
6 9 255

Comme les éléments non utilisés de F3 ont été recopiés, F3 peut être considéré comme vide.
On travaille maintenant sur F1 et F2 et on écrit sur F3. On compare 3 à 6. On écrit 3. On compare 4 à 6. On écrit 4. On compare 255 à 6. On écrit 6. On compare 255 à 255. Comme on est en fin des 2 groupes triés, on écrit le marqueur de fin de groupe à savoir 255. Le fichier F2 a été totalement utilisé. On réécrit sur F2 la partie non utilisée de F1. On obtient:

fichier F3
3 4 6 9 255

fichier F1
2 5 255

On travaille maintenant sur F1 et F3 et on écrit sur F2. On compare 3 à 2. On écrit 2. On compare 3 à 5. On écrit 3. On compare 4 à 5. On écrit 4. On compare 6 à 5. On écrit 5. On compare 6 à 255. On écrit 6. On compare 9 à 255. On écrit 9. On compare 255 à 255. Comme on est en fin des 2 groupes triés, on écrit le marqueur de fin de groupe à savoir 255. Le fichier F3 a été totalement utilisé. Et F1 aussi. Et le fichier est trié! Il reste à enlever le dernier élément de F2 qui est le marqueur de fin de paquet trié (il n'y en a plus qu'un).

fichier F2
2 3 4 5 6 9 255 


type ATrier=chaîne
entité DataRec
composantes:Data: ATrier
            Etat: entier
fent

tableau Fi i=1,…,3 de fichier de DataRec
fichier de ATrier: FIN, FOut
DataRec: Drec, DRec2, Bidon
entier: i, j

Procédure EclateFIn(¯FName, ­i) !FName=nom du fichier à trier & i = numéro du fichier le plus long!
paramètre: FName: chaîne
                   i: entier
tableau Ni i=1,2 de entier
tableau Fi i=1,2 de fichier de DataRec
fichier de ATrier: FIn
D: ATrier
DataRec: Drec
entier: Cpt, k

F1 ß "F1.TMP"
ouvrir F1
F2 ß "F2.TMP"
ouvrir F2
FIn ß FName
ouvrir FIn
lire D sur FIn
Cpt ß 0
i ß 1
N1 ß 0
N2 ß 0
tant que NOT EOF(FIn) faire
  Data de DRec ß D
  Etat de DRec ß 1
  si Cpt³N1+i mod 2 alors i ß 1+i mod 2    !on a un nombre de records égal à un nombre de Fibonacci!
                        Cpt ß 0
  fsi
  écrire DRec sur Fi
  écrire Bidon sur Fi
  Cpt ß Cpt+1
  Ni ß Ni+1
  lire D sur FIn
ftant
pour k de Cpt+1 à N1+i mod 2 faire !on complète avec des 'bidon' pour arriver à un nombre de Fibonacci!
  écrire Bidon sur Fi
  Ni ß Ni+1
fpour
si N1 < N2 alors i ß 2
sinon i ß 1
fsi
fermer FIn, F1, F2
fproc

fonction AutreF(i) !F1 et F3 sont utilisés successivement alors que F2 contient tjrs le reste du fichier!
   paramètre: i: entier
   à valeur entier
entier: Tmp

si i=1 alors Tmp ß 3
sinon Tmp ß 1
fsi
résultat(Tmp)

fonction PlusPetit(D1,D2) !on réinvente l'ordre pour des entités!
  paramètres: D1,D2: DataRec
  à valeur: booléen
booléen: Tmp

Tmp ß (Etat de D1<Etat de D2) ou ((Etat de D1=Etat de D2) et (Data de D1<Data de D2))
résultat(Tmp)

Etat de Bidonß 2 !un 'bidon' est caractérisé par un état à 2. Tt élément valable a son état à 1!
écrire "Nom du fichier à trier:"
lire FName
EclateFIn(FName,i)
si i=1 alors F1 ß "F1.TMP" !F1 correspond tjrs au + long fichier!
             F2 ß "F2.TMP"
sinon F1 ß "F2.TMP"
      F2 ß "F1.TMP"
fsi
F3 ß "F3.TMP"
N2 ß 1
i ß 1
tant que NOT (N2=0) faire !qd il n'y a plus d'élément en surplus, c'est que ts les éléments se trouvent dans le fichier trié!
ouvrir Fi !Fi est le fichier qui est fusionné avec F2!
lire DRec sur Fi
ouvrir F2
lire DRec2 sur F2j 
ß Autre(i)
ouvrir Fj !Fj est le fichier qui reçoit la fusion!
tant que NOT EOF(F2) faire !F2 est toujours le plus petit fichier!
tant que NOT ((Etat de DRec=2) et (Etat de DRec2=2)) faire !on arrête la fusion de paquets qd les entités lues sont 'bidon'!
si PlusPetit(DRec, DRec2) alors écrire DRec sur Fj
                                lire DRec sur Fi
sinon écrire DRec2 sur Fj
             lire DRec2 sur F2
fsi
ftant
écrire Bidon sur Fj
ftant
rebobiner F2 !on réouvre F2 pour y recopier les éléments restants de Fi!
N2 ß 0
lire DRec sur Fi
tant que NOT EOF(Fi) faire !comme F2 est toujours le plus petit fichier, il reçoit le reste inutilisé de l'autre fichier!
  écrire DRec sur F2
  N2 ß N2+1
  lire DRec sur Fi
ftant
i ß j
ftant
fermer Fi
fermer FAutreF(i) !le tri est fini!
ouvrir Fi !on nettoie le fichier d'entités pour récupérer les ATrier!
FOut ß "TRI.DAT"
ouvrir FOut
lire DRec sur Fi
tant que NOT EOF(Fi) faire
  si Etat de DRec=1 alors écrire Data de DRec sur FOut
  fsi
  lire DRec sur Fi
ftant
fermer Fi
fermer FOut
Pour charger une archive contenant le code source en Turbo Pascal et en Delphi 5 de cet algorithme, cliquez ici

Page précédente.

Page d'accueil.