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.

Tipo de inserción

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 sub-part contains only the first element at the beginning of the sorting process. We will take an element from the unsorted array and place them in the correct position in the sorted sub-array.

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).
• Iterate over the given array from the second element.
  • Tome la posición actual y el elemento en dos variables.
  • Escribe un bucle que iteraates until the first element of the array or the element occurs that is less than the current element.
    • Actualizaciónate the current element with the prevelemento ioso.
    • 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))

Selección Ordenar

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).
• Iterate sobre la matriz dada.
  • Mantener el índice del elemento mínimo.
  • Escribe un bucle que iteraates from the current element to the last element.
    • 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 Ordenar

Bubble sort is a simple algorithm. It swaps the adjacent elements on each iteration repeatedly until the given array is sorted.

It iterates over the array and moves the current element to the next position until it is less than the next element.

Las ilustraciones nos ayudan a comprender bubble sort visualmenteally. Veámoslos.

Veamos los pasos para implementar el bubble sort.

1. Inicialice la matriz con datos ficticios (enteros).
2. Iterate sobre la matriz dada.
   1. Iterate del 0 a ni-1. El último i los elementos ya están ordenados.
      1. Check whether the current element is greater than the next element or not.
      2. If the current element is greater than the next element, then swap the two elements.

La complejidad temporal del bubble sort is O (n ^ 2), y la complejidad del espacio si O (1).

You can easily implement the bubble sort by now. Let’s see the 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))

Ordenar fusión

Merge sort es un algoritmo recursivo para ordenar la matriz dada. Es más eficiente que el p.revAlgoritmos muy discutidos en términos de complejidad temporal. Sigue el enfoque de divide y vencerás.

The merge sort algorithm divides the array into two halves and sorts them separately. After sorting the two halves of the array, it merges them into a single sorted array.

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.
  • Iterate over the two sub-arrays.
    • 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 fusionar_ordenar con matriz de parámetros, índices izquierdo y derecho.
  • If the left index is greater than or equal to the right index, then return.
  • Encuentre el punto medio de la matriz para dividir la matriz en dos mitades.
  • Llame recursivamente al fusionar_ordenar 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 🙂 👨‍💻