Aller au contenu principal

Atelier 18 - Système de classement d'un tournoi eSport

Créez un programme Java qui simule le classement d'un tournoi eSport, en implémentant le tri par insertion, le tri par tas (Heap Sort) et le tri indirect.

Spécifications​

1. Enum Jeu​

Créez un enum Jeu avec les valeurs : VALORANT, LEAGUE_OF_LEGENDS, CS2, ROCKET_LEAGUE, OVERWATCH.

2. Classe Joueur​

Créez une classe Joueur avec les attributs suivants :

  • id (int)
  • pseudo (String)
  • jeu (Jeu)
  • score (int) — points accumulés dans le tournoi
  • rang (String) — ex. "Bronze", "Argent", "Or", "Platine", "Diamant"

Redéfinissez toString() pour afficher :

#id [JEU] pseudo — score pts (rang)

3. Données initiales​

Créez une liste de 15 joueurs minimum couvrant tous les jeux, avec des scores variés entre 0 et 10 000.

Exemple de quelques joueurs :

new Joueur(1,  "Shadow42",   Jeu.VALORANT,          8500, "Diamant"),
new Joueur(2,  "NightFury",  Jeu.CS2,               6200, "Platine"),
new Joueur(3,  "Pixel",      Jeu.LEAGUE_OF_LEGENDS, 3100, "Or"),
new Joueur(4,  "ZeroTwo",    Jeu.ROCKET_LEAGUE,     9800, "Diamant"),
new Joueur(5,  "BladeX",     Jeu.OVERWATCH,         1500, "Bronze"),
// ... au moins 10 autres

Copiez la liste en tableau int[] scores contenant uniquement les scores, dans le même ordre que la liste — vous l'utiliserez pour les tris de primitives.

Section 4 — Tri par insertion​

4a. Implémenter insertionSort​

Implémentez la méthode suivante sur le tableau de scores (une copie) :

public static void insertionSort(int[] arr) { ... }

Affichez le tableau avant et après le tri.

4b. Tracer l'exécution​

Modifiez votre méthode pour qu'elle affiche l'état du tableau après chaque insertion :

Avant : [8500, 6200, 3100, 9800, 1500, ...]
Étape 1 : [6200, 8500, 3100, 9800, 1500, ...]
Étape 2 : [3100, 6200, 8500, 9800, 1500, ...]
...
Après  : [1500, 3100, 6200, 8500, 9800, ...]

4c. Cas meilleur / pire cas​

Créez deux tableaux supplémentaires :

  • dejaTrie : les scores dans l'ordre croissant (meilleur cas, O(n))
  • inverseTrie : les scores dans l'ordre décroissant (pire cas, O(n²))

Pour chacun, comptez le nombre total de déplacements effectués par insertionSort et affichez-les. Vérifiez que le pire cas produit nettement plus de déplacements.

Section 5 — Tri par tas (Heap Sort)​

5a. Implémenter heapSort​

Implémentez les deux méthodes suivantes sur une copie du tableau scores :

public static void heapSort(int[] arr) { ... }
private static void heapify(int[] arr, int n, int i) { ... }

Affichez le tableau avant et après le tri.

5b. Visualiser la construction du tas​

Modifiez heapSort pour afficher l'état du tableau après la Phase 1 (construction du max-heap) :

Avant Phase 1 : [8500, 6200, 3100, 9800, 1500, ...]
Après Phase 1 (max-heap) : [9800, 8500, 3100, 6200, 1500, ...]

Vérifiez manuellement que arr[0] est bien le plus grand élément.

5c. Comparaison Insertion Sort vs Heap Sort​

Générez un tableau de 50 000 entiers aléatoires entre 1 et 1 000 000 (new Random().ints(50_000, 1, 1_000_000).toArray()).

Mesurez et affichez le temps d'exécution de chaque algorithme sur une copie identique du tableau :

Insertion Sort : X ms
Heap Sort      : X ms

Pour 50 000 éléments, Heap Sort (O(n log n)) devrait être significativement plus rapide qu'Insertion Sort (O(n²)).

Section 6 — Tri indirect​

6a. Tri indirect par score​

Créez un tableau Integer[] tabIndex = {0, 1, 2, ..., n-1} (un index par joueur).

Triez tabIndex par score décroissant en comparant les joueurs via leurs indices :

Arrays.sort(tabIndex, (a, b) -> joueurs.get(b).getScore() - joueurs.get(a).getScore());

Affichez le classement final en lisant les joueurs via tabIndex :

Classement final (par score décroissant) :
1. ZeroTwo    — 9800 pts (Diamant) [ROCKET_LEAGUE]
2. Shadow42   — 8500 pts (Diamant) [VALORANT]
3. NightFury  — 6200 pts (Platine) [CS2]
...

Vérifiez que la liste originale des joueurs n'a pas été modifiée (affichez-la après pour confirmer).

6b. Tri indirect par pseudo (alphabétique)​

Créez un second tableau d'indices Integer[] tabIndexAlpha.

Triez-le cette fois par pseudo en ordre alphabétique :

Arrays.sort(tabIndexAlpha, (a, b) -> joueurs.get(a).getPseudo().compareTo(joueurs.get(b).getPseudo()));

Affichez la liste des joueurs dans l'ordre alphabétique de leur pseudo.

6c. Deux ordres, un seul tableau​

Affichez côte à côte les deux classements (score et alphabétique) sur une même itération, en accédant aux mêmes objets Joueur via les deux tableaux d'indices :

Score          | Alphabétique
----------------------------
ZeroTwo  9800  | BladeX   1500
Shadow42 8500  | NightFury 6200
...

Confirmez que la liste originale est identique à sa création — c'est l'avantage clé du tri indirect.

6d. Tri indirect avec Heap Sort (défi)​

Implémentez un tri indirect en utilisant votre propre heapSort (section 6) au lieu de Arrays.sort().

Adaptez heapSort et heapify pour qu'ils trient un tableau int[] indices en comparant les scores via joueurs.get(indices[i]).getScore().

Vérifiez que le résultat est identique à celui de la section 6a.

Récapitulatif des complexités​

À la fin de votre programme, affichez un tableau comparatif (sous forme de commentaire ou de sortie console) :

Algorithme       | Meilleur   | Moyen      | Pire       | Mémoire
-----------------------------------------------------------------
Insertion Sort   | O(n)       | O(n²)      | O(n²)      | O(1)
Heap Sort        | O(n log n) | O(n log n) | O(n log n) | O(1)
Tri indirect     | —          | O(n log n) | O(n log n) | O(n)