Exercices sur les tableaux et les structures





1  Tri par insertion d'un tableau

On veut trier (avec l'algorithme de tri par insertion) un tableau, tout en gardant la trace des positions initiales des éléments. Ainsi, pour un tableau de 10 éléments, le programme affichera :
 Tableau initial :
88  62  47  16  87  27  61  36  2  40  

La 1e valeur vaut 2 et correspond à l'elt d'indice 8
La 2e valeur vaut 16 et correspond à l'elt d'indice 3
La 3e valeur vaut 27 et correspond à l'elt d'indice 5
La 4e valeur vaut 36 et correspond à l'elt d'indice 7
La 5e valeur vaut 40 et correspond à l'elt d'indice 9
La 6e valeur vaut 47 et correspond à l'elt d'indice 2
La 7e valeur vaut 61 et correspond à l'elt d'indice 6
La 8e valeur vaut 62 et correspond à l'elt d'indice 1
La 9e valeur vaut 87 et correspond à l'elt d'indice 4
La 10e valeur vaut 88 et correspond à l'elt d'indice 0
Les valeurs des éléments du tableau sont des valeurs aléatoires obtenues avec le générateur pseudo-alétoire rand. Ce générateur est initialisé à l'aide de la fonction srand par le temps en secondes écoulé depuis le 1e janvier 1970 (obtenu avec la fonction time déclarée dans time.h) :
srand((unsigned int)time(NULL));

2  Tri d'un tableau en 2 parties suivant la parité des éléments

Écrire un programme qui, à partir d'un tableau d'entiers aléatoires, le trie suivant le critère suivant : tous les entiers pairs doivent être au début du tableau et les entiers impairs à la fin. Le nombre d'opérations effectuées sera proportionnel à la taille du tableau. Par exemple :
tableau initial :
14 5 17 8 11 4 8 6 4 7 

tableau trie :
14 4 6 8 8 4 11 17 5 7 

3  Problème du drapeau hollandais

On veut trier un tableau dont les éléments ne prennent que 10 valeurs (de 0 à 9) suivant le critère suivant : tous les éléments dont la valeur est strictement inférieure à 3 sont au début du tableau, tous les éléments dont la valeur est comprise entre 3 et 6 sont au milieu, et tous les éléments dont la valeur est strictement supérieure à 6 sont à la fin. Le programme affichera par exemple :
tableau initial :
5 8 1 4 3 9 2 7 3 8 1 4 5 3 8 

tableau trie :
1 2 1 4 3 5 3 4 3 5 8 7 9 8 8 


This document was translated from LATEX by HEVEA.