algo d'arrangement ( type quicksort)

Question

Bonjour tout le monde,

Je dois considérer l'idée suivante pour réaliser un arrangement*:

1)On choisit une clé de référence compatible avec l'intervalle à trier*;
2)On cherche, à partir de la gauche de l'intervalle, une clé >= la clé choisie**;
3)On cherche, à partir de la droite de l'intervalle, une clé <= la clé choisie*;
4)On échange les clés trouvées en 2) et en 3)*;
5)On réitère les recherches et l'échange (2-4) tant que les indices de recherche ne se sont pas croisés.
--> L'état final des indices de recherche sont les i et j souhaités.

Je dois l'appliquer à la main sur plusieurs exemples ... et je coince sur un exemple que j'ai pris au bol. Le voici :
Code :

{6,2,3,9,2,6,1,8,4}

Arrivé un moment, il faut changer de clé de référence ou quelque chose comme ca, et c'est là que je bloque si je devais l'expliquer à quelqu'un.

Quelqu'un peut-il m'expliquer pas à pas l'arrangement de ce petit tableau ?

merci

PS: Il y'a-til des cas limites, cas particuliers, valeur(s) problématique(s) de la clé de référence que je pourrais rencontrer en metant en oeuvre cet algorithme ?

Guillemouze · Answer

je suis pas sur de comprendre l'algo. En gros, si on prend la clé 4, ca donne :

{6,2,3,9,2,6,1,8,4} 
{4,2,3,9,2,6,1,8,6}
{1,2,3,9,2,6,4,8,6}
{1,2,3,4,2,6,9,8,6}
{1,2,3,2,4,6,9,8,6}

dans ce cas, l'algo ne marche pas parcequ'il y a le 2 en double
Pire, si tu prend 2 comme clé, tu boucle a l'infini

Algo d'arrangement ( type quicksort)

1 réponse

Votre réponse

Discussions similaires