www

Unnamed repository; edit this file 'description' to name the repository.
Log | Files | Refs

tas.c (1376B)

      1 #include <module.h>
      2 #include <types.h>
      3 #include <tri/tas/tas.h>
      4 
      5 MODULE(TriParTas);
      6 
      7 
      8 void initTriParTas(void** etat) {
      9 	*etat = NULL;
     10 }
     11 
     12 void deinitTriParTas(void** etat) {
     13 	*etat = NULL;
     14 }
     15 
     16 void percoler(int racine, void* t, int taille, AccesseurIndex get, AccesseurEchanger echanger, Comparaison comparer) {
     17 	int gauche = 2 * racine + 1;
     18 	int droite = 2 * racine + 2;
     19 	
     20 	void* valracine;
     21 	void* valgauche;
     22 	
     23 	while (droite < taille) {
     24 		valracine = get(t, racine);
     25 		valgauche = get(t, gauche);
     26 		
     27 		if (comparer(valracine, valgauche) < 0) {
     28 			if (comparer(valgauche, get(t, droite)) < 0) {
     29 				echanger(t, racine, droite);
     30 				racine = droite;
     31 			}
     32 			else {
     33 				echanger(t, racine, gauche);
     34 				racine = gauche;
     35 			}
     36 		} else {
     37 			if (comparer(valracine, get(t, droite)) < 0) {
     38 				echanger(t, racine, droite);
     39 				racine = droite;
     40 			} else {
     41 				return;
     42 			}
     43 		}
     44 		
     45 		gauche = 2 * racine + 1;
     46 		droite = 2 * racine + 2;
     47 	}
     48 	
     49 	if ((gauche < taille) && (comparer(get(t, racine), get(t, gauche)) < 0))
     50 		echanger(t, racine, gauche);
     51 }
     52 
     53 void triParTas(void* t, int taille, AccesseurIndex get, AccesseurEchanger echanger, Comparaison comparer) {
     54 	int i;
     55 	for (i = (taille / 2) - 1; i >= 0; i--)
     56 		percoler(i, t, taille, get, echanger, comparer);
     57 	
     58 	for (i = taille - 1; i > 0; i--) {
     59 		echanger(t, i, 0);
     60 		taille--;
     61 		percoler(0, t, taille, get, echanger, comparer);
     62 	}
     63 }