La clasificación es una de las características más utilizadas en la programación. Y tomará tiempo completar la clasificación si no usamos el algoritmo correcto.
En este artículo, vamos a discutir 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. Esa es la cuestión de la sintaxis del lenguaje.
Veremos diferentes algoritmos de peor a mejor en este tutorial. Entonces, no te preocupes. Siga el artículo e impleméntelos.
Vamos a sumergirnos en los algoritmos de clasificación.
Tabla de contenido
Tipo de inserción
La clasificación por inserción es uno de los algoritmos de clasificación simples. Es fácil de implementar. Y le costará más tiempo ordenar una matriz. No se usará en la mayoría de los casos para ordenar arreglos más grandes.
El algoritmo de ordenación por inserción mantiene las subpartes ordenadas y no ordenadas en la matriz dada.
La subparte clasificada contiene solo el primer elemento al comienzo del proceso de clasificación. Tomaremos un elemento de la matriz sin ordenar y los colocaremos en la posición correcta en la sub-matriz ordenada.
Veamos las ilustraciones visuales del ordenamiento por inserción paso a paso con un ejemplo.
Veamos los pasos para implementar el ordenamiento por inserción.
- Inicialice la matriz con datos ficticios (enteros).
- Iterar sobre la matriz dada desde el segundo elemento.
- Toma la posición actual y el elemento en dos variables.
- Escriba un ciclo que itere hasta que ocurra el primer elemento de la matriz o el elemento que sea menor que el elemento actual.
- Actualiza el elemento actual con el elemento anterior.
- Decremento de la posición actual.
- Aquí, el ciclo debe llegar al inicio de la matriz o encontrar un elemento más pequeño que el elemento actual. Reemplace el elemento de posición actual con el elemento actual.
La complejidad temporal del ordenamiento por inserción es O(n^2), y la complejidad espacial si es O(1).
Eso es todo; hemos ordenado la matriz dada. Ejecutemos el siguiente código. Espero que haya instalado Python, si no, consulte la guía de instalación. Alternativamente, puede usar 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))
Clasificación de selección
La ordenación por selección es similar a la ordenación por 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 no ordenada y lo colocaremos en la última posición de la subparte ordenada.
Veamos ilustraciones de tipo selección para una mejor comprensión.
Veamos los pasos para implementar el ordenamiento por selección.
- Inicialice la matriz con datos ficticios (enteros).
- Iterar sobre la matriz dada.
- Mantener el índice del elemento mínimo.
- Escriba un bucle que itere 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 ordenamiento por selección es O(n^2), y la complejidad espacial si es O(1).
Intente implementar el algoritmo ya que es similar al ordenamiento por 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))
Ordenamiento de burbuja
Bubble sort 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 sea menor que el siguiente elemento.
Las ilustraciones nos ayudan a comprender visualmente el tipo de burbuja. Veámoslos.
Veamos los pasos para implementar el ordenamiento por burbujas.
La complejidad temporal del tipo de burbuja es O(n^2) y la complejidad espacial es O(1).
Ya puede implementar fácilmente la ordenación de burbuja. 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))
Ordenar por fusión
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 divide y vencerás.
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 la ilustración. Vamos a verlo.
Veamos los pasos para implementar el ordenamiento por fusión.
- Inicialice la matriz con datos ficticios (enteros).
- Escriba una función llamada fusionar 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 usando los índices dados.
- Copie los elementos de la matriz en las respectivas matrices izquierda y derecha.
- Iterar sobre los dos sub-arreglos.
- Compare los dos elementos de submatrices.
- Reemplace el elemento de la matriz con el elemento más pequeño de las dos sub-matrices para ordenar.
- Compruebe si quedan elementos en ambos subconjuntos.
- Agréguelos a la matriz.
- Escriba una función llamada merge_sort con una matriz de parámetros, índices izquierdo y derecho.
- Si el índice de la izquierda es mayor o igual que el índice de la derecha, entonces regrese.
- Encuentre el punto medio de la matriz para dividir la matriz en dos mitades.
- Llame recursivamente a merge_sort usando los índices izquierdo, derecho y medio.
- Después de las llamadas recursivas, combine la matriz con la función de combinación.
La complejidad temporal del ordenamiento por fusión es O(nlogn), y la complejidad espacial si es 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 usan con frecuencia. Espero que hayas disfrutado aprendiendo a clasificar.
A continuación, infórmese sobre los algoritmos de búsqueda.
Codificación feliz 🙂 👨💻