Bonjour,
Pour la fonction merge_sort vu qu'on demande d'utiliser la fonction merge et split , sachant la fonction split prend une liste et la divise en couple de deux listes (l1,l2), et que la fonction merge prend deux listes triées , je ne vois pas comment la fonction merge_sort pourrais me renvoyer une liste déja triée si la liste passée en paramètre de l'est pas, je pense que ces deux fonctions seulement ne feront pas suffisant ce que la fonction merge devrait renvoyer .
Merci,
Bonjour,
Essayez de penser à une preuve par récurrence que la fonction merge_sort est correcte, par récurence sur la taille de son parametre :
Cas de base : Les listes de longueur 0 et 1 sont triées [Check]
hypothèse : merge_sort sait trier toutes les listes de longueur comprises entre 0 et m.
hérédité : on a une liste ln de taille n, on la découpe en deux listes lk1 et lk2, telle que leur longueur vérifient : n = k1 + k2 (k1 et k2 différents de 0 et inférieur à m). Par hypothèse de récurrence, on sait trier les listes de lk1 et lk2. merge sait prendre deux listes triés et les fusionner de sorte que le résultat soit trié, et donc merge_sort sait trier une liste de taille n. [check]
(il manque quelques arguments pour en faire une preuve complète, mais l'idée est là).
Dit autrement : la magie c'est que merge_sort, par hypothèse, sait trier des listes plus petites que son paramètre. L'idée de l'algo, c'est donc de prendre son paramètre, de construire deux listes plus petites qu'elle saura trié, et de combiner ces listes triées pour retourner son paramètre trié.
Bonjour,
Je reformule (peut-être beaucoup) la réponse de Simon:
merge_sort essaie de trier les listes.
split (écrit avant merge_sort) sait les couper en deux; merge (aussi écrit avant merge_sort) sait fusionner deux listes en une liste triée, pourvu que les deux listes soient triées.
Pour effectuer le travail de merge_sort, on peut essayer de couper la liste en deux (avec split), mais pour pouvoir ensuite les fusionner en une liste triée (ce qui est l'objectif) avec merge, il faudrait que les deux listes en question soient triées - c'est-à-dire, si le travail qu'on veut confier à merge_sort (trier la liste de départ) ait été effectué sur les deux listes (plus courtes que la liste de départ).
On arrive donc à la situation suivante: pour faire effectuer son travail à merge_sort avec les outils dont on dispose déjà, il faudrait qu'on soit capable d'effectuer le même travail, sur des listes plus courtes.
C'est typiquement une situation où la récursivité est censée aider: "pour résoudre le problème posé, on résoud le même problème, mais dans un cas plus simple" (je simplifie: il faut bien sûr qu'il y ait des cas où on n'a pas besoin de faire d'appel récursif - mais Simon vous a mis sur la voie: les listes courtes (de longueur 0 ou 1) sont toujours triées).