Scribd
Cargar
5 vistas5 páginas

Merge Sort

Mergesort es un algoritmo de ordenación que utiliza el enfoque de divide y vencerás, dividiendo un vector en partes izquierda y derecha, ordenándolas recursivamente y luego combinándolas. El proceso se repite hasta que cada parte tiene un solo elemento o está vacía, lo que indica que está ordenada. El coste del algoritmo es O(n log n), donde n es el número de elementos en el vector.

Cargado por

cryssstalblues
Derechos 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
5 vistas5 páginas

Merge Sort

Mergesort es un algoritmo de ordenación que utiliza el enfoque de divide y vencerás, dividiendo un vector en partes izquierda y derecha, ordenándolas recursivamente y luego combinándolas. El proceso se repite hasta que cada parte tiene un solo elemento o está vacía, lo que indica que está ordenada. El coste del algoritmo es O(n log n), donde n es el número de elementos en el vector.

Cargado por

cryssstalblues
Derechos 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

Ejemplo mergesort

Mergesort es un método algorítmico de ordenación mediante DV.


La solución es recursiva, se trata de ordenar la parte de la izquierda y la parte de la derecha. Una
vez están ordenadas, se mezclan las dos partes. Al ordenar cada parte, se aplica la misma idea.
El algoritmo termina cuando la parte del vector considerada es vacío o tiene un elemento ya
que en estos casos, el vector está ordenado.

Pasos a para resolver:


• Se resuelve el problema para la parte izquierda utilizando el mismo algoritmo. El resultado es
que la parte izquierda del vector está ordenada.
• Se resuelve el problema para la parte derecha utilizando el mismo algoritmo. El resultado es
que la parte derecha del vector está ordenada.
• Se mezclan las dos partes ya ordenadas, lo que da como resultado el vector completamente
ordenado.
Ejemplo mergesort
0 1 2 3 4 5 6 0 1 2 3 4 5 6
9 3 10 6 9 7 5 9 3 10 6 9 7 5

Inicio Fin Inicio Medio Fin

0 1 2 3 4 5 6 0 1 2 3 4 5 6
9 3 10 6 9 7 5 9 3 10 6 9 7 5

Inicio Fin Inicio Medio Fin


0 1 2 3 4 5 6
9 3 10 6 9 7 5

Inicio Fin

Caso base, un único elemento


Ejemplo mergesort (mezcla)
0 1 2 3 4 5 6 0 1 2 3 4 5 6
3 9 10 5 6 7 9 3 9 10 5 6 7 9

i j Fin i j Fin
0 1 2 3 4 5 6 0 1 2 3 4 5 6
3

k k
0 1 2 3 4 5 6 0 1 2 3 4 5 6
3 9 10 5 6 7 9 3 9 10 5 6 7 9

i j Fin i j Fin
0 1 2 3 4 5 6 0 1 2 3 4 5 6
3 5 3 5 6

k k
Ejemplo mergesort (código)

El caso base no tiene código Cada caso recursivo realiza una


pero si existe (inicio + 1 >= fin) llamada con la mitad de los
datos de entrada
Ejemplo mergesort (coste)
0 =0 =1
Siendo n el número de
( )=
2 (2) + > 1 elementos del vector
La función que mezcla el
vector tiene coste lineal

Disminución del tamaño del problema por división:


T(n) = O(n k) (si a < b k)

T(n) = c * nk (si 1 ≤ n ≤ b) T(n) = O(n k * log(n)) (si a = b k)

( ) (b) ( )
n
( ) )
T n = a*T + c * n k si n ≥ b T n = O(n logb(a)) (si a > b k

(log( )) es un coste muy común en DV


𝑇
𝑛
𝑠
𝑖
𝑛
En esta caso: a = 2, b = 2 y k = 1 -> O(n^log(n))
𝑛
𝑇
𝑛
𝑐
𝑠
𝑖
𝑛
𝑜
𝑛
𝑂
𝑛

También podría gustarte