TecNoticias, tu portal de información

Explicación de 3 tipos de algoritmos de clasificación y su implementación en Python

Imagen de 200 grados de Pixabay En el artículo anterior, analicé la recursividad y construiremos sobre esta base con algoritmos de clasificación en este artículo. Los algoritmos de clasificación se utilizan para reorganizar elementos en una matriz de modo que cada elemento sea mayor o igual que su predecesor. Hay muchos tipos diferentes de algoritmos de ordenación y le mostraré los tres más comunes con los que vale la pena familiarizarse: ordenación por selección, ordenación por inserción, ordenación por fusión. Como ejemplo para demostrar cómo se aplica cada algoritmo de ordenación, imagine que está tratando de ordenar n libros en un estante por apellido del autor. En la ordenación por selección, comience por buscar en todo el estante para encontrar el libro cuyo apellido del autor aparece primero en el alfabeto y coloque ese libro al comienzo del estante en la posición 1 desde el izquierda. A continuación, comenzaríamos desde el libro en la posición 2 y nos moveríamos hacia la derecha para buscar el libro cuyo apellido del autor aparece primero en el alfabeto en el subarreglo restante, luego colocaríamos ese libro en la posición 2. Repita este proceso hasta la ranura n — 1 y habremos ordenado todo el estante de libros utilizando la ordenación por selección. Para implementar el algoritmo de ordenación por selección en Python, necesitamos realizar un seguimiento de dos subarreglos: el subarreglo ordenado (elementos en el arreglo original a la derecha del índice actual i) y el subarreglo restante sin ordenar (elementos en el arreglo original a la izquierda del índice actual i). Para cada elemento en el arreglo original, necesitamos iterar a través de los elementos en el subarreglo restante sin clasificar para encontrar el elemento más pequeño e intercambiarlo con el elemento en el índice actual i. La complejidad de tiempo del algoritmo de clasificación por selección es O(n²) , ya que hay dos bucles for en este algoritmo.def selection_sort(arr):
n = largo(arr)
para i en el rango (n):
# Encuentra el elemento más pequeño en los índices restantes de la matriz
min_idx = yo
para j en el rango (i + 1, n):
si arr[j] min_idx = j # Intercambiar el elemento mínimo más pequeño con el elemento en la posición i
Arr[i]arr[min_idx] = arr[min_idx]arr[i]return arrEn ordenación por inserción, los elementos en los primeros índices i son los mismos que los elementos que estaban originalmente en los primeros índices i. Similar a la ordenación por selección, recorremos cada elemento de la matriz original de izquierda a derecha. Sin embargo, esta vez compararemos el elemento en el índice actual i (clave) con cada elemento en el subarreglo ordenado a la derecha del índice actual hasta que encontremos un elemento que no sea más que el elemento actual y lo colocaremos aquí en este nueva posición. El límite superior de la complejidad temporal del algoritmo de ordenación por inserción es O(n²), que ocurre cuando los elementos de la matriz están en orden inverso, ya que el ciclo while interno tiene que iterar a través de cada elemento de la subarreferencia ordenada. El límite inferior de la complejidad temporal del algoritmo de ordenación por inserción es O(n) si todos los elementos ya están ordenados y el ciclo while interno no tiene que realizar ninguna iteración.def inserción_ordenación(arr):
n = largo(arr)
para i en el rango (1, n):
clave = arr[i]
j = i – 1 # Clave de comparación para cada elemento en el
# subarreglo ordenado hasta que la clave sea más pequeña
# que el elemento actual
mientras que j >= 0 y clave Arr[j + 1] = arr[j]
j -= 1 # Insertar llave en posición identificada
Arr[j + 1] = key return arr Merge sort es un algoritmo de divide y vencerás, mediante el cual descomponemos el problema en subproblemas, resolvemos los subproblemas recursivamente y luego combinamos las soluciones de los subproblemas para resolver el problema original. En nuestro ejemplo de clasificación de libros, así es como aplicaríamos divide y vencerás: Dividir: dividir la matriz en dos mitades; Conquistar: ordenar recursivamente los libros en cada una de las dos mitades resultantes del paso anterior. El caso base ocurre cuando solo queda un libro en el subarreglo; Combinar: fusionar las mitades ordenadas juntas. fragmentos, y clasificar cada fragmento lleva un tiempo lineal para fusionar las dos mitades.def merge_sort(arr):
# Terminando el caso base
si len(arr) regreso
más:
# Divide el arreglo en dos subarreglos
punto medio = len(arr) // 2
izquierda = arr[:midpoint]
derecha = arr[midpoint:] # Ordenar subarreglos
sorted_left = merge_sort(izquierda)
sorted_right = merge_sort(right) # Combinar subarreglos ordenados
sorted_arr = []
mientras que len(ordenado_izquierda) > 0 y len(ordenado_derecha) > 0:
# Compara los primeros elementos de los subarreglos
si ordenado_izquierda[0] sorted_arr.append(sorted_left[0])
sorted_left.pop(0)
más:
sorted_arr.append(sorted_right[0])
sorted_right.pop(0) # Insertar elementos restantes en subarreglos ordenados
sorted_arr.extend(sorted_left)
sorted_arr.extend(sorted_right) return sorted_arrSelection sort, sorted sort y merge sort son algoritmos de clasificación canónicos que se deben conocer. Los ejemplos de Python están destinados a ayudar a demostrar cómo funcionan estos algoritmos en la práctica. En la siguiente parte de esta serie Explicación de los algoritmos, explicaré los algoritmos de búsqueda.