$$crire une m$$thode nomm$$e trier qui permet le tri par insertion d$$un ensemble de nombres entiers.

Les donn$$es sont stock$$es dans une pile p$1$ pass$$e en param$$tre $$ la m$$thode trier et le programme

doit retourner une pile p$2$ contenant ces nombres tri$$s avec le minimum au sommet de la pile.

L$$algorithme propos$$ est le suivant : on utilise une pile p$3$ qui est vide au d$$but$.$ Tant que la pile

p$1$ n$$est pas vide, on consid$$re les deux cas suivants :

$$ si la pile p$2$ est vide ou si l$$l$$ment au sommet de p$1$ est plus petit que celui de p$2$ :

on retire l$$l$$ment au sommet de la pile p$1$ pour empiler dans la pile p$2,$ puis si la pile p$3$ n$$est pas

vide on retire tous les $$l$$ments de la pile p$3$ pour empiler dans la pile p$2.$

$$ sinon :

on d$$place l$$l$$ment au sommet de la pile p$2$ la pile p$3.$

$$crire la m$$thode nomm$$e trier de la classe Test fournie ci$-$joint pour ce propos. Le programme

principal main NE doit pas $$tre modifi$.$

La pile p$1$ est construite $$ partir d$$un tableau d$$entiers en utilisant la m$$thode push.

$/*$Exemple de sortie$*/$

Les elements de ma pile sont au depart :

$3$

$9$

$6$

$2$

$0$

$8$

$5$

$2$

$3$

$4$

Les elements de ma pile triee sont :

$0$

$2$

$2$

$3$

$3$

$4$

$5$

$6$

$8$

$9$

TEST.JAVA:

public class Test $\{$

static Stack trier $($Stack p$1)\{$

$//$VOTRE CODE VIENT ICI

$\}$

public static void main$($ String$[]$ args $)\{$

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

Stack pile;

pile $=$ new ArrayStack$(10)$;

Stack pileTrie;

pileTrie $=$ new ArrayStack$(10)$;

$/*$Empiler la pile avec les elements de tab et afficher ses elements$*/$

for $($int i $=0$; i $<$ tab.length; i$++)\{$

pile.push$($tab$[$i$])$;

$\}$

System.out.println$($ "Les elements de ma pile sont au depart : $")$;

while $(!$ pile.isEmpty$())\{$

System.out.println$($ pile.pop$())$;

$\}$

$/*$Empiler la pile a nouveau avec tab et afficher ses elements tries$*/$

for $($int i $=0$; i $<$ tab.length; i$++)\{$

pile.push$($tab$[$i$])$;

$\}$

pileTrie$=$trier$($pile$)$;

System.out.println$()$;

System.out.println$($ "Les elements de ma pile triee sont : $")$;

while $(!$pileTrie.isEmpty$())\{$

System.out.println$($ pileTrie.pop$())$;

$\}$

$\}$

$\}$