2 minutes
Tri Par Fusion Avec Python
Dernière mise à jour: 26 septembre, 2022Probablement mon algorithme de tri préféré et celui qui a pris le plus de temps à comprendre. J'espère pouvoir vous aider à comprendre comment fonctionne cet algorithme. Nous divisons essentiellement notre tableau (ou liste) de manière récursive jusqu'à ce que les morceaux soient suffisamment petits pour être triés. Enfin, nous pouvons commencer à les trier et lancer la "fusion". Cela semble vraiment simple, non ? Allons droit au but !
§Un Exemple Pour Nous Aider À Comprendre
Tout d'abord, je suppose que vous comprenez la récursivité de base. Comme nous ne ferons pas vraiment quelque chose de compliqué, ne vous inquiétez pas si vous n'êtes pas un expert en récursivité.
Supposons que nous voulions trier ce tableau:
arr = [42, 25, 37, 2, 11, 76, 12]
Nous allons diviser et commencer à trier/fusionner du côté gauche de manière récursive. Dans la première étape :
[42, 25, 37, 2] --- [11, 76, 12]
Dans la deuxième étape :
[42, 25] --- [37, 2] --- [11, 76, 12]
Dans la troisième étape :
[42] --- [25] --- [37, 2] --- [11, 76, 12]
Nous pouvons maintenant commencer à trier à partir du côté gauche. Disons que nous voulons aller du min au max dans notre tableau. Tout d'abord, nous allons trier 42 et 25. Donc dans la quatrième étape :
[25, 42] --- [37, 2] --- [11, 76, 12]
Dans la cinquième étape :
[25, 42] --- [37] --- [2] --- [11, 76, 12]
Dans la sixième étape :
[25, 42] --- [2, 37] --- [11, 76, 12]
A la septième étape :
[2, 25, 37, 42] --- [11, 76, 12]
A la huitième étape :
[2, 25, 37, 42] --- [11, 76] --- [12]
Dans le neuvième épisode :
[2, 25, 37, 42] --- [11] --- [76] --- [12]
A la dixième étape :
[2, 25, 37, 42] --- [11, 76] --- [12]
A la onzième étape :
[2, 25, 37, 42] --- [11, 12, 76]
Et enfin dans la douzième étape :
[2, 11, 12, 25, 37, 42, 76]
Cet algorithme nous aide à comprendre l'importance des algorithmes "divide and conquer". Nous divisons simplement le problème en petits morceaux plus faciles à résoudre. The code for this algorithm actually looks like this:
def mergeSort(nums):
if len(nums) <= 1:
return nums
if len(nums) > 1:
mid = len(nums) // 2
left = nums[:mid]
right = nums[mid:]
mergeSort(left)
mergeSort(right)
i = 0
j = 0
k = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
nums[k] = left[i]
i += 1
else:
nums[k] = right[j]
j += 1
k += 1
while i < len(left):
nums[k] = left[i]
i += 1
k += 1
while j < len(right):
nums[k] = right[j]
j += 1
k += 1
numbers = [42, 25, 37, 2, 11, 76, 12]
mergeSort(numbers)
print(numbers)
§Complexité Du Tri Par Fusion
La complexité temporelle du tri par fusion est O(nlogn) puisque nous divisons notre tableau en deux n fois environ. Comme vous pouvez le voir, le tri par fusion n'est peut-être pas l'algorithme le plus rapide pour trier des tableaux/listes relativement plus grands. Il est suggéré d'utiliser le tri par fusion sur des listes liées relativement plus petites.
La complexité spatiale du tri par fusion est O(n). Créer tous ces sous-tableaux pour les trier plus tard allait bien sûr nous coûter cher. Donc, si vous manquez d'espace, ne choisissez peut-être pas le tri par fusion.
En termes de stabilité, nous pouvons être sûrs que le tri par fusion est stable. Nous utilisons "gauche < droite" pour comparer les éléments. En cas d'égalité, nous copions d'abord la valeur de gauche dans notre tableau, puis celle de droite. Ainsi notre commande est préservée. Cela prouve que le tri par fusion est stable.
Continuez à apprendre!
Ilker AkbiyikTable Des Matières
Articles Similaires
