Tris spéciaux

Les tris spéciaux ont des complexités inférieures à $\mathcal{O}(n\log(n))$, ce qui n'est bien sur possible que si l'on se place dans des cas particuliers d'entrées.

Tri par paquets (bucket sort)

On veut trier les $n$ objets d'un tableau $\mathcal{E}$ par rapport à leur valeur via une injection $f: \mathcal{E} \to [0, m[$ allant de $\mathcal{E}$ dans l'ensemble des entiers de 0 à $m-1$.

Le tri par paquets consiste à créer un tableau de taille $m$ et de ranger chaque élément $o$ de $\mathcal{E}$ dans ce tableau à l'indice $f(o)$. Il suffit ensuite de rendre la restriction de ce tableau aux éléments contenant les éléments de $\mathcal{E}$.

Écrire le pseudocode de cet algorithme. On supposera que l'on cherche à trier $n$ entiers.

Quelle est la complexité en temps et en mémoire de cet algorithme ?

Utilisez cet algorithme pour trier :

  1. $n$ entiers deux à deux différents.
  2. comment modifier cet algorithme si les entiers peuvent être égaux ?
  3. complexité de cet algorithme ?

Quand utiliseriez vous cet algorithme pour trier $n$ objets ?

Tri par base

Ce tri s'applique uniquement aux entiers positifs. Notre entrée est une liste $T$ de listes de mêmes tailles composées de 0 et de 1 représentant des entiers écrit en base 2 (comme pour le compteur binaire). Par exemple : $T = [[1, 0, 0, 1], [1, 1, 1, 0], [0, 0, 0, 1]]$ qui correspond aux nombres $[9, 14, 1]$.

Le principe de ce tri est très simple :

Les parcours des liste T se font, toujours, de la gauche vers la droite.

Pour notre exemple :

  1. après premiere boucle : $[[1,1,1,0], [1, 0, 0, 1], [0, 0, 0, 1]]$
  2. après deuxième boucle : $[[1, 0, 0, 1], [0, 0, 0, 1], [1,1,1,0]]$
  3. après troisième boucle :$[[1, 0, 0, 1], [0, 0, 0, 1], [1,1,1,0]]$
  4. après quatrième boucle : $[[0, 0, 0, 1], [1, 0, 0, 1], , [1,1,1,0]]$

Questions :

Donnez le pseudo-code, la preuve et la complexité de cet algorithme.