Simulation de Algorithmes de tri

À propos de cette expérience

Observez comment bubble sort, insertion sort et merge sort transforment la même entrée pour la mettre en ordre croissant. Faites une pause lors d’une comparaison, avancez pas à pas pour chaque écriture ou remontez l’intégralité de la trace. Les décomptes distincts des comparaisons de valeurs et des écritures dans le tableau principal permettent de distinguer le travail algorithmique de la durée de l’animation.

Objectifs pédagogiques

Suivre les comparaisons et les écritures de trois algorithmes de tri par comparaison
Comparer les performances avec des entrées mélangées, triées et inversées
Distinguer la croissance quadratique dans le pire des cas de la croissance en n log n

Comment l’utiliser

1Gardez l’entrée mélangée et la longueur du tableau fixes. Exécutez bubble sort jusqu’au bout et notez le nombre de comparaisons et d’écritures.
2Redémarrez avec insertion sort, puis merge sort, en utilisant la même entrée. Comparez les décomptes finaux.
3Essayez une entrée triée et observez l’arrêt anticipé de bubble sort ainsi que le petit nombre de comparaisons d’insertion sort.
4Utilisez « Précédent » et le curseur de suivi pour examiner une fusion. Les tampons temporaires peuvent contenir des valeurs qui ne sont plus visibles à leur position d’origine dans le tableau principal.

Le modèle

C_{bubble, worst} = \frac{n ( n - 1 )}{2}

Comparaisons de valeurs de bubble sort dans le pire des cas

T_{insertion, worst} = O (n^{2}), T_{merge, worst} = O (n lo g n)

Évolution du temps d’exécution d’insertion sort et de merge sort dans le pire des cas

W_{swap} = 2

Un échange est comptabilisé comme deux écritures dans le tableau principal

Hypothèses

Les entrées contiennent des entiers uniques de 1 à n. Le mélange utilise une graine fixe afin que chaque algorithme reçoive des données identiques.
Une comparaison est un test entre des valeurs de données, et non un test d’indice ou de limite de boucle. Une écriture est une affectation dans le tableau principal, y compris lorsque la clé d’insertion reste inchangée.
Les copies dans les tampons temporaires de merge sort ne sont pas prises en compte dans le nombre d’écritures. L’utilisation de mémoire supplémentaire n’est pas incluse dans le total des opérations affiché.
La vitesse de lecture est choisie à des fins pédagogiques et ne constitue pas une mesure de performance en temps réel.

À essayer en classe

Q1Pourquoi bubble sort n’a-t-il besoin que de n − 1 comparaisons lorsque l’entrée est déjà triée dans cette implémentation ?
Q2Quel algorithme effectue le moins de comparaisons avec une entrée en ordre inverse et un tableau de même longueur ?
Q3Pourquoi le nombre d’images d’animation n’est-il pas une mesure fiable de la vitesse d’un algorithme ?

Foire aux questions

Pourquoi des valeurs semblent-elles brièvement dupliquées lors du tri par insertion ou par fusion ?

Une valeur peut être conservée dans une clé temporaire ou un tampon de fusion pendant que le tableau principal est écrasé. La visualisation affiche le contenu du tableau principal à chaque écriture ; l’unicité est rétablie une fois l’opération terminée.

Le tri par fusion utilise-t-il toujours moins d’écritures ?

Non. Le nombre de comparaisons du tri par fusion augmente efficacement, mais les résultats fusionnés sont réécrits plusieurs fois. Le nombre d’opérations dépend des données d’entrée et des affectations prises en compte.