Exercice noté #4

Vous devez implémenter une variante du tri à bulle vu en cours où l'on s'interesse à trier des valeurs entières en ordre décroissant et en place, c'est-à-dire en modifiant directement le tableau passé en argument. Le tri à bulle classique (celui vu en cours) compare en boucle deux valeurs successives du tableau et les échange si elles ne sont pas dans l'ordre désiré. Cela implique que de nombreux échanges sont effectués afin de déplacer certaines valeurs à leur place. La variante que vous devez écrire effectue plusieurs passages de l'algorithme de tri à bulle, où chaque passage compare les valeurs du tableau distante d'une certaine valeur n appelé le régime. L'idée est de commencer par un régime élevé (par exemple 11) afin de comparer des valeurs éloignées (indice 0, 11, 22, etc.) dans le tableau, puis de baisser progressivement le régime, pour terminer avec un régime 1 qui correspond à l'algorithme de tri à bulle classique (où les valeurs sucessives sont comparées).

Vous devez écrire une fonction bubbleShell qui admet dans cet ordre deux arguments qui sont le tableau à trier et un tableau de régimes, c'est-à-dire, un tableau de valeurs entières strictement décroissantes et terminant par l'entier 1. Votre fonction doit retourner un tableau qui contient le nombre d'échanges effectués à chaque régime: la ieme valeur de ce tableau correspond donc au nombre d'échanges effectués par votre algorithme pour la ieme valeur dans le tableau de régime.

Voici deux exemples d'appels de votre fonction, ainsi que le détail des différentes étapes de l'algorithme. Dans le premier appel, les valeurs distantes de 5 commencent par être comparées et 53 échanges sont effectués. Le régime 3 est ensuite considéré et 15 échanges sont effectués; enfin le régime 1 est effectué (un tri à bulle classique), ce qui requiert 17 échanges. Un total de 85 échanges ont donc été effectués alors que le tri à bulle classique requiert 303 échanges, tel que mesuré par le second appel.

print(bubbleShell([1,3,2,5,4,6,7,8,10,41,43,49,22,13,24,40,20,9,9,10,1,13,45,25,43,12,48,47,25,7], [5,3,1]));
53,15,17

regime 5: 43,49,47,25,43,40,48,45,25,41,12,20,22,13,24,6,13,9,10,10,1,7,8,9,7,1,3,2,5,4
regime 3: 48,49,47,43,45,40,41,43,25,25,13,24,22,13,20,10,12,9,7,10,9,7,8,4,6,5,3,2,1,1
regime 1: 49,48,47,45,43,43,41,40,25,25,24,22,20,13,13,12,10,10,9,9,8,7,7,6,5,4,3,2,1,1

print(bubbleShell([1,3,2,5,4,6,7,8,10,41,43,49,22,13,24,40,20,9,9,10,1,13,45,25,43,12,48,47,25,7], [1]));
303

regime 1: 49,48,47,45,43,43,41,40,25,25,24,22,20,13,13,12,10,10,9,9,8,7,7,6,5,4,3,2,1,1

Vous devez également écrire une fonction best qui prend en argument un tableau ainsi qu'un tableau de tableaux de régimes et qui retourne le tableau de régimes le meilleur, c'est-à-dire celui entraînant le moins d'échanges pour le tableau donné en argument. Voici un exemple non normatif (vous pouvez afficher les choses différemment, voire ne rien afficher) d'appel où le meilleur régime est [11,9,7,3,1]

var regimes = [[1],[5,4,3,2,1],[7,3,1],[11,9,7,3,1]];
var t = [2,4,5,7,8,2,5,8,9,12,13,2,4,56,12,5,7,23,12,24,34,56,3,6,1];
print(best(t,regimes));
11,9,7,3,1

tri selon [ 1 ] en 184 echanges
tri selon [ 5,4,3,2,1 ] en 48 echanges
tri selon [ 7,3,1 ] en 63 echanges
tri selon [ 11,9,7,3,1 ] en 35 echanges


Notation: Cet exercice est noté sur 6 points. Le nom du programme à remettre est bubbleshell.js et la remise doit se faire par studium.