/* Fichier quickSort.cpp : une version de quickSort À l'intra, il y a une question sur la simulation de l'execution de la première fois la fonction partitionner. */ #include #include // pour setw et setprecision #include using namespace std; void continuer() { cout << endl << endl << "Appuyez sur une lettre suivie de Entree " ; char lettre; cin >> lettre ; cout << endl; } // patron de fonction (fonction modèle) template void permuter(T & a, T & b) { T tempo = a; a = b; b = tempo; } int partitionner ( float tableau[], int debut, int fin) { int g = debut , d = fin ; float valPivot = tableau[debut] ; do { while ( g <= d && tableau[g] <= valPivot) g++; while ( tableau[d] > valPivot) d--; if ( g < d ) permuter(tableau[g], tableau[d]); } while ( g <= d ) ; permuter(tableau[d], tableau[debut]); return d; } /* Cette fonction est récursive car dans son corps on appelle cette même fonction */ void quickSort ( float tableau[], int gauche, int droite ) { if (droite > gauche) /* au moins 2 éléments */ { int indPivot = partitionner ( tableau, gauche, droite); quickSort ( tableau, gauche, indPivot - 1 ); quickSort ( tableau, indPivot + 1, droite); } } void afficher(float tab[], int nbPers, const string message = "avant le tri: ") { cout.setf(ios::fixed); cout.setf(ios::showpoint); cout << "Contenu du tableau " << message << endl ; cout << " indice taille\n"; for(int i = 0; i < nbPers; i++) cout << setw(6) << i << ") " << setw(10) << setprecision(2) << tab[i] << endl; cout << endl; } int main() { float taille[] = { 1.72, 1.68, 1.53, 1.81, 1.75, 1.87, 1.62, 1.58, 1.97 }; int nbPers = sizeof(taille) / sizeof(float) ; afficher(taille, nbPers); // dernier paramètre par défaut quickSort( taille, 0, nbPers-1); afficher(taille, nbPers, "apres le tri:"); continuer(); return 0; } /* Exécution : Contenu du tableau avant le tri: indice taille 0) 1.72 1) 1.68 2) 1.53 3) 1.81 4) 1.75 5) 1.87 6) 1.62 7) 1.58 8) 1.97 Contenu du tableau apres le tri: 0) 1.53 1) 1.58 2) 1.62 3) 1.68 4) 1.72 5) 1.75 6) 1.81 7) 1.87 8) 1.97 Appuyez sur une lettre suivie de Entree */