DEUG MIAGE

Structure de Données et Programmation

 

Travaux dirigés

Série n°6


This document is the API specification for the Java 2 Platform, Standard Edition, version 1.3.1

This document is the API specification for the Java 2 Platform, Standard Edition, version 1.4.2


EXERCICE 1 : Tri par Insertion

 

EXERCICE 2 : Tri par Sélection

 

EXERCICE 3 : Tri à Bulles

 

EXERCICE 4 : Tri par comptage de fréquence

 

EXERCICE 5 : Tri rapide

 


EXERCICE 1 : Tri par Insertion Exo1.java


A)    Ecrire une méthode void triInsertion(int[] t) qui trie par insertion un tableau de nombres entiers passé en argument.

Vous pourrez utiliser les méthodes suivantes pour tester votre solution :

public static void main(String[] args){

    int[] tab={4,3,2,1,0,5,6,7,8,9};

    //int[] tab={2,5,4,7,1,8,3,6,0,9};

    //int[] tab={9,8,7,6,5,4,3,2,1,0};

    //int[] tab={0,1,2,3,4,5,6,7,8,9};

    afficherTableau(tab);

    triInsertion(tab);

    afficherTableau(tab);

}

 

public static void afficherTableau(int[] t){

       for(byte i=0;i<t.length;i++) System.out.print(t[i]+" ");

       System.out.println();

}

 

B) Ecrire une méthode void triInsertion2(int[] t) qui trie par insertion en réalisant les décalages en même temps que la recherche du point d’insertion.

 

C)     Ecrire une méthode void triInsertion3(int[] t) qui trie par insertion en réalisant des échanges.

On pourra définir une méthode void echanger(int[] t, int i, int j) qui échange dans un tableau d’entiers (premier argument) les éléments d’indice i et j (second et troisième arguments).

 


EXERCICE 2 : Tri par Sélection            Exo2.java        TriSelectionTest.java


A) Ecrire une méthode void triSelection(int[] t) qui trie par sélection un tableau de nombres entiers passé en argument.

 

B) Utiliser le framework de test unitaire Junit pour tester votre programme.

 


EXERCICE 3 : Tri à Bulles          Exo3.java


A) Ecrire une méthode int triBulle(int[] t) qui trie un tableau de nombres entiers passé en argument et qui retourne le nombre de comparaisons effectuées lors du tri. Vous pourrez utiliser la méthode main suivante pour tester votre solution :

public static void main(String[] args){

     int[] tab={4,3,2,1,0,5,6,7,8,9};

    afficherTableau(tab);

    System.out.println("Nombres de comparaisons : "+triBulles(tab));

    afficherTableau(tab);

}

 

B) Remarquons que, si l'on n'a pas fait d'inversion (échange) lors d’un parcours, c'est que le tableau est déjà trié : on peut alors stopper l'algorithme. On peut éviter les passages inutiles à l'aide d'un booléen mis à false au début de chaque passage, et positionné à true dés qu’un échange a lieu. Ecrire une méthode int triBulles2(int[] t) qui implémente cette optimisation.

 

C) Plusieurs élément du « haut » du tableau peuvent se trouver rangés dans l'ordre ; on peut donc optimiser le traitement en s'arrêtant, lors d’une itération, au dernier élément déplacé de l'itération précédente. Ecrire une méthode int triBulles3(int[] t) qui implémente cette optimisation.

 

D) Le shakerSort est un tri à bulle dans lequel on fait successivement monter les maxima par échanges (i,i+1) successifs puis redescendre les minima par échanges (j,j-1). Ce tri est basé sur une simple observation du comportement du tri à bulles : en effet, quand on fait un passage pour trier le maximum du tableau, on a tendance à déplacer les éléments les plus petits du tableau vers le début (bas) de celui-ci. L’idée consiste à alterner les sens de passage de la « bulle ». Implémenter cet algorithme.

 


EXERCICE 4 : Tri par comptage de fréquence        Exo4.java


A)    Ecrire une méthode int[] frequenceCumul(int[] t, int k) qui renvoie le tableau contenant les fréquences cumulées des éléments du tableau t passé en premier argument, sachant que les valeurs prisent par ce tableau sont dans l’intervalle [0..k] où cas l’entier k est passé en second argument.

 

B)     Ecrire une méthode void triComptage(int[] t, int k) qui trie le tableau t passé en premier argument, sachant que les valeurs prisent par ce tableau sont dans l’intervalle [0..k] où cas l’entier k est passé en second argument.

 


EXERCICE 5 : Tri rapide Exo5.java


A)    Ecrire une méthode int partition(int[] t, int gauche, int droit) qui partitionne le tableau t passé en premier argument entre les indices gauche et droit (second et troisième arguments), autour de son premier élément considéré comme pivot, et qui retourne la position du pivot dans le tableau partitionné.

B)     Ecrire une méthode void triRapide(int[] t, int gauche, int droit) qui trie le tableau t passé en premier argument entre les indices bas et haut (second et troisième arguments).

C)     Utiliser le programme TriRapideTest.java et le framework de test unitaire Junit pour tester votre programme.

 

D)    Utiliser la méthode prédéfinie java.util.Arrays.sort(int [] t) de la classe Arrays pour effectuer un tri rapide sur un tableau d’entiers.

 


 

Signaler une erreur - Proposer une amélioration -

 

Haut du document