Exercice 1 - Fonction de génération de tableaux

Ecrire la fonction T = Genere_Tableau(n) qui génère un tableau de n valeurs entières aléatoires entre 0 et 100 000.

function T=Genere_Tableau(n)
  % Fonction Genere_Tableau
  %   Génère un tableau de n valeurs entières aléatoires entre 0 et VALEUR_MAX
  %
  % PARAMETRES
  %   VALEUR_MAX : borne supérieure des valeurs du tableau généré
  % ENTREE
  %   n : taille du tableau
  % SORTIE
  %   T : Tableau de n valeurs entières aléatoires entre 0 et VALEUR_MAX
  
  VALEUR_MAX = 100000;

  T = abs(ceil(VALEUR_MAX * rand(1,n)));

end

Exercice 2 - Fonction d’insertion d’élément

Comme vu dans le TD 3, programmez la fonction GNU Octave T = Inserer_Element(T, p_init, p_fin) qui réalise l’insertion d’un élément à partir d’un tableau de nombre entiers, d’un indice de position initiale (p_init) et d’un indice de position finale (p_fin).

function T=Inserer_Element(T, p_init_, p_fin)
  % Fonction Inserer_Element
  %   Inserer un élément à partir d'un tableau de nombre entiers, d'un indice de
  %     position initiale (p_init) et de position finale (p_fin).
  %
  % ENTREE
  %   T       : Tableau de n valeurs entières aléatoires 
  %   p_init  : indice de position initiale
  %   p_fin   : indice de position finale
  % SORTIE
  %   T       : Tableau de n valeurs entières aléatoires
	
	if (p_init > p_fin)
	  % On stocke la valeur de l'élement à déplacer
	  element = T(p_init);

		% On décale l'ensemble des valeurs
	  T(p_fin+1:p_init)=T(p_fin:p_init-1);

		% On replace la valeur de l'élément à la bonne position
		T(p_fin) = element;
	end
end

Exercice 3 - Tri par insertion

Comme vu dans le TD 3, programmez une fonction GNU Octave qui réalise le tri par insertion d’un tableau.

Tri par insertion

function T=Tri_Insertion(T)
  % Fonction Tri_Insertaion
  %   Effectue un tri par insertion sur un tableau T
  %
  % ENTREE
  %   T       : Tableau de n valeurs entières aléatoires
  % SORTIE
  %   T       : Tableau de n valeurs entières aléatoires triées

  printf('TRI PAR INSERTION\\n');
  tic(); % Pour mesurer le temps

  for i=1:length(T)
    x = T(i);
    j = i;

    while j > 1 && T(j-1) > x
      j = j-1;
    endwhile

    T = Inserer_Element(T,i,j);
  endfor

  toc(); % Pour mesurer le temps

end

Exercice 4 - Tri par sélection

Comme vu dans le TD 3, programmez une fonction GNU Octave qui réalise le tri par sélection d’un tableau.

Tri par sélection

function T=Tri_Selection(T)
  % Fonction Tri_Selection
  %   Effectue un tri par selection sur un tableau T
  %
  % ENTREE
  %   T       : Tableau de n valeurs entières aléatoires
  % SORTIE
  %   T       : Tableau de n valeurs entières aléatoires triées

  printf("TRI PAR SELECTION\\n");
  tic(); % Pour mesurer le temps

  n=length(T);

  for i=1:n-1
    min = i;

    for j=i+1:n
      % On cherche le minimum
      if T(j) < T(min)
        min = j;
      endif
    endfor

    if min ~= i % Si i est différent de min (on a trouvé un autre minimum)
      % On échange les deux valeurs
      tmp = T(i);
      T(i) = T(min);
      T(min) = tmp;
    endif
  endfor

  toc(); % Pour mesurer le temps

end

Exercice 5 - Tri à bulles (Bubble sort)

Ecrivez la fonction tri_a_bulles définie par l’algorithme suivant

fonction t=tri_a_bulle(tableau t)
	taille = taille(t)
	pour i de taille à 1
		pour j de 2 à i
			si t[j-1]>t[j] alors
				echanger ([j-1] et t[j]
			finsi
		finpour
	finpour
fin		

Tri à bulles

function T=Tri_A_Bulles(T)
  % Fonction Tri_A_Bulles
  %   Effectue un tri à bulles sur un tableau T
  %
  % ENTREE
  %   T       : Tableau de n valeurs entières aléatoires
  % SORTIE
  %   T       : Tableau de n valeurs entières aléatoires triées

  printf("TRI A BULLES\\n");
  tic(); % Pour mesurer le temps

  n= length(T);
    for i=n:-1:1
      
      for j=2:i
        
        if T(j-1)>T(j)
          % On echange les valeurs
          temp = T(j-1);
          T(j-1)=T(j);
          T(j)=temp;
        endif
      endfor
    endfor

  toc(); % Pour mesurer le temps

end

Exercice 6 - Tri rapide (QuickSort)