Fiche de révision : Mélanger et inverser un tableau

Plan du Cours

  1. Échange de deux cases
  2. Mélange de Fisher–Yates
  3. Inversion d’un préfixe
  4. Copie et partage de tableaux

1. Échange de deux cases

Points essentiels

  • Pour échanger tab[i] et tab[j] sans perdre leur valeur, on copie d’abord tab[i] dans une variable temporaire, on affecte tab[j] à tab[i], puis on affecte la variable temporaire à tab[j].

Astuce mémo

Sauver, remplacer, restituer : temporaire → première case → seconde case.

2. Mélange de Fisher–Yates

★ À maîtriser

  • Dans le mélange moderne de Fisher–Yates, aussi appelé mélange de Durstenfeld, on part de i = tableau.length - 1, on tire uniformément j entre 0 et i inclus, on échange les cases i et j, puis on recommence avec i - 1 jusqu’à i = 1.

📌 L’expression (int)(Math.random() * i) produit un indice de 0 à i - 1, tandis que Fisher–Yates exige un indice de 0 à i inclus ; elle ne permet donc pas de tirer la case i.

  • Pour un tableau de taille n ≥ 1, Fisher–Yates effectue exactement n−1n - 1 tirages et échanges, avec un temps Θ(n) et une mémoire auxiliaire Θ(1).

Compléments

  • Dans Java, nextInt(i + 1) renvoie un entier compris entre 0 inclus et i + 1 exclu, soit un indice de 0 à i inclus.

  • Le mélange d’un tableau vide ne demande aucun échange.

Astuce mémo

Dernière case → tirage jusqu’à i inclus → échange → reculer jusqu’à 1.

3. Inversion d’un préfixe

★ À maîtriser

  • Pour inverser les k premières cases, on échange les indices 0 et k - 1, puis 1 et k - 2, et ainsi de suite jusqu’à ce que les indices se rejoignent ou se croisent ; les cases à partir de k restent inchangées.

📐 Formule - L’inversion d’un préfixe de longueur k effectue ⌊k/2⌋\lfloor k/2 \rfloor échanges, prend un temps Θ(k) et utilise une mémoire supplémentaire Θ(1).

Compléments

📌 L’inversion d’un préfixe exige la précondition 0 ≤ k ≤ tab.length.

  • Inverser le préfixe de longueur 5 de [5, 4, 6, 2, 1, 7, 9, 8, 3] donne [1, 2, 6, 4, 5, 7, 9, 8, 3].

  • Pour inverser tout le tableau, il faut choisir k = tab.length.

Astuce mémo

Deux indices se rapprochent depuis les extrémités du préfixe.

4. Copie et partage de tableaux

★ À maîtriser

📌 La méthode clone() crée un tableau indépendant contenant une copie des entiers, tandis que l’affectation int[] alias = depart crée un second nom pour le même tableau.

Compléments

  • Conserver le tableau de départ et effectuer des opérations sur une copie permet de rejouer la même configuration.

  • Une copie superficielle d’un tableau int[][] ne copie pas ses lignes.

Astuce mémo

clone() crée un autre tableau ; l’affectation donne un second nom au même tableau.

Teste tes connaissances

Teste tes connaissances sur Mélanger et inverser un tableau avec 7 questions à choix multiples et corrections détaillées.

1. Dans un tableau, `tab[i]` vaut 12 et `tab[j]` vaut 5. Quelle suite d’affectations échange ces valeurs sans en perdre une ?

2. Un tableau contient 6 éléments. Lors d’une étape de Fisher–Yates, quelle opération faut-il effectuer lorsque l’indice actif vaut i = 4 ?

Faire le QCM →

Révisez avec les flashcards

Mémorisez les concepts clés de Mélanger et inverser un tableau avec 10 flashcards interactives.

Quelle valeur faut-il copier dans une variable temporaire pour échanger tab[i] et tab[j] ?

La valeur de tab[i].

Après avoir affecté tab[j] à tab[i], que faut-il affecter à tab[j] ?

La variable temporaire.

Comment choisit-on l’indice d’échange à l’étape i du mélange moderne de Fisher–Yates ?

Uniformément entre 0 et i, bornes incluses.

Voir les flashcards →

Cours similaires

Crée tes propres fiches de révision

Importe ton cours et l'IA génère fiches, QCM et flashcards en 30 secondes.

Générateur de fiches