Em cada estágio de implementação, iremos guiá-lo através dos diferentes algoritmos de classificação. Python será o componente de implementação. Depois de ter o algoritmo, você pode integrá-lo rapidamente a qualquer idioma. Este é o tópico da sintaxe da linguagem. Dê um mergulho nos algoritmos de classificação.

Compreendendo a implementação de listas vinculadas em Python

Ordem de inserção

Um dos algoritmos de classificação mais fáceis é o tipo de inserção. A implementação é fácil. E você terá que classificar um array por mais tempo. Não é utilizado para classificar matrizes maiores na maioria das circunstâncias. A técnica do tipo de inserção mantém as subpartes classificadas na tabela fornecida. No início do processo de classificação, a subparte de classificação inclui apenas o primeiro elemento. Na submatriz classificada, escolhemos um elemento da matriz não classificada e o inserimos no local correto. A complexidade do tempo é O (n2) e a complexidade do espaço é 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))

O tipo de seleção é como a inserção com uma pequena alteração. Ele separa a matriz em componentes classificados e não classificados também. Em seguida, escolhemos o menor elemento de cada iteração da subseção não classificada e o inserimos na posição final da subseção classificada. A complexidade do tempo é O (n2) e a complexidade do espaço é 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))

Classificar bolhas é um algoritmo simples. Ele troca continuamente as entradas próximas em cada iteração até que a matriz em questão seja classificada. Ele passa pelo painel e empurra o elemento atual para o próximo lugar até que esteja mais baixo do que o próximo. A complexidade do tempo O (n2) e a complexidade do espaço é 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))

A classificação por mesclagem é um algoritmo de classificação de matriz recursiva. Em termos de complexidade de tempo, é mais eficiente do que os algoritmos apresentados anteriormente. Segue a abordagem de divisão e conquista. O algoritmo de classificação por mesclagem divide e classifica a matriz em duas partes individualmente. Ele une as duas metades em uma única matriz classificada depois de separá-la. Ele divide a matriz até que ela se torne a classificação mais fácil. Como este é um algoritmo recursivo. A complexidade do tempo é O (nlogn), e a complexidade do espaço é 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))