Programme Python pour le tri par fusion

En tant que langage de programmation multi-paradigme avec une approche de conception structurée et orientée objet et une syntaxe et une grammaire simples et épurées, Python émerge rapidement comme le langage de choix pour les programmeurs travaillant sur des projets de complexité et d'échelle variables.

Python fournit une bibliothèque modulaire d'algorithmes prédéfinis qui permet à ses utilisateurs d'effectuer diverses opérations susceptibles de les aider à accomplir leur tâche par eux-mêmes ou de servir d'étape sur la voie de la réalisation d'un objectif plus vaste et plus complexe. L'un des algorithmes de ce type les plus populaires est celui qui active la fonctionnalité Merge Sort.

Qu'est-ce que le tri par fusion ?

Il s'agit d'une technique de tri à usage général qui permet aux utilisateurs de prendre un ensemble de données aléatoire de n'importe quel type et de n'importe quelle source et de le diviser en étapes répétitives jusqu'à ce qu'il soit finalement décomposé en ses composants individuels - une technique récursive, communément appelée ' méthode "diviser pour mieux régner".

L'algorithme assemble ensuite les composants individuels - encore une fois par étapes répétitives - mais les trie dans une séquence logique prédéterminée à chaque étape, en utilisant la comparaison de base et l'échange jusqu'à ce que la série de données entière soit reconstituée dans la séquence logique souhaitée. .

Découvrez nos autres cours de science des données chez upGrad.

Technique Diviser pour mieux régner

Prenons, par exemple, un jeu de données aléatoire de lettres de l'alphabet : N, H, V, B, Q, D, Z, R.

Étape 1 : L'ensemble de données d'origine est d'abord divisé en deux groupes comme suit :

N, H, V, B Q, D, Z, R

Étape 2 : Les deux tableaux résultants sont subdivisés comme suit :

N, H V, B Q, D Z, R

Étape 3 : Enfin, les quatre tableaux sont recrachés jusqu'à ce que la série de données entière soit décomposée en ses composants individuels :

N H V B Q D Z R

Le processus s'inverse ensuite et les points de données individuels commencent maintenant à fusionner par étapes. Mais au cours de ce processus de fusion, chaque élément de chaque sous-tableau est évalué et échangé afin qu'il se trie dans une séquence logique (ordre alphabétique), comme suit :

Étape 4 : Les éléments individuels fusionnent en paires tout en échangeant les positions nécessaires pour former la séquence correcte :

H, N B, V D, Q R, Z

Étape 5 : Le processus récursif de fusion et de tri se poursuit jusqu'à l'itération suivante :

B, H, N, V ​​D, Q, R, Z

Etape 6 : L'ensemble de la série de données est finalement reconstitué dans son ordre alphabétique logique :

B, D, H, N, Q, R, V, Z

Explorez nos cours populaires en science des données

Implémentations de tri par fusion

Il existe deux approches pour l'implémentation de Merge Sort en Python. L'approche descendante et l'approche ascendante.

Approche descendante :

L'approche descendante la plus couramment utilisée est celle décrite ci-dessus. Cela prend plus de temps et utilise plus de mémoire, et est donc inefficace lorsque vous travaillez avec des ensembles de données plus petits. Cependant, il est beaucoup plus fiable, en particulier lorsqu'il est appliqué à de grands ensembles de données.

Lisez nos articles populaires sur la science des données

Code d'entrée :

def merge_sort (inp_arr):

taille = len(inp_arr)

si taille > 1 :

milieu = taille // 2

arr_gauche = inp_arr(:milieu)

rIght_arr = inp_arr(milieu :)

merge_sort(left_arr)

fusionner _sort(right_arr)

je = 0

j = 0

k = 0

(Où i et j sont les itérateurs pour parcourir les moitiés gauche et droite de la série de données, respectivement, et k est l'itérateur de la série de données globale).

taille_gauche = len(arr_gauche)

right _size = len(right_arr)

tandis que je < taille_gauche et j < taille droite :

si tab_gauche(i) < tab_droit (j) :

inp_arr(k) – left_arr(i)

je >= 1

autre:

inp_arr(k) = right_arr (j)

j += 1

k += 1

tant que je <taille_gauche :

inp_arr (k) = left_arr(i)

je += 1

k += 1

tandis que j < taille_droite :

inp_arr (k) = right_arr(j)

j += 1

k += 1

inp_arr = (N, H, V, B, Q, D, Z, R)

print(:Tableau d'entrée:\n”)

impression(inp_arr)

merge_sort (inp_arr)

print("Tableau trié :\n")

imprimer (inp_arr)

Sortir:

Tableau d'entrée : N, H, V, B, Q, D, Z, R

Tableau de sortie : B, D, H, N, Q, R, V, Z

Une approche en profondeur:

L'approche ascendante est plus rapide, utilise moins de mémoire et fonctionne efficacement avec des ensembles de données plus petits, mais peut rencontrer des problèmes lorsque vous travaillez avec des ensembles de données volumineux. Il est donc moins utilisé.

Code d'entrée :

def fusionner(gauche, droite):

résultat = [] x, y = 0, 0

pour k dans la plage (0, len(gauche) + len(droite)) :

if i == len(left): # if à la fin de la 1ère mi-temps,

result.append(right[j]) # ajoute toutes les valeurs de la 2ème mi-temps

j += 1

elif j == len(right): # si à la fin de la 2ème mi-temps,

result.append(left[x]) # ajoute toutes les valeurs de la 1ère mi-temps

je += 1

elif droite[j] < gauche[i] :

result.append(droit[j])

j += 1

autre:

result.append(gauche[i])

je += 1

résultat de retour

def mergesort(ar_list):

longueur = len(ar_list)

taille = 1

tant que taille < longueur :

size+=size # s'initialise à 2 comme décrit

pour pos dans la plage (0, longueur, taille):

début = position

milieu = pos + int(taille / 2)

fin = pos + taille

gauche = ar_list[ début : milieu ] droite = ar_list[ milieu : fin ]

ar_list[début:fin] = fusionner(gauche, droite)

retourner ar_list

ar_list = [N, H, V, B, Q, D, Z, R] print(mergesort(ar_list))

Sortir:

Tableau d'entrée : N, H, V, B, Q, D, Z, R

Tableau de sortie : B, D, H, N, Q, R, V, Z

Implémentation de Merge Sort appliquée à des ensembles de données réels plus complexes

Appliquons l'approche descendante à quatre véhicules tout-terrain aléatoires en Inde :

Code d'entrée :

Voiture de classe :

def __init__(soi, marque, modèle, prix):

self.brand = marque

self.model = modèle

soi.prix = prix

def __str__(soi) :

return str.format("Marque : {}, Modèle : {}, Prix : {}", self.brand,

self.model, self.price)

def merge(list1, i, j, k, comp_fun):

copie_gauche = liste1[i:k + 1]

r_sous-liste = liste1[k+1:r+1]

index_copie_gauche = 0

j_sublist_index = 0

index_trié = je

tandis que left_copy_index < len(left_copy) etj_sublist_index <

len(j_sublist):

si comp_fun(left_copy[left_copy_index], j_sublist[j_sublist_index]):

list1[sorted_index] = left_copy[left_copy_index]

left_copy_index = left_copy_index + 1

sinon :

liste1[index_trié] = j_sous-liste[j_sous-liste_index]

j_sublist_index = j_sublist_index + 1

index_trié = index_trié + 1

tandis que left_copy_index < len(left_copy):

list1[sorted_index] = left_copy[left_copy_index]

left_copy_index = left_copy_index + 1

index_trié = index_trié + 1

tandis que j_sublist_index < len(j_sublist) :

liste1[index_trié] = j_sous-liste[j_sous-liste_index]

j_sublist_index = j_sublist_index + 1

index_trié = index_trié + 1

def merge_sort(list1, i, j, comp_fun):

si je >= j :

revenir

k = (je + j)//2

merge_sort(list1, je, k, comp_fun)

merge_sort(list1, k + 1, j, comp_fun)

fusionner(list1,i, j, k, comp_fun)

voiture1 = Voiture("Jeep", "Wrangler", 0.58)

voiture2 = Voiture("Ford", "Endeavour", 0.35)

voiture3 = Voiture ("Jaguar Land Rover", "Range Rover Sport", 1.76)

voiture4 = Voiture ("Mercedes Benz", "Classe G", 2.42)

liste1 = [voiture1, voiture2, voiture3, voiture4]

merge_sort(list1, 0, len(list1) -1, lambda carA, carB : carA.brand < carB.brand)

imprimer ("Voitures triées par marque :")

pour la voiture dansla liste1 :

impression (voiture)

imprimer ()

merge_sort(list1, 0, len(list1) -1, lambda voitureA, voitureB : voitureA.prix < voitureB.prix)

print ("Voitures triées par prix :")

pour la voiture dansla liste1 :

impression (voiture)

Sortir:

Voitures triées par marque :

Ford Endeavour

Jaguar Land Rover Range Rover Sport

Jeep Wrangler

Mercedez Benz Classe G

Voitures triées par prix :

Ford Endeavour

Jeep Wrangler

Jaguar Land Rover Range Rover

Mercedez Benz Classe G

Vous pouvez apprendre les aspects théoriques et pratiques de Python avec le certificat professionnel upGrad en science des données et analyse commerciale de l'Université du Maryland. Ce cours vous aide à apprendre Python à partir de zéro. Même si vous êtes novice en programmation et en codage, upGrad vous proposera un cours préparatoire de deux semaines afin que vous puissiez acquérir les bases de la programmation. vous découvrirez divers outils tels que Python, SQL, tout en travaillant sur plusieurs projets industriels.

Planifiez votre carrière en développement de logiciels dès maintenant !

Postuler au programme de certificat professionnel en science des données et analyse commerciale