Exercice 0 - Tri par sélection

• Problème 0 : Ecrivez une fonction find-min qui trouve le minimum d'une liste en utilisant la fonction foldr de Racket. Exemples de résultats attendus :

  > (find-min '(10 33 2 7 123))
  2
  > (find-min '(32.2 0.03 45))
  0.03
  

• Problème 1 : En utilisant la fonction find-min, implémentez le tri par sélection sous la forme d'une fonction sélection-sort qui prend en entrée une liste de nombres et renvoie une liste contenant les mêmes éléments dans l'ordre croissant. Exemples de résultats attendus :

  > (selection-sort '(5 3 2 1 24 5))
  '(1 2 3 5 5 24)
  > (selection-sort '(15.3 25.2 7.62 0.23))
  '(0.23 7.62 15.3 25.2)
  

• Problème 2 : Implémentez une version récursive terminale de la fonction sélection-sort, appelée sélection-sort-tr, qui prend une liste unique en entrée et renvoie une liste triée en utilisant l'algorithme de tri par sélection.

Exercice 1 - Tri à bulles

• Problème 0 : Implémentez une fonction compare-and-swap qui, étant donné deux nombres, renvoie une paire contenant ces nombres dans l'ordre croissant. Exemples de résultats attendus :

  > (compare-and-swap 7 2)
  '(2 . 7)
  > (compare-and-swap 0 2)
  '(0 . 2)
  

• Problème 1 : En utilisant la fonction compare-and-swap précédemment implémentée, implémentez une fonction bubble-iteration qui, étant donné une liste, effectue une itération de l'algorithme de tri à bulles : étant donné une liste, comparez tous les éléments de la liste par paires contiguës et permutez-les si nécessaire afin que les éléments de chaque paire soient dans un ordre croissant. Exemples de résultats attendus :

  > (bubble-iteration '(5 4 3 2 1))
  '(4 3 2 1 5)
  > (bubble-iteration '(3 2 1 5 4))
  '(2 1 3 4 5)
  > (bubble-iteration '(2 1 3 4 5))
  '(1 2 3 4 5)
  

• Problème 2 : En utilisant la fonction bubble-iteration précédemment implémentée, implémentez l'algorithme de tri à bulles sous la forme d'une fonction bubble-sort qui, étant donné une liste l de nombres et le nombre iter, renvoie le résultat de l'application de iter itérations de bubble-iteration à l. Exemples de résultats attendus :

  > (bubble-sort '(5 4 3 2 1) 0)
  '(5 4 3 2 1)
  > (bubble-sort '(5 4 3 2 1) 1)
  '(4 3 2 1 5)
  > (bubble-sort '(5 4 3 2 1) 2)
  '(3 2 1 4 5)
  > (bubble-sort '(5 4 3 2 1) 3)
  '(2 1 3 4 5)
  > (bubble-sort '(5 4 3 2 1) 4)
  '(1 2 3 4 5)
  > (bubble-sort '(5 4 3 2 1) 5)
  '(1 2 3 4 5)
  

Exercice 2 - Tri pair-impair

Le but de cet exercice est d'implémenter l'algorithme de tri pair-impair, qui, lorsqu'on lui fournit une liste l et un nombre d'itérations iter à effectuer, fait ce qui suit :

1. Si iter est pair, il compare chaque élément ayant un indice pair dans l avec son voisin et les échange si nécessaire pour qu'ils soient dans l'ordre croissant.
2. Si iter est impair, faites de même pour chaque élément dont l'indice dans l est impair.

-Problème 0 : Implémentez une variante de la fonction compare-and-swap ci-dessus qui retourne une liste de ses arguments dans l'ordre croissant au lieu d'une paire.

-Problème 1 : En utilisant la fonction compare-and-swap-2, implémentez une fonction appelée even-iteration qui prend une liste et fait ce qui suit :

1. Si la taille de la liste est inférieure à 4, elle exécute l'algorithme bubble-sort implémenté précédemment pour 2 itérations. implémenté précédemment pour 2 itérations.
2. Sinon, il compare et échange chaque élément ayant un indice pair dans l avec son voisin en utilisant compare-and-swap-2.

-Problème 2 : Implémenter une fonction remove-first-last qui prend en entrée une liste l (que nous supposons être de taille au moins 2) et retourne une liste contenant les mêmes éléments, dans leur ordre original, à l'exception du premier et du dernier.

-Problème 3 : En utilisant remove-first-last et even-iteation, implémentez une fonction odd-iteration qui, étant donné une liste l, fait ce qui suit :

1. Si la taille de la liste est inférieure à 4, elle exécute l'algorithme bubble-sort implémenté précédemment pour 2 itérations. implémenté précédemment pour 2 itérations.
2. Sinon, il compare et échange chaque élément ayant un indice impair dans l avec son voisin en utilisant compare-and-swap-2.

Devoir à rendre sur moodle

En utilisant les fonctions even-iteration et odd-iteration, implémentées ci-dessus, implémentez une fonction odd-even-sort qui prend une liste l et un nombre iter d'itérations à effectuer et implémente l'algorithme de tri pair-impair décrit ci-dessus :

1. si iter est 0, la fonction renvoie l,
2. si il est pair, elle applique l'itération paire à l et s'appelle elle-même récursivement sur la même liste avec iter-1 comme second argument.
3. s'il est impair, alors il applique odd-iteration à l et s'appelle récursivement sur la même liste avec iter-1 comme second argument.