In Développement Dernière mise à jourated:
Partager sur:
Logiciel Jira est l'outil de gestion de projet n°1 utilisé par les équipes agiles pour planifier, suivre, publier et prendre en charge d'excellents logiciels.

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 ne contient que le premier élément au début du tri process. 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).
  • iterate sur le tableau donné à partir du deuxième élément.
    • Prenez la position actuelle et l'élément dans deux variables.
    • Écrivez une boucle qui itèreates jusqu'à ce que le premier élément du tableau ou l'élément inférieur à l'élément actuel apparaisse.
      • Mise à jourate l'élément courant avec le prevélément précieux.
      • 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 mieux comprendreanding.

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

  • Initialisez le tableau avec des données factices (entiers).
  • iterate sur le tableau donné.
    • Conservez l'index de l'élément minimum.
    • Écrivez une boucle qui itèreates de l'élément actuel 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))

Bubble Sort

Bubble le tri est un algorithme simple. Il échange les éléments adjacents à chaque répétition d'itérationatequotidiennement jusqu'à ce que le tableau donné soit trié.

Il itèreates 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 bubble sort scieally. Voyons-les.

Voyons les étapes pour mettre en œuvre le bubble sort.

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

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

Vous pouvez facilement mettre en œuvre le bubble trier 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 le prevalgorithmes longuement discutés en termes de complexité temporelle. Il suit l’approche diviser pour mieux régner.

L'algorithme de tri par fusion divise le tableau en deux moitiés et les trie séparément.ately. 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.
    • iterate 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 greater supérieur ou égal à l'index de droite, puis revenez.
    • 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 🙂 👨‍💻

Partager sur:
  • Hafeezul Kareem Shaik
    Auteur
    Hafeez est développeur et aime partager ses connaissances de Python et des langages de développement émergents.

Merci à nos commanditaires

Plus de bonnes lectures sur le développement

Alimentez votre entreprise

Certains des outils et services pour aider votre entreprise grow.
  • L'outil de synthèse vocale qui utilise l'IA pour générerate des voix humaines réalistes.

    Essayez Murf AI
  • Web scraping, proxy résidentiel, proxy manager, web unlocker, moteur de recherche et tout ce dont vous avez besoin pour collecter des données Web.

    Essayez Brightdata
  • Monday.com est un système d'exploitation de travail tout-en-un pour vous aider à gérer les projets, les tâches, le travail, les ventes, le CRM, les opérations, workflowset plus encore.

    Essayez Monday
  • Intruder est un scanner de vulnérabilités en ligne qui détecte les failles de cybersécurité de votre infrastructure, afin d'éviter des violations de données coûteuses.

    Essayez Intruder