A chaque étape de mise en œuvre, nous vous guiderons à travers les différents algorithmes de tri. Python sera le composant d'implémentation. Une fois que vous avez l'algorithme, vous pouvez l'intégrer rapidement dans n'importe quel langage. C'est le sujet de la syntaxe du langage. Plongez dans les algorithmes de tri.

Comprendre l'implémentation des listes chaînées en Python

Tri par insertion

L'un des algorithmes de tri les plus simples est le type d'insertion. La mise en œuvre est facile. Et vous devrez trier un tableau plus de temps. Il n'est pas utilisé pour trier des tableaux plus grands dans la plupart des cas. La technique de type insertion conserve les sous-parties triées dans le tableau fourni. Au début du processus de tri, la sous-partie de tri ne comprend que le premier élément. Dans le sous-tableau trié, nous choisissons un élément du tableau non trié et l'insérons au bon endroit. La complexité temporelle est O(n2) et la complexité spatiale est O (1).

def insertion_sort(arr, n):
	for i in range(1, n):
		current_position = i
		current_element = arr[i]
		while current_position > 0 and current_element <
		 arr[current_position - 1]:

			arr[current_position] = arr[current_position - 1]
			current_position -= 1
		arr[current_position] = current_element
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	insertion_sort(arr, 9)
	print(str(arr))

Le tri par sélection est comme l'insertion avec un petit changement. Il sépare également le tableau en composants classés et non triés. Ensuite, nous choisissons le moindre élément de chaque itération de la sous-section non triée et l'insérons dans la position finale de la sous-section triée. La complexité temporelle est O(n2) et la complexité spatiale est O (1).

def selection_sort(arr, n):
	for i in range(n):
		min_element_index = i
		for j in range(i + 1, n):
			if arr[j] < arr[min_element_index]:
				min_element_index = j
		arr[i], arr[min_element_index] = arr[min_element_index], arr[i]
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	selection_sort(arr, 9)
	print(str(arr))

Trier les bulles est un algorithme simple. Il permute continuellement les entrées proches à chaque itération jusqu'à ce que le tableau concerné soit trié. Il traverse le panneau et pousse l'élément actuel à l'endroit suivant jusqu'à ce qu'il soit plus bas que le suivant. La complexité temporelle O(n2) et la complexité spatiale sont O (1).

def bubble_sort(arr, n):
	for i in range(n):
		for j in range(n - i - 1):
			if arr[j] > arr[j + 1]:
				arr[j], arr[j + 1] = arr[j + 1], arr[j]
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	bubble_sort(arr, 9)
	print(str(arr))

Le tri par fusion est un algorithme de tri de tableau récursif. En termes de complexité temporelle, il est plus efficace que les algorithmes présentés précédemment. Il suit l'approche de la division et de la conquête. L'algorithme de tri par fusion se décompose et trie le tableau en deux parties individuellement. Il unit les deux moitiés en un seul tableau trié après l'avoir trié. Il divise le tableau jusqu'à ce que le tableau devienne le tri le plus simple. Comme il s'agit d'un algorithme récursif. La complexité temporelle est O(nlogn) et la complexité spatiale est O(1).

def merge(arr, left_index, mid_index, right_index):
	left_array = arr[left_index:mid_index+1]
	right_array = arr[mid_index+1:right_index+1]
	left_array_length = mid_index - left_index + 1
	right_array_length = right_index - mid_index
	i = j = 0
	k = left_index
	while i < left_array_length and j < right_array_length:
		if left_array[i] < right_array[j]:
			arr[k] = left_array[i]
			i += 1
		else:
			arr[k] = right_array[j]
			j += 1
		k += 1
	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):
	if left_index >= right_index:
		return
	mid_index = (left_index + right_index) 
	merge_sort(arr, left_index, mid_index)
	merge_sort(arr, mid_index + 1, right_index)
	merge(arr, left_index, mid_index, right_index)
if __name__ == '__main__':
	arr = [2, 3, 6, 7, 8, 9, 1, 4, 5]
	merge_sort(arr, 0, 8)
	print(str(arr))