Ordenar implementaciones de algoritmos en Python

La clasificación es una de las funciones más utilizadas en programación. Y llevará tiempo completar la clasificación si no usamos el algoritmo correcto.

En este artículo, discutiremos diferentes algoritmos de clasificación.

Lo guiaremos a través de los diferentes algoritmos de clasificación con cada paso que viene en la implementación. La parte de implementación estará en Python. Puede convertirlo fácilmente a cualquier idioma una vez que obtenga el algoritmo. Ésa es la cuestión de la sintaxis del lenguaje.

Veremos diferentes algoritmos de peor a mejor en este tutorial. Así que no se preocupe. Siga el artículo e impleméntelos.

Profundicemos en los algoritmos de clasificación.

Insertion Sort

La ordenación por inserción es uno de los algoritmos de ordenación simples. Es fácil de implementar. Y le costará más tiempo ordenar una matriz. No se utilizará en la mayoría de los casos para clasificar matrices más grandes.

El tipo de inserción El algoritmo mantiene subpartes ordenadas y no ordenadas en la matriz dada.

El ordenados La subparte contiene solo el primer elemento al comienzo del proceso de clasificación. Tomaremos un elemento de la matriz no ordenada y los colocaremos en la posición correcta en la sub-matriz ordenada.

Veamos las ilustraciones visuales de tipo de inserción paso a paso con un ejemplo.

Veamos los pasos para implementar el tipo de inserción.

La complejidad temporal del tipo de inserción is O (n ^ 2), y la complejidad del espacio si O (1).

Eso es; hemos ordenado la matriz dada. Ejecutemos el siguiente código. Espero que haya instalado Python, si no, consulte el guía de instalación. Alternativamente, puede utilizar un compilador de Python en línea.

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))

Selection Sort

El orden de selección es similar al orden de inserción con una ligera diferencia. Este algoritmo también divide la matriz en subpartes ordenadas y no ordenadas. Y luego, en cada iteración, tomaremos el elemento mínimo de la subparte sin clasificar y colóquelo en la última posición del subparte ordenada.

Vamos a ilustraciones de tipo de selección para un mejor entendimiento.

Veamos los pasos para implementar el tipo de selección.

La complejidad temporal del tipo de selección is O (n ^ 2), y la complejidad del espacio si O (1).

Intente implementar el algoritmo ya que es similar al tipo de inserción. Puedes ver el código a continuación.

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

La clasificación de burbujas es un algoritmo simple. Intercambia los elementos adyacentes en cada iteración repetidamente hasta que se ordena la matriz dada.

Itera sobre la matriz y mueve el elemento actual a la siguiente posición hasta que es menor que el siguiente elemento.

Las ilustraciones nos ayudan a comprender ordenamiento de burbuja visualmente. Veámoslos.

Veamos los pasos para implementar el ordenamiento de burbuja.

  1. Inicialice la matriz con datos ficticios (enteros).
  2. Itere sobre la matriz dada.
    1. Iterar desde ni-1. El último i los elementos ya están ordenados.
      1. Compruebe si el elemento actual es mayor que el siguiente elemento o no.
      2. Si el elemento actual es mayor que el siguiente, intercambie los dos elementos.

La complejidad temporal del ordenamiento de burbuja is O (n ^ 2), y la complejidad del espacio si O (1).

Ahora puede implementar fácilmente la clasificación de burbujas. Veamos el código.

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))

Merge Sort

Merge sort es un algoritmo recursivo para ordenar la matriz dada. Es más eficiente que los algoritmos discutidos anteriormente en términos de complejidad de tiempo. Sigue el enfoque de divide y conquista.

El algoritmo de clasificación por fusión divide la matriz en dos mitades y las clasifica por separado. Después de ordenar las dos mitades de la matriz, las fusiona en una sola matriz ordenada.

Como es un algoritmo recursivo, divide la matriz hasta que la matriz se convierte en la más simple (matriz con un elemento) para ordenar.

Es hora de ilustrar. Vamos a verlo.

Veamos los pasos para implementar el tipo de fusión.

La complejidad temporal del tipo de fusión is O (nlogn), y la complejidad del espacio si O (1).

Eso es todo para la implementación del algoritmo de clasificación por fusión. Verifique el código a continuación.

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))

Conclusión

Hay muchos otros algoritmos de clasificación, pero los anteriores son algunos de los que se utilizan con frecuencia. Espero que hayas disfrutado aprendiendo a clasificar.

A continuación, descubra algoritmos de búsqueda.

Codificación feliz 🙂 👨‍💻