Projet SDA - tri par paquets

typedef struct Liste Liste;
struct Liste {
	double valeur;
	Liste* next;
	Liste* last;
};

Liste* inserer(Liste* l, double x) {
	Liste* tmp = malloc(sizeof(Liste));
	tmp->valeur = x;
	tmp->next = l;
	tmp->last = NULL;
	if (l != NULL) {
		l->last = tmp;
	}
	return tmp;
}
void tri_paquet (double T[], unsigned taille, unsigned nb_intervalle) {
	unsigned i, j;
	Liste* Taux[nb_intervalle];
	for (i=0; i<nb_intervalle; i++) {
		Taux[i] = malloc(sizeof(Liste));
		Taux[i] = NULL;
	}
	double inter = 1.0/(double)nb_intervalle;
	double valeur;
	// Affectation des valeurs de T[i] dans les sous intervalles Taux.
	for (i=0; i<taille; i++)
		for (j=0; j<nb_intervalle; j++)
			if ((T[i] >= j*inter) && (T[i] < (j+1.0)*inter))
				Taux[j]=inserer(Taux[j],T[i]);

	// Tri par insertion des sous intervalles Taux.
	for (i=0; i<nb_intervalle; i++) {
		Liste* tmpliste = Taux[i];
		if (tmpliste != NULL) {
			unsigned nb_trie = 1;
			Liste* tmpliste2;
			Liste* debutliste = Taux[i];
			unsigned compteur=1;
			// On compte le nombre d'élément du sous intervalle i.
			while (tmpliste->next != NULL) {
				compteur++;
				tmpliste=tmpliste->next;
			}
			// On trie par insertion tant que tout les éléments ne sont pas triés.
			while (nb_trie < compteur) {
				tmpliste = debutliste;
				int bool = 0;

				for (j=0;j<nb_trie;j++)
					tmpliste = tmpliste->next;

				valeur = tmpliste->valeur;
				tmpliste2 = tmpliste->last;
				if (valeur < tmpliste2->valeur) {
					while (valeur < tmpliste2->valeur) {
						if (tmpliste2->last != NULL)
							tmpliste2=tmpliste2->last;
						else {
							bool = 1;
							debutliste = tmpliste;
							break;
						}
					}
					// On actualise le précédent et le suivant de l'élément.
					tmpliste->last->next = tmpliste->next;
					if (tmpliste->next != NULL)
						tmpliste->next->last = tmpliste->last;

					// Si l'élément devient le plus petit de la liste.
					if (bool == 1) {
						tmpliste->last = NULL;
						tmpliste->next = tmpliste2;
						tmpliste2->last = tmpliste;
					}
					// Si l'élément n'est pas le plus petit de la liste.
					else {
						tmpliste2->next->last = tmpliste;
						tmpliste->next = tmpliste2->next;

						tmpliste->last = tmpliste2;
						tmpliste2->next = tmpliste;
					}
				}
				nb_trie++;
			}
			Taux[i]=debutliste;
		}
	}

	// Concaténation des sous intervalles Taux dans Taux[0]
	Liste* debut;
	Liste* Tauxtri;
	for (i=0;i<nb_intervalle;i++) {
		if (Taux[i] != NULL) {
			debut = Taux[i];
			break;
		}
	}
	Tauxtri = debut;
	for (i=1; i<nb_intervalle ;i++) {
		while (Tauxtri->next != NULL) {
			Tauxtri = Tauxtri->next;
		}
		if (Taux[i] != NULL)
			Tauxtri->next = Taux[i];
	}
	// Affectation des valeurs triés dans le tableaux.
	Tauxtri = debut;
	for (i=0; i<taille; i++) {
		T[i] = Tauxtri->valeur;
		Tauxtri = Tauxtri->next;
	}
}