• Assurez la sécurité des applications de la bonne manière! Détectez, protégez, surveillez, accélérez et plus encore…
  • Le tri est l'une des fonctionnalités les plus utilisées en programmation. Et il faudra du temps pour terminer le tri si nous n'utilisons pas le bon algorithme.

    Dans cet article, nous allons discuter de différents algorithmes de tri.

    Nous vous guiderons à travers les différents algorithmes de tri à chaque étape de la mise en œuvre. La partie mise en œuvre sera en Python. Vous pouvez facilement le convertir dans n'importe quelle langue une fois que vous obtenez l'algorithme. C'est la question de la syntaxe du langage.

    Nous verrons différents algorithmes du pire au meilleur dans ce tutoriel. Alors ne t'inquiète pas. Suivez l'article et mettez-les en œuvre.

    Plongeons dans les algorithmes de tri.

    Tri par insertion

    Le tri par insertion est l'un des algorithmes de tri simples. C'est facile à mettre en œuvre. Et cela vous coûtera plus de temps pour trier un tableau. Il ne sera pas utilisé dans la plupart des cas pour trier des tableaux plus grands.

    La tri par insertion L'algorithme maintient les sous-parties triées et non triées dans le tableau donné.

    La trié La sous-partie contient uniquement le premier élément au début du processus de tri. Nous prendrons un élément du tableau non trié et le placerons à la bonne position dans le sous-tableau trié.

    Voyons les illustrations visuelles de tri par insertion étape par étape avec un exemple.

    Voyons les étapes pour mettre en œuvre le tri par insertion.

    • Initialisez le tableau avec des données factices (entiers).
    • Itérer sur le tableau donné à partir du deuxième élément.
      • Prenez la position actuelle et l'élément dans deux variables.
      • Ecrivez une boucle qui itère jusqu'à ce que le premier élément du tableau ou l'élément inférieur à l'élément actuel apparaisse.
        • Mettez à jour l'élément actuel avec l'élément précédent.
        • Décrémentation de la position actuelle.
      • Ici, la boucle doit atteindre le début du tableau ou trouver un élément plus petit que l'élément courant. Remplacez l'élément de position actuel par l'élément actuel.

    La complexité temporelle du tri par insertion is O (n ^ 2), et la complexité de l'espace si O (1).

    C'est ça; nous avons trié le tableau donné. Exécutons le code suivant. J'espère que vous avez installé Python, sinon consultez le guide d'installation. Vous pouvez également utiliser un compilateur Python en ligne.

    def insertion_sort(arr, n):
    	for i in range(1, n):
    
    		## current position and element
    		current_position = i
    		current_element = arr[i]
    
    		## iteratin until
    		### it reaches the first element or
    		### the current element is smaller than the previous element
    		while current_position > 0 and current_element <
    		 arr[current_position - 1]:
    			## updating the current element with previous element
    			arr[current_position] = arr[current_position - 1]
    
    			## moving to the previous position
    			current_position -= 1
    
    		## updating the current position element
    		arr[current_position] = current_element
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	insertion_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Tri de sélection

    Le tri par sélection est similaire au tri par insertion avec une légère différence. Cet algorithme divise également le tableau en sous-parties triées et non triées. Et puis, à chaque itération, nous prendrons l'élément minimum du sous-partie non triée et placez-le dans la dernière position du sous-partie triée.

    Let's illustrations de tri par sélection pour une meilleure compréhension.

    Voyons les étapes pour mettre en œuvre le tri par sélection.

    • Initialisez le tableau avec des données factices (entiers).
    • Itérer sur le tableau donné.
      • Conservez l'index de l'élément minimum.
      • Ecrivez une boucle qui itère de l'élément courant au dernier élément.
        • Vérifiez si l'élément actuel est inférieur ou non à l'élément minimum.
        • Si l'élément actuel est inférieur à l'élément minimum, remplacez l'index.
      • Nous avons l'index minimum des éléments avec nous. Échangez l'élément actuel avec l'élément minimum à l'aide des index.

    La complexité temporelle du tri par sélection is O (n ^ 2), et la complexité de l'espace si O (1).

    Essayez d'implémenter l'algorithme car il est similaire au tri par insertion. Vous pouvez voir le code ci-dessous.

    def selection_sort(arr, n):
    	for i in range(n):
    
    		## to store the index of the minimum element
    		min_element_index = i
    		for j in range(i + 1, n):
    			## checking and replacing the minimum element index
    			if arr[j] < arr[min_element_index]:
    				min_element_index = j
    
    		## swaping the current element with minimum element
    		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	selection_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Tri des bulles

    Le tri à bulles est un algorithme simple. Il échange les éléments adjacents à chaque itération à plusieurs reprises jusqu'à ce que le tableau donné soit trié.

    Il itère sur le tableau et déplace l'élément actuel vers la position suivante jusqu'à ce qu'il soit inférieur à l'élément suivant.

    Les illustrations nous aident à comprendre tri à bulles visuellement. Voyons-les.

    Voyons les étapes pour mettre en œuvre le tri à bulles.

    1. Initialisez le tableau avec des données factices (entiers).
    2. Itérer sur le tableau donné.
      1. Itérer à partir de à ni-1. Le dernier i les éléments sont déjà triés.
        1. Vérifiez si l'élément actuel est supérieur ou non à l'élément suivant.
        2. Si l'élément actuel est supérieur à l'élément suivant, permutez les deux éléments.

    La complexité temporelle du tri à bulles is O (n ^ 2), et la complexité de l'espace si O (1).

    Vous pouvez facilement implémenter le tri à bulles maintenant. Voyons le code.

    def bubble_sort(arr, n):
    	for i in range(n):
    		## iterating from 0 to n-i-1 as last i elements are already sorted
    		for j in range(n - i - 1):
    			## checking the next element
    			if arr[j] > arr[j + 1]:
    				## swapping the adjucent elements
    				arr[j], arr[j + 1] = arr[j + 1], arr[j]
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	bubble_sort(arr, 9)
    
    	## printing the array
    	print(str(arr))

    Tri par fusion

    Le tri par fusion est un algorithme récursif pour trier le tableau donné. C'est plus efficace que les algorithmes discutés précédemment en termes de complexité temporelle. Il suit l'approche de division et de conquête.

    L'algorithme de tri par fusion divise le tableau en deux moitiés et les trie séparément. Après avoir trié les deux moitiés du tableau, il les fusionne en un seul tableau trié.

    Comme il s'agit d'un algorithme récursif, il divise le tableau jusqu'à ce que le tableau devienne le plus simple (tableau avec un élément) à trier.

    Il est temps d'illustrer. Voyons ça.

    Voyons les étapes pour mettre en œuvre le tri par fusion.

    • Initialisez le tableau avec des données factices (entiers).
    • Ecrire une fonction appelée fusionner pour fusionner des sous-tableaux en un seul tableau trié. Il accepte le tableau d'arguments, les index gauche, milieu et droit.
      • Obtenez les longueurs des sous-tableaux gauche et droit en utilisant les index donnés.
      • Copiez les éléments du tableau dans les tableaux gauche et droit respectifs.
      • Itérez sur les deux sous-tableaux.
        • Comparez les deux éléments de sous-tableaux.
        • Remplacez l'élément du tableau par le plus petit élément des deux sous-tableaux pour le tri.
      • Vérifiez s'il reste des éléments dans les deux sous-tableaux.
      • Ajoutez-les au tableau.
    • Ecrire une fonction appelée tri par fusion avec tableau de paramètres, index gauche et droit.
      • Si l'index de gauche est supérieur ou égal à l'index de droite, retournez.
      • Trouvez le point central du tableau pour diviser le tableau en deux moitiés.
      • Appelez récursivement le tri par fusion en utilisant les index gauche, droit et milieu.
      • Après les appels récursifs, fusionnez le tableau avec le fusionner la fonction.

    La complexité temporelle du tri par fusion is O (nlogn), et la complexité de l'espace si O (1).

    C'est tout pour l'implémentation de l'algorithme de tri par fusion. Vérifiez le code ci-dessous.

    def merge(arr, left_index, mid_index, right_index):
    	## left and right arrays
    	left_array = arr[left_index:mid_index+1]
    	right_array = arr[mid_index+1:right_index+1]
    
    	## getting the left and right array lengths
    	left_array_length = mid_index - left_index + 1
    	right_array_length = right_index - mid_index
    
    	## indexes for merging two arrays
    	i = j = 0
    
    	## index for array elements replacement
    	k = left_index
    
    	## iterating over the two sub-arrays
    	while i < left_array_length and j < right_array_length:
    
    		## comapring the elements from left and right arrays
    		if left_array[i] < right_array[j]:
    			arr[k] = left_array[i]
    			i += 1
    		else:
    			arr[k] = right_array[j]
    			j += 1
    		k += 1
    
    	## adding remaining elements from the left and right arrays
    	while i < left_array_length:
    		arr[k] = left_array[i]
    		i += 1
    		k += 1
    
    	while j < right_array_length:
    		j += 1
    		k += 1
    
    def merge_sort(arr, left_index, right_index):
    	## base case for recursive function
    	if left_index >= right_index:
    		return
    
    	## finding the middle index
    	mid_index = (left_index + right_index) // 2
    
    	## recursive calls
    	merge_sort(arr, left_index, mid_index)
    	merge_sort(arr, mid_index + 1, right_index)
    
    	## merging the two sub-arrays
    	merge(arr, left_index, mid_index, right_index)
    
    if __name__ == '__main__':
    	## array initialization
    	arr = [3, 4, 7, 8, 1, 9, 5, 2, 6]
    	merge_sort(arr, 0, 8)
    
    	## printing the array
    	print(str(arr))

    Conclusion

    Il existe de nombreux autres algorithmes de tri, mais vous trouverez ci-dessus certains des algorithmes fréquemment utilisés. J'espère que vous avez aimé apprendre le tri.

    Ensuite, découvrez algorithmes de recherche.

    Codage heureux 🙂 👨‍💻