TD Algo-Prog 4

Dans tous ces exercices, on souhaite définir une fonction void tri( int t[], int n ) qui, étant donné un tableau t à n élements, ordonne ses éléments par ordre croissant. Exemple : le tableau

{
3, 1, 2, 7, 11, 24, 2 }

à 7 éléments devient


{ 1, 2, 2, 3, 7, 11, 24 }

. Pour chacun des exercices, il faut répondre aux questions et en déduire une définition de la fonction tri.

Le principe du tri par sélection (par échange ou par extraction) est de chercher le plus petit élément pour le mettre en premier position, puis en partant du second élément, chercher le plus petit élément pour le mettre en seconde position, etc. A la i-ième étape, on sélectionne donc le plus petit élément dans la partie de tableau t[i:n-1] et on l'échange avec t[i].
Écrire une fonction void selectionne( int t[], int n, int i ) qui cherche l'indice du plus petit élément dans t[i:n-1] et échange la valeur de cet élement avec celle de t[i].

Le principe du tri bulle (bubble sort) est de comparer deux à deux les éléments consécutifs t[i] et t[i+1] d'un tableau et d'effectuer une permutation si

t[i]
> t[i+1]

. On continue de trier jusqu'à ce qu'il n'y ait plus de permutation.
Écrire une fonction int remonte_bulle( int t[], int n ) qui effectue une permutation de t[i] avec t[i+1] si ces éléments sont dans le désordre et ceci pour chaque indice i depuis 0 jusqu'à n-2, et retourne 1 si une permutation a eu lieu, 0 sinon.

Écrire une fonction void fusionne( int t[], int n ) qui, étant donné un tableau t à n éléments où n est pair, interclasse les éléments des moitiés t[0:n/2] et t[n/2+1:n-1] que l'on supposera triées. Cette fonction procède par effet de bord. Après exécution de cette fonction le tableau t est trié.

Le tri rapide (quicksort) - aussi appelé "tri de Hoare" (du nom de son inventeur) ou "tri par segmentation" ou "tri des bijoutiers"- est certainement l’algorithme de tri le plus efficace. Comme le tri fusion, il s’agit d’un algorithme récursif utilisant le paradigme "diviser pour régner". Le principe de ce tri est le suivant :

On choisit un élement (appelé pivot), on notera x sa valeur
On permute les éléments du tableau à trier de façon à ce que, pour un indice i particulier :

        - l'élément d'indice i ait pour valeur x
        - tous les élements de t[0:i-1] aient une valeur inférieure à x
        - tous les éléments de t[i+1:n-1] aient une valeur supérieure à x

On trie (récursivement) les parties de tableau t[0:i-1] et t[i+1:n-1].

Dérouler l'algorithme de tri rapide sur l'exemple donné plus haut.
Écrire une fonction récursive

int partitionne( int t[], int imin,
int imax, int j)

qui, étant donné deux indices imin et imax définissant une partie de tableau t[imin:imax], et un indice j entre imin et imax, réalise les permutations nécessaires pour que, en notant x, la valeur t[j] et i, le résultat de la fonction :

      - l'élément d'indice i ait pour valeur x
        - tous les élements de t[imin:i-1] aient une valeur inférieure à x
        - tous les éléments de t[i+1:imax] aient une valeur supérieure à x.