Publicado · en mejora
Algorithm
Los algoritmos de ordenamiento ponen los datos en orden: merge sort, quicksort, heapsort, estabilidad, la cota inferior n log n y el ordenamiento integrado.
Ordenar consiste en reorganizar elementos según un orden definido, como numérico, alfabético o cronológico. Hay dos grandes familias: los ordenamientos por comparación (burbuja, inserción, selección, merge sort, quicksort y heapsort), que solo preguntan si un elemento va antes que otro, y los que no comparan, como counting sort y radix sort, que usan directamente los valores enteros o sus dígitos.
El ordenamiento es el paso previo de la búsqueda binaria, la eliminación de duplicados, la fusión de intervalos, los rankings y muchas otras tareas, por eso es uno de los primeros algoritmos que se estudian. Conocer la cota inferior Ω(n log n) de los ordenamientos por comparación, la diferencia entre ordenamientos estables e in-place, y cómo funcionan los ordenamientos integrados, como Timsort en Python o el introsort de la mayoría de las implementaciones de std::sort en C++, ayuda a elegir bien en el trabajo y en las entrevistas.
Para estudiarlo conviene seguir a mano el ordenamiento por inserción, merge sort y quicksort sobre arreglos pequeños, luego implementar merge sort y quicksort y comparar sus casos mejor, promedio y peor. Después, practica ordenar con funciones clave y comparadores, y resuelve problemas basados en el ordenamiento, como fusionar intervalos o contar inversiones.
Merge sort divide la entrada a la mitad y fusiona las mitades; quicksort particiona alrededor de un pivote. Ambos funcionan en O(n log n) en promedio.
Un ordenamiento estable conserva el orden original de los elementos con claves iguales; uno in-place casi no usa memoria adicional. Cuál importa más depende de la tarea.
Un argumento con árboles de decisión muestra que todo ordenamiento por comparación necesita del orden de n log n comparaciones en el peor caso. Merge sort y heapsort alcanzan esa cota.
Counting sort y radix sort ordenan enteros con un rango o un número de dígitos limitado en tiempo casi lineal, sin comparar los elementos entre sí.
merge_sort divide la lista a la mitad, ordena cada mitad de forma recursiva y luego fusiona ambas tomando siempre el menor de los dos elementos del frente. En caso de empate toma primero el de la izquierda (<=), lo que lo hace estable, y funciona en O(n log n) para cualquier entrada. La última línea compara el resultado con la función integrada sorted().
merge_sort.py
def merge_sort(items):
"""Return a new sorted list (stable, O(n log n))."""
if len(items) <= 1:
return list(items)
mid = len(items) // 2
left, right = merge_sort(items[:mid]), merge_sort(items[mid:])
merged, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # take the left one on ties: stable
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
return merged + left[i:] + right[j:]
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(data)) # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort(data) == sorted(data)) # True
python merge_sort.pySeis capítulos que te llevan desde la instalación hasta las ideas clave de Ordenamiento.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Ordenamiento.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.