0% encontró este documento útil (0 votos)
30 vistas19 páginasComplejidad y Funcionamiento de Merge Sort
estructura de datos
Cargado por
Amaris CaceresDerechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
0% encontró este documento útil (0 votos)
30 vistas19 páginasComplejidad y Funcionamiento de Merge Sort
estructura de datos
Cargado por
Amaris CaceresDerechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
ORDENAMIENTO
POR MERGE SORT
Grupo #3
INTRODUCCIÓN
La investigación se centra en el algoritmo de ordenamiento
Merge Sort, el cual es recursivo y se caracteriza por tener un
número mínimo de comparaciones entre los elementos de un
arreglo. Este algoritmo se basa en la técnica de dividir el vector a
ordenar en dos partes iguales, ordenar cada parte de manera
independiente y luego combinar ambas partes en un solo vector
ordenado, manteniendo el orden.
El proceso del Merge Sort se descompone en tres pasos
fundamentales: dividir, ordenar y combinar. Cada uno de estos
pasos tiene su propia definición, pero son interdependientes en la
construcción del algoritmo.
OBJETIVOS GENERALES
❖ Investigar sobre el ordenamiento Merge Sort como se utiliza,
cuáles son sus características sus ventajas y desventajas al
usar el Merge Sort en un algoritmo en java o en cualquier
otro programa para crear algoritmos.
❖ Comprender cuál es el funcionamiento de Merge Sort en un
algoritmo.
❖ Investigar para obtener los conocimientos de cómo utilizar el
Merge Sort y en qué momento utilizarlo en un algoritmo de
los diferentes programas de Programación.
MARCO CONCEPTUAL
El método Merge Sort es un algoritmo de ordenamiento que se basa en la técnica
de "Divide y vencerás". Su funcionamiento consiste en dividir una estructura en
mitades, ordenar cada una de ellas de manera recursiva y luego intercalar ambas
mitades de forma ordenada. Este proceso se repite hasta que se alcanza el caso
base, donde la lista está vacía o contiene un solo elemento, lo que se considera
ordenado por definición.
El algoritmo Merge Sort presenta una complejidad temporal de O(n log n), lo que
lo convierte en una opción eficiente para el ordenamiento de listas grandes. Es
particularmente ventajoso en situaciones donde el uso de memoria adicional no
es un inconveniente y cuando la lista a ordenar puede estar parcialmente
ordenada. En contraste, se recomienda el uso de Quicksort en casos donde la
memoria adicional es un problema y la lista es aleatoria.
MARCO CONCEPTUAL
Merge Sort es un algoritmo estable, lo que significa que preserva el orden de los
elementos con valores iguales tras la ordenación. Este algoritmo es comúnmente
utilizado en ordenamientos externos, permitiendo manejar grandes volúmenes de
datos que no pueden ser almacenados en la memoria principal. Su
funcionamiento se basa en la técnica de "divide y vencerás", que implica dividir la
lista en sublistas más pequeñas, ordenarlas recursivamente y luego combinarlas
en un solo vector ordenado.
A pesar de su eficiencia, la implementación recursiva de Merge Sort requiere un
espacio adicional de memoria, utilizando el doble del espacio que ocupa el
arreglo original. Esta característica puede ser una desventaja en contextos donde
la memoria es un recurso limitado.
METODO DE ORDENACIÓN
❑ El Merge Sort, o ordenamiento por mezcla, es un algoritmo de ordenamiento
con una complejidad computacional de O(n log n), lo que lo hace eficiente
para ordenar listas de elementos. Este algoritmo se caracteriza por ser estable,
lo que significa que los elementos iguales mantienen su orden original
después de la ordenación. La estabilidad es una propiedad importante en los
algoritmos de ordenamiento, ya que no todos los algoritmos la garantizan.
❑ Este método implica dividir el listado en sub-listados más pequeños, que
luego se ordenan y se combinan. Para mezclar dos listados ordenados, se
utilizan punteros que comparan los elementos de cada lista, seleccionando el
menor o mayor según el criterio de ordenamiento. Este proceso se repite hasta
que ambos listados se han concatenado completamente.
METODO DE ORDENACIÓN
❑ La complejidad del proceso de mezcla es lineal, O(n + m), donde n y m son los
tamaños de los listados a mezclar. A medida que se divide el listado original,
se forma un árbol de decisiones cuya altura es logarítmica, lo que contribuye a
la complejidad total de O(n log n). Este enfoque es fundamental en
aplicaciones donde la eficiencia es crítica, como en bases de datos.
❑ El algoritmo se implementa de manera recursiva, dividiendo el array en
mitades, ordenando cada mitad y luego intercalando las mitades ordenadas. Si
el array tiene dos elementos, se comparan e intercambian directamente. Este
método es similar al Quicksort, pero se distingue por su enfoque en la
estabilidad y la estructura de mezcla. En resumen, el Merge Sort es un
algoritmo robusto y eficiente para la ordenación de datos, con aplicaciones
significativas en diversas áreas de la informática.
HISTORIA
❑ Donald Knuth menciona a John Von Neumann como el creador del algoritmo
de ordenación por mezcla, desarrollado en 1945. Este algoritmo utiliza la
técnica de divide y vencerás, dividiendo una secuencia de datos en dos
subsecuencias que se ordenan recursivamente antes de fusionarlas en una
secuencia ordenada. El proceso continúa hasta que se obtiene una única
secuencia ordenada.
❑ Merge Sort se caracteriza por ser un algoritmo de ordenamiento estable, lo
que significa que mantiene el orden de los elementos iguales. Además, es
eficiente en el manejo de medios secuenciales de acceso lento y se considera
la mejor opción para ordenar listas enlazadas, ya que puede implementarse
con un espacio extra de O(1). En contraste, otros algoritmos como quicksort y
heapsort pueden tener un rendimiento deficiente en este contexto.
TIPOS DE MÉTODOS
El algoritmo de merge sort utiliza principalmente dos métodos basados en la
técnica divide y vencerás:
Método recursivo: Divide un conjunto de datos en partes más pequeñas hasta
que los subproblemas sean lo suficientemente simples como para ser resueltos
directamente. Luego, se combinan las soluciones parciales para formar una lista
completamente ordenada.
Ejemplo de flujo recursivo:
Tienes un array [38, 27, 43, 3, 9, 82, 10].
El algoritmo primero divide este array en dos mitades: [38, 27, 43] y [3, 9, 82,
10].
TIPOS DE MÉTODOS
Luego sigue dividiendo: [38, 27, 43] se divide en [38] y [27, 43], y así
sucesivamente.
Finalmente, comienza el proceso de fusión: [38] y [27, 43] se fusionan
comparando los elementos en orden.
Este enfoque recursivo garantiza una complejidad temporal de O(n log n), que
es eficiente para grandes conjuntos de datos.
TIPOS DE MÉTODOS
Método iterativo (sin recursión): Aunque menos común, también puede
implementarse de forma iterativa dividiendo y fusionando los subconjuntos de
datos en ciclos en lugar de hacerlo recursivamente.
Cómo funciona el método iterativo en Merge Sort:
División en bloques: En lugar de dividir recursivamente el array, en la versión
iterativa se comienzan a ordenar porciones muy pequeñas (de tamaño 1, es
decir, cada elemento individual). Luego, se incrementa el tamaño de los
subarrays que se van fusionando gradualmente.
TIPOS DE MÉTODOS
Fusión de bloques: En cada paso, se van fusionando los bloques ordenados en
pares, comparando elementos y reorganizándolos en una nueva lista. La fusión
se realiza de la misma manera que en el método recursivo, pero esta vez se
controla a través de ciclos en lugar de llamadas recursivas.
Ventajas del método iterativo:
Eficiencia de espacio: Evita el uso de la pila de llamadas, lo que puede ser
beneficioso en escenarios con limitaciones de memoria.
UTILIDAD
El Merge Sort, o ordenamiento por mezcla, es un algoritmo de ordenamiento
que presenta una complejidad computacional de O (n log n), lo que lo hace muy
eficiente para ordenar listas de elementos. Este método es estable y se destaca
por su capacidad de paralelización, así como por su eficacia en el manejo de
medios de acceso secuencial que son lentos. Es especialmente ventajoso para
ordenar listas enlazadas, ya que puede implementarse con un espacio adicional
de O(1), lo que contrarresta el bajo rendimiento de otros algoritmos en este tipo
de estructuras.
La relevancia del Merge Sort se extiende a diversas aplicaciones, especialmente
en el ámbito de Bases de Datos, donde la eficiencia en el ordenamiento es
crucial. Además, su estudio permite introducir conceptos fundamentales sobre
el tiempo de ejecución y la eficiencia en la resolución de problemas.
DESARROLLO
DESARROLLO
DESARROLLO
PRUEBA DE ESCRITORIO
CONCLUSIONES
❖ Merge Sort se caracteriza por su gran eficiencia al dividir los datos en grupos
pequeños, lo que acelera su ordenación y lo hace ideal para manejar grandes
volúmenes de información.
❖ La operación Merge es clave, ya que permite combinar de manera coherente
datos que han sido modificados en paralelo, lo que es esencial cuando se
realizan múltiples cambios simultáneamente.
❖ Al ser un algoritmo recursivo, Merge Sort minimiza las comparaciones
necesarias y ofrece un rendimiento predecible, lo que lo convierte en una
opción confiable frente a otros métodos como Quicksort.
BIBLIOGRAFÍA
[Link]
es/[Link]/0.10%20Merge%20Sort%20&%20Quick%20Sort%20&%20Matriz%20
[Link]
[Link]
sort
[Link]
270
[Link]
merge-
sort#:~:text=Merge%20Sort%20divide%20el%20conjunto,manejan%20grandes
%20conjuntos%20de%20datos.