Algorithmes de tri récursifs et non récursifs - algorithme, tri, récursivité

Quelqu'un peut-il expliquer en anglais en quoi des implémentations non récursives et récursives d'algorithmes de tri diffèrent les unes des autres?

Réponses:

Les algorithmes de tri récursif fonctionnent en divisant l’entrée en deux ou plusieurs entrées plus petites, puis en les triant, puis en combinant les résultats. Tri par fusion et tri rapide sont des exemples d'algorithmes de tri récursif.

Une technique non récursive est tout ce qui n’utilise pas la récursivité. Tri par insertion est un exemple simple d'algorithme de tri non récursif.

Comment ils diffèrent, dans quel sens? Gardez à l’esprit: tout algorithme récursif peut être implémenté en tant qu’algorithme itératif, et inversement (regardez ceci poster). Itération ou récursion - c’est juste un détail d’implémentation; bien que cela puisse avoir un impact majeur sur les performances en fonction du choix, l’algorithme sera néanmoins le même.

Un algorithme de tri récursif fait appel à lui-même pour trier une plus petite partie du tableau, puis combine les résultats partiellement triés. Quick-sort est un exemple.

Un algorithme non récursif effectue le tri en une seule fois, sans s'appeler lui-même. Le tri en bulle est un exemple d'algorithme non récursif.