Tutorial del algoritmo de ordenación y combinación de Python
Aprenda a implementar Merge Sort en Python. Un ejemplo interactivo paso a paso de la estrategia de clasificación Divide y vencerás.
Descripción general
Merge Sort es un algoritmo de clasificación altamente eficiente que utiliza una estrategia de divide y vencerás. Divide una lista sin ordenar en sublistas más pequeñas, las ordena y luego las vuelve a fusionar.
El algoritmo divide recursivamente la matriz por la mitad hasta llegar a submatrices de un solo elemento. Luego, fusiona las submatrices ordenadas comparando elementos de cada lado y colocándolos en orden. Esto garantiza una complejidad temporal óptima.
Independientemente de si la matriz inicial está ordenada, invertida o completamente aleatoria, Merge Sort se ejecuta en un tiempo O (n log n). Sin embargo, requiere O(n) espacio adicional para contener las sublistas durante la fase de fusión.
Código y salida de ejecución
Una implementación recursiva estándar del algoritmo Merge Sort en Python.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# Test dataset
data = [38, 27, 43, 3, 9, 82, 10]
print("Original List:", data)
sorted_data = merge_sort(data)
print("Sorted List: ", sorted_data)Original List: [38, 27, 43, 3, 9, 82, 10]
Sorted List: [3, 9, 10, 27, 38, 43, 82]Implementación paso a paso
- Ordenar listas vinculadas donde la estructura de nodos facilita la combinación sin copiar
- Rutinas de clasificación externa para archivos que no caben completamente en la RAM del sistema
- Aplicaciones de clasificación estables donde las claves coincidentes deben conservar su orden original
Preguntas frecuentes
¿Es Merge Sort un algoritmo de clasificación estable?
Sí, Merge Sort es estable. Al comparar elementos idénticos, el elemento del subarreglo izquierdo (primero el original) se coloca primero, conservando sus posiciones relativas originales.
¿Por qué Python usa Timsort en lugar de Merge Sort puro?
El `sorted()` integrado de Python utiliza Timsort, que es un algoritmo híbrido que combina Merge Sort y Insertion Sort. Optimiza los patrones de datos del mundo real identificando subsegmentos ya ordenados, lo que los hace más rápidos que Merge Sort puro.
Temas relacionados
Explore el algoritmo de clasificación rápida en Python. Aprenda la selección dinámica, la partición y la recursividad en este ejemplo de codificación interactivo.
Algoritmos de clasificación de PythonExplore los algoritmos de clasificación de Python. Visualice la clasificación por burbujas y la clasificación por combinación de forma nativa dentro del contexto IDE de un navegador.
Algoritmo de búsqueda binaria de PythonBusque listas ordenadas en tiempo logarítmico O (log n). Ejecute y comprenda la búsqueda binaria en Python, incluida la lógica paso a paso, los casos extremos y las optimizaciones.