QuickSort
Es un algoritmo que sigue la estrategia de divide y vencerás.
Elija un elemento pivote de la matriz. Esto se puede hacer de varias maneras, como
seleccionando el primer elemento, el último elemento o un elemento aleatorio.
Partición: reorganice la matriz de modo que todos los elementos menores que el
pivote se coloquen antes y todos los elementos mayores que el pivote se coloquen
después. Después de este paso, el pivote se encuentra en su posición final ordenada.
Aplique recursivamente los pasos anteriores a las submatrices a la izquierda y a la
derecha del pivote hasta que se ordene toda la matriz.
//Define una función llamada `quick_sort` que toma una lista `arr` como argumento.
def quick_sort(arr):
//Verifica si la longitud de la lista `arr` es menor o igual a 1. Si es verdadero, devuelve la lista `arr` tal
como está, ya que una lista de longitud 0 o 1 ya está ordenada.
if len(arr) <= 1:
return arr
//En caso contrario (es decir, si la lista tiene más de un elemento), se ejecuta el siguiente bloque de
código.
else:
//Se elige el primer elemento de la lista como pivote. En este caso, el pivote se elige de forma ingenua
como el primer elemento de la lista.
pivot = arr[0]
//Se crea una lista llamada `less_than_pivot` que contiene todos los elementos de `arr` que son menores
o iguales que el pivote.
less_than_pivot = [x for x in arr[1:] if x <= pivot]
//Se crea una lista llamada `greater_than_pivot` que contiene todos los elementos de `arr` que son
mayores que el pivote.
greater_than_pivot = [x for x in arr[1:] if x > pivot]
//Se llama recursivamente a la función `quick_sort` con las sublistas `less_than_pivot` y
`greater_than_pivot`, y se concatenan junto con el pivote para formar la lista ordenada final.
return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)
# Ejemplo de uso
//Se define una lista `arr` que se utilizará como ejemplo de entrada para la función `quick_sort`.
arr = [29, 10, 14, 37, 13]
//Se llama a la función `quick_sort` con la lista `arr` y se guarda el resultado en la variable `sorted_arr`.
sorted_arr = quick_sort(arr)
//Se imprime la lista ordenada `sorted_arr`.
print(sorted_arr)
MergeSort
Sigue la estrategia de divide y vencerás.
Dividir: divide la matriz sin ordenar en dos mitades de forma recursiva hasta que cada
submatriz contenga solo un elemento.
Conquistar: fusionar los subarreglos divididos de forma ordenada. Esto se hace
comparando elementos de cada submatriz y fusionándolos en una nueva matriz
ordenada.
Combinar: repita el proceso de fusión hasta que todos los subarreglos se fusionen en
un solo arreglo ordenado.
La operación de combinación es la clave para MergeSort. Implica fusionar dos matrices
ordenadas en una única matriz ordenada. MergeSort garantiza una complejidad
temporal de O (n log n) en todos los casos, lo que lo hace más predecible que
QuickSort. Sin embargo, MergeSort requiere espacio adicional para la operación de
combinación, por lo que en algunos casos puede no ser tan eficiente en cuanto a
espacio como QuickSort.
// Define una función llamada `merge_sort` que toma una lista `arr` como argumento.
def merge_sort(arr):
// Verifica si la longitud de la lista `arr` es menor o igual a 1. Si es verdadero, devuelve la lista
`arr` tal como está, ya que una lista de longitud 0 o 1 se considera ordenada por definición.
if len(arr) <= 1:
return arr
# Divide la lista en dos mitades
// Calcula el índice medio de la lista `arr`, que se utilizará para dividir la lista en dos mitades.
middle = len(arr) // 2
// Crea una nueva lista `left_half` que contiene la primera mitad de la lista `arr`.
left_half = arr[:middle]
// Crea una nueva lista `right_half` que contiene la segunda mitad de la lista `arr`.
right_half = arr[middle:]
# Ordena recursivamente las dos mitades
// Llama recursivamente a `merge_sort` con la lista `left_half` para ordenarla.
left_half = merge_sort(left_half)
// Llama recursivamente a `merge_sort` con la lista `right_half` para ordenarla.
right_half = merge_sort(right_half)
# Combina las dos mitades ordenadas
// Combina las dos mitades ordenadas (`left_half` y `right_half`) llamando a la función `merge` y
devuelve la lista ordenada resultante.
return merge(left_half, right_half)
// Define una función llamada `merge` que toma dos listas ordenadas `left` y `right` como
argumentos.
def merge(left, right):
// Crea una lista vacía `result` que se utilizará para almacenar los elementos ordenados.
result = []
// Inicializa los índices `left_idx` y `right_idx` para recorrer las listas `left` y `right`,
respectivamente.
left_idx, right_idx = 0, 0
# Mezcla los elementos en orden
// Itera mientras los índices `left_idx` y `right_idx` sean menores que las longitudes de las listas
`left` y `right`, respectivamente.
while left_idx < len(left) and right_idx < len(right):
// Compara los elementos en las posiciones `left_idx` y `right_idx` de las listas `left` y `right`,
respectivamente.
if left[left_idx] < right[right_idx]:
// Si el elemento en `left[left_idx]` es menor, se agrega a `result` y se incrementa `left_idx`.
result.append(left[left_idx])
left_idx += 1
else:
// Si el elemento en `right[right_idx]` es menor, se agrega a `result` y se incrementa `right_idx`.
result.append(right[right_idx])
right_idx += 1
# Agrega los elementos restantes
// Agrega los elementos restantes de la lista `left` a `result`.
result.extend(left[left_idx:])
// Agrega los elementos restantes de la lista `right` a `result`.
result.extend(right[right_idx:])
// Devuelve la lista `result` que contiene los elementos ordenados de las listas `left` y `right`.
return result
# Ejemplo de uso
// Define una lista `arr` que se utilizará como ejemplo de entrada para la función `merge_sort`.
arr = [29, 10, 14, 37, 13]
// Llama a la función `merge_sort` con la lista `arr` y guarda el resultado en la variable
`sorted_arr`.
sorted_arr = merge_sort(arr)
// Imprime la lista ordenada `sorted_arr`.
print(sorted_arr)
Heapsort
Es un algoritmo de ordenamiento eficiente que utiliza una estructura de datos llamada
heap. Aquí está el paso a paso de cómo funciona:
Construcción del heap máximo: Se construye un heap máximo a partir del arreglo de
entrada. Un heap máximo es un árbol binario completo donde el valor de cada nodo es
mayor o igual que los valores de sus hijos.
Extracción del máximo: Se extrae el elemento máximo del heap (que está en la raíz).
Luego, se reemplaza con el último elemento del heap y se restablece la propiedad del
heap llamando a una función heapify en la raíz.
Repetición: Se repite el paso 2 hasta que todos los elementos hayan sido extraídos del
heap. Los elementos extraídos se colocan al final del arreglo, lo que resulta en un
arreglo ordenado.
// Define una función llamada `heapify` que toma una lista `arr`, un tamaño `n` y un índice `i`
como argumentos.
def heapify(arr, n, i):
// Inicializa `largest` como el índice `i`, que representa el índice del nodo actual en el heap.
largest = i
// Calcula el índice del hijo izquierdo del nodo actual.
left = 2 * i + 1
// Calcula el índice del hijo derecho del nodo actual.
right = 2 * i + 2
// Comprueba si el índice del hijo izquierdo está dentro de los límites del heap y si el valor en el
hijo izquierdo es mayor que el valor en el nodo actual. Si es así, actualiza `largest` al índice del
hijo izquierdo.
if left < n and arr[left] > arr[largest]:
largest = left
// Comprueba lo mismo para el hijo derecho y actualiza `largest` si es necesario.
if right < n and arr[right] > arr[largest]:
largest = right
// Si `largest` no es igual a `i`, intercambia los valores en los índices `i` y `largest` en el arreglo
`arr` y llama recursivamente a `heapify` en el subárbol con raíz en `largest`.
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
// Define una función llamada `heap_sort` que toma una lista `arr` como argumento .
def heap_sort(arr):
// Obtiene la longitud de la lista `arr`.
n = len(arr)
# Construir un heap máximo.
// Construye un heap máximo a partir de la lista `arr` comenzando desde el último nodo que
tiene hijos hasta la raíz.
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extraer elementos uno por uno desde el heap.
// Extrae elementos del heap uno por uno. Intercambia el primer elemento (que es el máximo
en un heap máximo) con el último elemento y ajusta el heap utilizando `heapify`.
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Intercambiar
heapify(arr, i, 0)
# Ejemplo de uso
//Define una lista `arr` que se utilizará como ejemplo de entrada para el algoritmo Heapsort.
arr = [29, 10, 14, 37, 13]
// Llama a la función `heap_sort` con la lista `arr` para ordenarla utilizando Heapsort.
heap_sort(arr)
// Imprime un mensaje indicando que el arreglo está ordenado.
print("Arreglo ordenado:")
// Imprime la lista ordenada `arr`.
print(arr)
