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.

Inicialice la matriz con datos ficticios (enteros).
Itere sobre la matriz dada desde el segundo elemento.
- Tome la posición actual y el elemento en dos variables.
- Escriba un bucle que se repita hasta que aparezca el primer elemento de la matriz o el elemento que sea menor que el elemento actual.
  - Actualiza el elemento actual con el elemento anterior.
  - Disminución de la posición actual.
- Aquí, el bucle debe llegar al inicio de la matriz o encontrar un elemento más pequeño que el elemento actual. Reemplaza el elemento de posición actual con el elemento actual.

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.

Inicialice la matriz con datos ficticios (enteros).
Itere sobre la matriz dada.
- Mantener el índice del elemento mínimo.
- Escribe un bucle que repita desde el elemento actual hasta el último elemento.
  - Compruebe si el elemento actual es menor que el elemento mínimo o no.
  - Si el elemento actual es menor que el elemento mínimo, reemplace el índice.
- Tenemos el índice mínimo de elementos con nosotros. Intercambia el elemento actual con el elemento mínimo usando los índices.

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.

Inicialice la matriz con datos ficticios (enteros).
Itere sobre la matriz dada.
1. Iterar desde 0 a 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.

Inicialice la matriz con datos ficticios (enteros).
Escribe una función llamada unir para fusionar submatrices en una sola matriz ordenada. Acepta la matriz de argumentos, los índices izquierdo, medio y derecho.
- Obtenga las longitudes de las submatrices izquierda y derecha utilizando los índices dados.
- Copie los elementos de la matriz en las respectivas matrices izquierda y derecha.
- Repita las dos submatrices.
  - Compare los dos elementos de las submatrices.
  - Reemplace el elemento de la matriz con el elemento más pequeño de las dos submatrices para ordenar.
- Compruebe si quedan elementos en ambas submatrices.
- Agréguelos a la matriz.
Escribe una función llamada merge_sort con matriz de parámetros, índices izquierdo y derecho.
- Si el índice de la izquierda es mayor o igual que el índice de la derecha, regrese.
- Encuentre el punto medio de la matriz para dividir la matriz en dos mitades.
- Llame recursivamente al merge_sort utilizando los índices izquierdo, derecho y medio.
- Después de las llamadas recursivas, combine la matriz con el unir funció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))

Para concluir

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 🙂 👨‍💻