le tri d'un tableau

الموضوع في 'أرشيف المنتدى التعليمي' بواسطة hamaied, بتاريخ ‏12 ماي 2008.

  1. hamaied

    hamaied عضو

    إنضم إلينا في:
    ‏3 أفريل 2008
    المشاركات:
    53
    الإعجابات المتلقاة:
    47
      12-05-2008 22:11


    Tri d'un tableau:
    1. introduction:
    Le tri consiste à ordonner dans un ordre bien déterminé (croissant ou décroissant) les éléments d’un tableau. Il existe plusieurs méthodes de tri. Dans la suite on vous en présente 3 : tri par sélection, tri à bulles et tri par insertion.
    Enoncé :On se propose de remplir un tableau T de n éléments (1<n<20) par des entiers, le trier et l’afficher.
    Exemple n= 4
    T
    15​
    0​
    10​
    50​
    …………..
    T​
    0​
    10​
    15​
    50​
    …………..


    2. tri par sélection:
    Principe :
    On commence à parcourir le tableau à partir du premier élément pour chercher l’indice de ce minimum. Ce dernier peut se répéter plusieurs fois, on décide de choisir le premier ou le dernier).
    On compare ce minimum avec T [1] ; s’ils ne sont pas dans le bon ordre, on les permute. Après cette opération, il est sur que T [1] contient la plus petite valeur.
    Le sous tableau de T allant de 2 à n est non trié, on répète les étapes 1) et 2) et ainsi de suite jusqu’à l’avant dernier élément (n-1).

    Analyse du programme principal

    NOM : TRI_TABLEAU
    S​
    L.D.E​
    O.U​
    4
    1
    3
    2
    5​
    Résultat = PROC AFFICHE (N, T)
    N = PROC LECTURE (N)
    T = PROC TRI_SELECTION (N, T)
    T = PROC REMPLIR (N, T)
    FIN TRI_TABLEAU
    AFFICHE
    N
    T
    LECTURE
    TRI_SELECTION
    T
    REMPLIR​
    Algorithme du programme principal
    0/ Début TRI_TABLEAU
    1/ PROC LECTURE (N)
    2/ PROC REMPLIR (N, T)
    3/ PROC TRI_SELECTION (N, T)
    4/ PROC AFFICHE (N, T)
    5/ Fin TRI_TABLEAU
    Tableau de déclaration de nouveaux types
    Type​
    TAB = tableau de Nmax entiers.​
    Tableau de déclaration des objets
    Objet
    Nature / Type​
    AFFICHE
    N
    T
    LECTURE
    TRI_SELECTION
    REMPLIR
    Nmax
    Procédure
    Variable/entier
    TAB
    Procédure
    Procédure
    Procédure
    Constante =19​




    Analyse de la procédure LECTURE

    DEF PROC LECTURE (var N : entier)
    S​
    L.D.E​
    O.U​

    1


    2​
    Résultat = N
    N = Répéter
    N = donnée ("Donner le nombre d’éléments")
    Jusqu’à (N dans [2.. Nmax])
    FIN LECTURE




    Algorithme de la procédure lecture
    0/ DEF PROC LECTURE (var N : entier)
    1/ Répéter
    Ecrire (" Donner le nombre d’éléments")
    Lire (N)
    Jusqu’à (N dans [2.. Nmax])
    2/ FIN LECTURE


    Analyse de la procédure REMPLIR

    DEF PROC REMPLIR (N : entier ; VAR T : TAB)
    S​
    L.D.E​
    O.U​

    1


    2​
    Résultat = T
    T =[] Pour i de 1 à N faire
    T = donnée ("T[",i, "]=")
    Fin Pour
    FIN REMPLIR

    i​
    Tableau de déclaration des objets locaux
    Objet
    Nature / Type​
    i
    Compteur / Entier​

    Algorithme de la procédure remplir
    0/ DEF PROC REMPLIR (N : entier ; VAR T :TAB )
    1/ Pour i de 1 à N faire
    Ecrire ("T[",i, "]=")
    Lire (T)
    Fin pour
    2/ FIN REMPLIR




    Analyse de la procédure TRI_SELECTION

    DEF PROC TRI_SELECTION (N : entier ; VAR T : TAB )
    S​
    L.D.E​
    O.U​

    1





    2​
    Résultat = T
    T = Pour i de 1 à N-1 faire
    ppm
    ß FN PREMPOSMIN (i,N,T)
    Si T[ppm] ≠T alors
    PROC PERMUT (T[ppm],T)
    Finsi
    Fin Pour
    FIN TRI_SELECTION

    i
    ppm
    PREMPOSMIN
    PERMUT​
    Tableau de déclaration des objets locaux
    Objet
    Nature / Type​
    i
    ppm
    PREMPOSMIN
    PERMUT
    Compteur/Entier
    Variable/Entier
    Fonction
    Procédure ​

    Algorithme de la procédure tri_selection
    0/ DEF PROC TRI_SELECTION (N : entier ; VAR T : TAB)
    1/ Pour i de 1 à N faire
    ppm
    ß FN PREMPOSMIN (i,N,T)
    Si T[ppm] ≠T alors
    PROC PERMUT (T[ppm],T)
    Finsi
    Fin Pour
    2/ FIN TRI_SELECTION



    Analyse de la fonction PREMPOSMIN

    DEF FN PREMPOSMIN (d, f : entier ; T : TAB) : entier
    S​
    L.D.E​
    O.U​

    2
    1




    3​
    Résultat = PREMPOSMIN
    PREMPOSMIN
    ß posmin
    posmin= [posmin
    ßd] Pour j de d+1 à f faire
    Si T[j] <T[posmin] alors
    Posmin
    ßj
    Finsi
    Fin Pour
    FIN PREMPOSMIN

    posmin
    j​
    Tableau de déclaration des objets locaux
    Objet
    Nature / Type​
    posmin
    j
    Entier
    Compteur/entier ​

    Algorithme de le fonction premposmin
    0/ DEF FN PREMPOSMIN (d, f : entier ; T :TAB ) : entier
    1/ [posmin
    ßd] Pour j de d+1 à f faire
    Si T[j] <T[posmin] alors
    Posmin
    ßj
    Finsi
    Fin Pour
    2/ PREMPOSMIN
    ß posmin
    3/ FIN PREMPOSMIN



    Analyse de la procédure PERMUT

    DEF PROC PERMUT (VAR X,Y : entier )
    S​
    L.D.E​
    O.U​

    2
    3
    1
    4​
    Résultat = X,Y
    int
    ßX
    X
    ßY
    Y
    ßint
    FIN PERMUT

    int​

    Tableau de déclaration des objets locaux
    Objet
    Nature / Type​
    int
    Variable /Entier ​
    Algorithme de la procédure permut
    0/ DEF PROC PERMUT (VAR X,Y : entier )
    1/ int
    ßX
    2/ X
    ßY
    3/ Y
    ß int
    4/ FIN PERMUT


    Analyse de la procédure AFFICHE

    DEF PROC AFFICHE (N : entier ; T : TAB )
    S​
    L.D.E​
    O.U​

    1


    2​
    Résultat = T
    T = Pour i de 1 à N faire
    Ecrire (" T[ ",i,"]= ", T)
    Fin Pour
    FIN AFFICHE

    i​

    Tableau de déclaration des objets locaux
    Objet
    Nature / Type​
    i
    Compteur/ entier ​
    Algorithme de la procédure affiche
    0/ DEF PROC AFFCICHE ( N : entier ; T :TAB )
    1/ Pour i de 1 à N faire
    Ecrire (" T[ ",i,"]= ", T)
    Fin Pour
    2/ FIN AFFICHE


    3. tri à bulles:
    Principe :
    On parcourt le tableau en comparant toute paire d’éléments consécutifs (ai-1, ai) non ordonnés. Ainsi après le premier parcours, l’élément maximum se retrouve en position n.
    On suppose que l’ordre s’écrit de gauche à droite (à gauche le plus petit élément, à droite le plus grand élément).
    On répète l’opération avec le nouveau sous tableau non trié (a1, a2,…, an-1), et ainsi de suite jusqu’à terminer tous les sous tableaux (le dernier est un couple).
    Le nom de tri à bulles vient donc de ce qu’à la fin de chaque itération interne (2ème boucle), les plus grands nombres de chaque sous tableau se déplacent vers la droite successivement comme des bulles de la gauche vers la droite.
    NB : les procédures lecture, remplir, permut et affiche sont les mêmes.

    Analyse de la procédure TRI_BULLES

    DEF PROC TRI_BULLES (N : entier ; VAR T : TAB)
    S​
    L.D.E​
    O.U​

    1






    2​
    Résultat = T
    T = [] Pour i de N à 1 faire
    [] Pour j de 2 à i faire
    [] Si T [j-1] >T[j] alors
    PROC PERMUT (T [j-1], T[j])
    Finsi
    FinPour
    Fin Pour
    FIN TRI_BULLES
    i
    j
    PERMUT​
    Tableau de déclaration des objets locaux
    Objet
    Nature / Type​
    i
    j
    PERMUT
    Compteur/Entier
    Compteur/Entier
    Procédure ​

    Algorithme de la procédure tri__BULLES
    0/
    DEF PROC TRI_BULLES ( N : entier ; VAR T :TAB )
    1/ []Pour i de N à 1 faire
    [] Pour j de 2 à i faire
    []Si T[j-1] >T[j] alors
    PROC PERMUT (T[j-1],T[j])
    Finsi
    FinPour
    Fin Pour
    2/ FIN TRI_BULLES




    4. tri par insertion:
    Principe :

    a) Commencer avec le 2ème élément.
    b) Comparer l'élément choisi avec tous ses précédents dans la liste et l'insérer dans sa bonne place pour que ces éléments soient rangés.
    c) Répéter les étapes 1 et 2 jusqu'a arriver au dernier nombre. La liste sera triée en ordre croissant
    NB : les procédures lecture, remplir, permut et affiche sont les mêmes
    Analyse de la procédure TRI_INSERTION

    DEF PROC TRI_INSERTION (N:entier, VAR T:TAB)
    S​
    L.D.E​
    O.U​

    1






    2








    3​
    Résultat: T
    T=[] Pour i de 2 à N faire
    [j <-1;B<-Vrai]TantQue j < i et (B) faire
    si T<T[j]
    alors
    B<-faux
    X<-T
    Pour k décroissant de i à j+1 faire
    T[k] <-T[k-1]
    FinPour
    T[j] <- X
    Sinon
    j<-j+1
    FinSi
    FinTantque
    FinPour
    FIN TRI_INSERTION.
    i
    j
    k
    B
    X​


    Tableau de déclaration des objets locaux:
    Objet ​
    Nature / Type​
    i
    j
    k
    B
    X​
    Entier
    Entier
    Entier
    Booléen
    entier ​
    Algorithme de la procédure INSERTION
    0) DEF PROC INSERTION (N:ENTIER; T:TAB)
    1) Pour i de 2 à N Répéter
    j <-1
    B <- Vrai
    TantQue j < i et (B=vrai) faire
    si T<T[j] alors
    B <-faux
    X <-T
    Pour k décroissant de i à j+1 Répéter
    T[k] <- T[k-1]
    FinPour
    T[j] <- X
    Sinon
    j <- j+1
    FinSi
    FinTantque
    FinPour
    2) FIN INSERTION.
    Recherche d'un élément dans un tableau:
    5. recherche séquentielle:
    Cette méthode de recherche consiste à parcourir les éléments du tableau un par un jusqu'à trouver la valeur cherchée ou arriver à la fin du tableau
    Analyse du programme principal

    NOM : Recherche_Seq
    S​
    L.D.E​
    O.U​
    4
    3
    2
    1​
    Résultat = PROC AFFICHE (Verif)
    Verif ← Recherche (T, N, K)
    Saisie (T, N, K)
    FIN Recherche_Seq

    AFFICHE
    N
    T
    Saisie
    K
    recherhce​










    Algorithme du programme principal
    Début Recherche_Seq
    Saisie (T, N, K)
    Verif ← Recherche (T, N, K)
    Affiche (Verif)
    Fin Recherche_Seq
    Analyse de la procédure Saisie:

    DEF PROC Saisie (VAR Tf : TAB ; VAR Nf, Kf : Entier)
    S​
    L.D.E​
    O.U​
    4
    1


    2


    3
    5​
    Résultat = (Tf,Nf,Kf)
    Nf=[ ]répéter
    Nf=donnée ("Donner la taille du tableau : ")
    Jusqu'à (Nf dans [1..100])
    Tf=[ ] pour i de 1 à Nf Faire
    Tf=donnée ("Donner l’élément N°", i, ": ")
    Fin pour
    Kf=donnée ("Donner la valeur a cherchée : ")
    Fin saisie

    i

    Algorithme de la procédure saisie:
    Début procédure Saisie (VAR Tf : TAB ; VAR Nf, Kf : Entier)
    Répéter
    Ecrire ("Donner la taille du tableau : "), Lire (Nf)
    Jusqu'à (Nf dans [1..100])
    Pour i de 1 à Nf Faire
    Ecrire ("Donner l’élément N°", i, ": "), Lire (Tf)
    Fin Pour
    Ecrire ("Donner la valeur a cherchée : "), Lire (Kf)
    Fin Saisie
    Analyse de la fonction recherhce:

    DEF FN recherhce (Tf : TAB ; Nf, Kf : Entier):entier
    [CENTER]S[/CENTER]
    [CENTER]L.D.E[/CENTER]
    [CENTER]O.U[/CENTER]
    3​
    2
    1






    4​
    Résultat = recherche
    recherche←Trouve
    Trouve= [Trouve←-1, i←1] Répéter
    Si Tf = Kf Alors
    Trouve ← i
    Sinon
    i ← i+1
    Finsi
    Jusqu’à (Trouve <>-1) OU (i > Nf)
    Fin recherche

    i
    Trouve
    [SIZE=3][/SIZE]

    Algorithme de la fonction Recherche :
    Début fonction recherche (Tf : TAB ; Nf, Kf : Entier) : Booléen
    [Trouve ← -1, i ← 1] Répéter
    Si Tf = Kf Alors
    Trouve ← i
    Sinon
    i ← i+1
    Finsi
    Jusqu’à (Trouve <>-1) OU (i > Nf)
    Recherche ← Trouve
    Fin Recherche

    [SIZE=3]Analyse de la procédure Affiche:
    [CENTER][/CENTER][/SIZE]
    [CENTER][/center]

    [SIZE=3]DEF PROC Affiche(Veriff:entier)[/SIZE]
    [FONT=Calisto MT][SIZE=3][CENTER]S[/CENTER][/SIZE][/FONT][SIZE=3][CENTER][/center][/SIZE][CENTER][/center]
    [FONT=Century Gothic][SIZE=3][CENTER]L.D.E[/CENTER][/SIZE][/FONT][SIZE=3][CENTER][/center][/SIZE][CENTER][/center]
    [FONT=Calisto MT][SIZE=3][CENTER]O.U[/CENTER][/SIZE][/FONT][SIZE=3][CENTER][/center][/SIZE][CENTER][/center]
    [CENTER]2
    1


    3[/CENTER]
    Résultat = écrire (msg)
    msg=[msg←(K," n’existe pas dans le tableau")]si (veriff<>-1) alors
    msg←(K," existe dans le tableau à l'indice",veriff)
    fin si
    fin Affiche




    [SIZE=3]Algorithme de la procédure Affiche :
    [/SIZE]
    Début procédure Affiche (Veriff : Booléen)
    msg←(K," n’existe pas dans le tableau")
    Si Veriff = vrai Alors
    Ecrire (K," existe dans le tableau à l'indice",Veriff)
    Finsi
    Fin Affiche
    6. [U]recherche dichotomique:
    [/U]
    [FONT=Courier New][SIZE=6][COLOR=#ff0000][CENTER]La méthode ne s'applique que lorsque le tableau est trié[/CENTER]
    [/COLOR][/SIZE][/FONT]
    [SIZE=6][COLOR=#ff0000][/COLOR][/SIZE]a) [U]Principe :
    [/U]
    Cette méthode de recherche consiste à :
    Fixer le début (Deb) et la fin (Fin) du tableau,
    Fixer le milieu du tableau (Mil = (Fin + Deb) Div 2),
    Comparer K et T[Mil], Si (K > T[Mil]) alors rechercher K dans le sous tableau [Mil + 1 … Fin] sinon si (K < T[Mil]) alors dans le tableau [Deb … Mil - 1],
    Répéter les étapes 1, 2 et 3 jusqu’à (K = T[Mil]) ou (Deb > Fin)
    b) [U]Exemple :
    [/U]
    Soit un tableau T contenant les dix éléments suivants :
    [CENTER]T :[/CENTER]
    [CENTER]-5[/CENTER]
    [CENTER]-2[/CENTER]
    [CENTER]-1[/CENTER]
    [CENTER]0[/CENTER]
    [CENTER]2[/CENTER]
    [CENTER]8[/CENTER]
    [CENTER]10[/CENTER]
    [CENTER]12[/CENTER]
    [CENTER]12[/CENTER]
    [CENTER]40[/CENTER]

    [CENTER]1[/CENTER]
    [CENTER]2[/CENTER]
    [CENTER]3[/CENTER]
    [CENTER]4[/CENTER]
    [CENTER]5[/CENTER]
    [CENTER]6[/CENTER]
    [CENTER]7[/CENTER]
    [CENTER]8[/CENTER]
    [CENTER]9[/CENTER]
    [CENTER]10[/CENTER]




    Pour K = -2 le programme affichera "-2 existe dans le tableau"
    Pour K = 5 le programme affichera "5 n’existe pas dans le tableau"
    c) [U]Analyse:
    [/U]
    [SIZE=3]Analyse du programme principal:
    [/SIZE]

    [SIZE=3]NOM :[/SIZE] Recherche_Dicho
    [FONT=Calisto MT][SIZE=3][CENTER]S[/CENTER][/SIZE][/FONT][SIZE=3][CENTER][/center][/SIZE][CENTER][/center]
    [FONT=Century Gothic][SIZE=3][CENTER]L.D.E[/CENTER][/SIZE][/FONT][SIZE=3][CENTER][/center][/SIZE][CENTER][/center]
    [FONT=Calisto MT][SIZE=3][CENTER]O.U[/CENTER][/SIZE][/FONT][SIZE=3][CENTER][/center][/SIZE][CENTER][/center]
    [CENTER]4
    3
    2
    1[/CENTER]
    Résultat = PROC AFFICHE (Verif)
    Verif ← Recherche (T, N, K)
    Saisie (T, N, K)
    FIN Recherche_Seq

    [CENTER]AFFICHE
    N
    T
    Saisie
    K
    recherhce[/CENTER]








    Algorithme du programme principal :
    Début Recherche_DichoSaisie (T, N, K)
    Verif ← Recherche (T, N, K)Affiche (Verif)Fin Recherche_ Dicho
    Analyse de la fonction Recherche:


    DEF FN recherhce (Tf : TAB ; Nf, Kf : Entier):entier
    [SIZE=3][CENTER]S[/CENTER][/SIZE][CENTER][/center]
    [SIZE=3][CENTER]L.D.E[/CENTER][/SIZE][CENTER][/center]
    [SIZE=3][CENTER]O.U[/CENTER][/SIZE][CENTER][/center]
    3
    2
    1










    4​
    Résultat = recherche
    recherche←Trouve
    Trouve= [Trouve←1, Deb←1,Fin←Nf] Répéter
    Mil← (Deb + Fin) Div 2
    Si Tf[Mil] > Kf Alors
    Fin ← Mil - 1
    Sinon
    Si Tf[Mil] < Kf Alors
    Deb ← Mil + 1
    Sinon
    Trouve ← i
    Finsi
    Jusqu’à (Trouve<>-1) OU (Deb > Fin)
    Fin recherche

    i
    Deb
    Fin
    Trouve​

    Algorithme de la fonction Recherche :
    Début fonction recherche (Tf : TAB ; Nf, Kf : Entier) : entier
    [Trouve ← -1, Deb ← 1, Fin ← Nf] Répéter
    Mil ← (Deb + Fin) Div 2Si Tf[Mil] > Kf AlorsFin ← Mil - 1Sinon
    Si Tf[Mil] < Kf AlorsDeb ← Mil + 1Sinon
    Trouve ← i
    FinsiJusqu’à (Trouve <>-1) OU (Deb > Fin)
    Recherche ← TouveFin Recherche





     
    1 person likes this.
  2. Ahmed.tn11

    Ahmed.tn11 عضو

    إنضم إلينا في:
    ‏2 جانفي 2008
    المشاركات:
    1.707
    الإعجابات المتلقاة:
    1.710
      12-05-2008 22:37
    merci mon ami mais il faut penser comment poster le sujet
     
  3. yassna3200

    yassna3200 عضو نشيط

    إنضم إلينا في:
    ‏21 جانفي 2007
    المشاركات:
    174
    الإعجابات المتلقاة:
    5
      13-05-2008 10:56
    merci
    bon travail
     
  4. fahhouda

    fahhouda عضو

    إنضم إلينا في:
    ‏17 فيفري 2008
    المشاركات:
    86
    الإعجابات المتلقاة:
    63
  5. Memede94

    Memede94 عضو فعال

    إنضم إلينا في:
    ‏13 نوفمبر 2007
    المشاركات:
    357
    الإعجابات المتلقاة:
    663
      13-05-2008 20:57


    Bonjour tout le monde, j'ai fait un TP il n'y pas longtemps sur les tri d'un tableau en java, j'ai trouvé que ça peut etre util le code du programme qui permet d'effectuer 3 types de tri !

    public class Tri {

    public static int[] tab;
    // Cette méthode permet de initilialiser un tableau avec des valeurs compris entre 0 et 9
    public static int[] initialiser(int taille){
    for ( int i =0; i<=taille;i++ ) {
    tab= (int) (9*Math.random());

    **
    return tab;
    **
    public static int[] afficher(int tab[]){
    int l= tab.length;;
    for (int i = 0; i<=l;i++){
    System.out.println(tab);
    **
    return tab;
    **
    public static int[] intervenir( int i, int j){
    int x = tab;
    tab = tab[j];
    tab[j] = x;
    return tab;
    **
    public static int[] triBulle(int tab[]){
    int l = tab.length;
    for (int i =0 , j =i+1; i < l-1 ; i++){
    if (tab > tab[j]) {
    intervenir(i,j);
    **
    **
    return tab;
    **
    public static int[] triSelection(int tab[]){
    int l = tab.length;
    for(int i=1; i <=l ; i++ ){
    double min = tab[0];
    if ( tab < min) { min = tab;**
    **
    return tab;
    **
    public static int[] triInsertion(int tab[]){
    int l = tab.length;
    for( int i =1; i<l;i++){
    int x = tab;
    int compteur = i-1;
    boolean marqueur;
    do
    {
    marqueur = false;
    if(tab[compteur]>x){
    tab[compteur+1] = tab[compteur];
    compteur--;
    marqueur = true;
    **
    if(compteur <0) marqueur = false;
    **
    while(marqueur);
    tab[compteur+1]= x;**
    return tab;
    **
    public static void main(String[] args) {
    int [] tab1 = initialiser(10);
    afficher(tab1);
    triBulle(tab1);
    afficher(tab1);
    triSelection(tab1);
    afficher(tab1);
    triInsertion(tab1);
    afficher(tab1);
    **

    **
     
  6. rgzied

    rgzied عضو فعال

    إنضم إلينا في:
    ‏12 ماي 2008
    المشاركات:
    415
    الإعجابات المتلقاة:
    164
      15-05-2008 16:16
    ce sujet est ok
     
  7. lotfi222

    lotfi222 كبار الشخصيات

    إنضم إلينا في:
    ‏24 فيفري 2008
    المشاركات:
    8.272
    الإعجابات المتلقاة:
    28.701
      15-05-2008 17:00
    merci pour le cours
     

مشاركة هذه الصفحة

جاري تحميل الصفحة...