Les TRIS en algorithmique : 3�me partie (Tri Bulles)

Le tri � bulles ou tri par propagation est un algorithme de tri qui consiste � faire remonter progressivement les plus grands �l�ments d'un tableau, comme les bulles d'air remontent � la surface d'un liquide.

Le principe du tri Bulles :

La m�thode consiste � faire plusieurs balayages du tableau en ordonnant les paires d��l�ments adjacents, de bas en haut.

A la fin du premier balayage, l��l�ment le plus grand est remont� au sommet du tableau comme une bulle d�air dans l�eau.

Lors du deuxi�me balayage, on ne consid�re que la partie non tri�e du tableau pour obtenir � la fin le deuxi�me plus grand �l�ment sous le plus grand et ainsi de suite jusqu�� ce que le tableau soit compl�tement tri� (par ordre croissant).

Algorithme du tri par Bulles :

Var

T : tableau [1..100] de r�els ;

n,v,i : entiers ;

aux : r�el ;

D�but

    v <-- n ;

    Tantque v>1 faire

            Pour i <--1 � (v-1) faire

                    Si T[i] > T[i+1] alors

                           Aux = T[i] ;

                           T[i] = T [i+1] ;

                            T [i+1] = aux ;

                    FinSi

            FinPour i

            v <-- v-1 ;

 Fin

On note que v est le compteur des balayages, il varie entre n et 2 et dans chaque cas de figure i variera entre 1 et (v-1).

aux est la variable auxiliaire servant pour la permutation des �l�ments compar�s, s�ils sont en d�sordre.

Exemple d�utilisation :

Soit le tableau suivant compos� de 5 �l�ments (n=5).

7

3

14

5

10

1er Balayage

7

3

14

5

10

7

3

14

10

5

7

14

3

10

5

14

7

3

10

5

A la fin du 1^er Balayage l��l�ment 14 est au sommet du tableau.

2�me Balayage

14

7

3

10

5

14

7

10

3

5

14

10

7

3

5

A la fin du 2^eme Balayage l��l�ment 10 est en dessous du plus grand �l�ment.

3�me Balayage

14

10

7

3

5

14

10

7

5

3

14

10

7

5

3

A la fin du 3^�mebalayage le tableau est bel et bien tri�.

Conclusion :

Le tri � bulles est souvent enseign� en tant qu'exemple algorithmique. Cependant, sa complexit� est de l'ordre de n� en moyenne (o� n est la taille du tableau), ce qui le classe parmi les mauvais algorithmes de tri. Il n'est donc quasiment pas utilis� en pratique.

Les TRIS en algorithmique : 2�me partie (Tri par extraction)

Principe du tri par extraction :

Cette m�thode utilise en plus du tableau � trier un deuxi�me tableau dans lequel on place les �l�ments tri�s.

On cherche le plus petit �l�ment dans le premier tableau et on le place au d�but du deuxi�me tableau.

 

Ensuite on cherche le plus petit �l�ment parmi ceux non encore s�lectionn�es du premier tableau et on le place dans le deuxi�me tableau jusqu�� ce que tous les �l�ments soient recopi�s dans le deuxi�me tableau. A chaque fois qu�un �l�ment est s�lectionn�, il est remplac� par une valeur sp�ciale pour ne pas �tre pr�s�lectionn� une deuxi�me fois.

Algorithme du tri par extraction :

Var

T,T1 : tableau [1..100] de r�els ;

n,ind,i,j : entiers ;

max : reel;

D�but

            Pour i <-- 1 � n faire

                     Ind <-- 1 ;

                     Pour  j <-- 2 � n faire

                            Si T[ind] > T[j] alors

                                   ind <-- j ;

                           FinSi

                     FinPour j

                    T1[i] <-- T[ind] ;

                    T[ind] <-- max ;

        FinPour i

Fin

On note max la valeur sp�ciale, plus grande que tous les �l�ments du tableau (dans le cas d�un tri croissant) et plus petite que tous les �l�ments du tableau (dans le cas d�un tri d�croissant). Avant de lancer l�algorithme de tri par extraction, on peut appliquer au tableau T un algorithme de recherche du maximum auquel on ajoute 1 pour d�terminer la valeur de max (max=max(T) + 1), ind est l�indice du plus petit �l�ment trouv�.

Exemple d�utilisation :

Soit le tableau suivant compos� de 6 �l�ments (n=6) .

15

2

24

-8

0

4

max = maximum(T) + 1 = 24 + 1 = 25.

i=1 :

15

2

24

25

0

4

I=2 :

15

2

24

25

25

4

i=3

15

25

24

25

25

4

i=4

15

25

24

25

25

25

i=5

25

25

24

25

25

25

i=6

25

25

25

25

25

25

Le r�sultat dans le tableau T1 :

-8

0

2

4

15

24

Remarquons qu�� la fin, le tableau T ne contient plus que les valeurs sp�ciales 25. Et T1 contient les anciens �l�ments de T tri�s par ordre croissant.

Conclusion :

Le tri par extraction est un algorithme de tri par comparaison. Il est particuli�rement simple, mais inefficace sur de grandes entr�es, car il s'ex�cute en temps quadratique en le nombre d'�l�ments � trier.

Les TRIS en algorithmique : 1�re partie

Trier veut dire ordonner un ensemble d��l�ments, les ranger en ordre croissant ou d�croissant :

�        Tri croissant : si l��l�ment d�indice i est inf�rieur ou �gal � l��l�ment d�indice i+1.

�        Tri d�croissant : si l��l�ment d�indice i est sup�rieur ou �gal � l��l�ment d�indice i+1.

Le but du tri est de faciliter l�utilisation d�un ensemble de donn�es, par exemple pour un algorithme de recherche, fusion, �clatement . . .

Tri Interne � Tri Externe :

Un tri interne s�effectue sur des donn�es pr�sentes en m�moire centrale. L�acc�s aux informations ne prend que peu de temps. Pour �valuer le temps de calcul, on ne consid�re que le nombre de combinaisons et de permutations.

Un tri externe s�effectue sur des donn�es r�sidant en m�moires secondaires (disquettes, disques durs�). Dans ce cas le temps d�acc�s aux informations devient plus important car il s�agit d�un organe m�canique qui tourne. C�est pourquoi en g�n�ral, on cherche � minimiser le nombre d�acc�s aux m�moires secondaires.

Tr�s souvent, tri interne est �quivalent � tri de tableaux, et tri externe est �quivalent � tri de fichiers rang�s s�quentiellement.

 Quelques m�thodes de tri :

Il existe plusieurs m�thodes de tris. Nous allons pr�senter quelques-unes.

Dans tous les algorithmes qui suivront, on consid�re un tableau de 100 cases, dont n remplies par des valeurs r�elles. Nous nous int�resserons au tri croissant. La saisie et l�affichage des �l�ments sont suppos�es faites par d�autres algorithmes appelants.

Tri par SELECTION :

C�est l�une des m�thodes les plus simples pour trier les �l�ments d�un tableau : T [1], T [2], T [3]�, T [n]  en ordre croissant par exemple.

Nous allons balayer tous les �l�ments pour chercher le plus petit que nous �changeons avec T [1].

Nous r�p�tons en cherchant le plus petit �l�ment parmi T [2] jusqu�� T[n] que nous �changeons avec T [2] et ainsi de suite.

Apr�s (n-1) application de cette recherche et �change, les �l�ments du tableau sont tri�s.

Algorithme de s�lection :

Var

T : tableau : [1..100] de r�els ;

n,s,min,i,j : entiers ;

D�but

(* Tri des �l�ments du tableau *)

Pour i <-- 1 � (n-1) faire

    Min <-- T[i] ;

    Pour j <-- i+1 � n faire

         Si min > T[j] alors

             Min <-- T[j] ;

             s <-- j ;

         FinSi

   FinPour j

   Si min < T[i] alors

    T[s] <-- T[i] ;

    T[i] <-- min ;

   FinSi

FinPour i

Fin

On note min la valeur de minimum et s l�indice de cette valeur.

N.B : La pr�sentation des autres algorithmes se fera dans les prochains articles.

       

L'installation et la configuration de SAMBA sous Linux

Un des principaux int�r�ts des r�seaux est la possibilit� de partager des fichiers.

Il existe des protocoles (notamment le FTP, File Transfert Protocol) permettant de transf�rer des fichiers � l'aide de commandes � travers un r�seau h�t�rog�ne.

Toutefois, ce type de manipulation est assez fastidieux. Ainsi, les r�seaux Microsoft Windows offrent une mani�re totalement transparente de partager des fichiers, en permettant notamment la copie par simple gliss�-d�poser.
Cependant, ce type de r�seau ne permet � la base qu'un partage de fichiers entre machines fonctionnant avec un syst�me Microsoft Windows.

Ainsi, en poss�dant une machine sous linux, la solution est d'utiliser Samba. D'autre part, ce dernier permet de d�finir des niveaux d'acc�s tr�s pointus tr�s proches de ceux propos�s par un serveur Windows NT. Samba est donc une alternative �conomique et robuste � un recours � un serveur Windows NT.

Samba en g�n�ral:

Samba est un serveur de fichiers pour Linux en licenceGNU GPL(libre) compatible avec les r�seaux Microsoft Windows. C'est-�-dire qu'il permet de partager les fichiers  d'un serveur Linux avec des ordinateurs dot�s d'un syst�me d'exploitation Windows d'une mani�re totalement transparente .

Architecture de Samba:

Sambaest constitu� d'un serveur et d'un client, ainsi que des outils permettant de r�aliser des services pratiques ou bien de tester la configuration �ventuellement.

• Le serveur : il est constitu� de deux applications d�mons:

                 Smbd : Le noyau du serveur fournissant les services d'authentification et d'acc�s aux ressources.

                 Nmbd : Il montre les services offerts par Samba.

• Le client :  

                Smbclient : C'est le client Linux qui permet le transfert des fichiers, acc�der � diff�rentes ressources....

               Smbtar : Il permet le transfert de ou vers un fichier TAR sous Linux.

               Testparam : Il v�rifie la syntaxe du fichier de configuration de Samba :  smb.conf

Installation et configuration de Samba:

La commande permettant d'installer Samba : yum -y install samba

Le fichier de configuration : vi /etc/samba/smb.conf

Ci-dessous des imprim�s �crans concernant la configuration qu'il faut respecter afin de bien installer et configurer Samba dans votre syst�me d'exploitation Linux.

- On cr�e un dossier de partage nomm� "share"et on modifie les permissions � l'aide de la commande chmod 777 /home/share.

- On visualise le fichier de configuration : vi /etc/samba/smb.conf.

- On effectue les changements et les ajouts n�cessaires.

- On d�marre le service avec : chkconfig smb on.

- On ajoute un groupe nomm� "security" : groupdadd security.

- On cr�e un dossier nomm� "security" : mkdir /home/security.

- On modifie ses permisssions : chmod 770 /home/security.

- On revoit le fichier de configuration : vi /etc/samba/smb.conf.

- On effectue les changements n�cessaires au sein du fichier de configuration et on sauvegarde.

- On red�marre notre service Samba : /etc/rc.d/init.d/smb restart.

- On cr�e un nouveau utilisateur : smbpasswd -a fedora.

Maintenant notre service Samba est op�rationnel. Sous Windows on peut se connecter � notre service Samba afin d'effectuer le transfert des fichiers de Linux vers Windows.

Conclusion :

Pour conclure je vous propose un petit sch�ma r�capitulatif au sujet de Samba :