Version imprimable
bonjour,
voila je cherche un algorithme lineaire qui me permet de faire la chose suivante
soit un vecteur et une valeur pivot, apres etre passé dans l'agorithme, toute les valeurs plus petites que le pivot sont a gauche, et toute les valeurs plus grandes sont a droites.
le hic, c'est que la seul operation permise est le swap de deux element (pas de recopiage de vecteur, etc..etc..) autre chose cela doit etre absolument lineaire.
merci
a+
Il te faut deux indices, un qui part du "bas" du vecteur l'autre qui part du "haut".
Phase 1 : Tant que les valeurs indicées par le bas sont inférieures au pivot, tu augmentes l'indice.
Dès que tu arrives à une valeur plus grande, tu passes à la phse 2
Phase 2 : tu prends l'indice haut, tant que les valeurs indicées par l'indice haut sont plus grandes que le pivot, tu descends. Quand tu arrives à une valeur plus petite, tu intervertis les deux valeurs indicées et tu recommences en phase 1.
Attention, c'est l'idée, il faut écrire l'algo détaillé maintenant.
merci, apres un peu de recherche, c'est sur quoi je suis tomber
a++