Scribd
Cargar
17 vistas6 páginas

Algoritmo de Ordenamiento por Mezcla

El algoritmo de ordenamiento por mezcla divide la lista en sublistas más pequeñas, ordena cada sublista de forma recursiva y luego las combina en una sola lista ordenada. Fue desarrollado por John Von Neumann en 1945 y tiene una complejidad de O(n log n). Divide la lista en partes iguales hasta que cada parte contenga un solo elemento y luego las vuelve a unir en orden mediante comparaciones y movimientos.

Cargado por

Luis Rodrigo Martinez Lopez
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
17 vistas6 páginas

Algoritmo de Ordenamiento por Mezcla

El algoritmo de ordenamiento por mezcla divide la lista en sublistas más pequeñas, ordena cada sublista de forma recursiva y luego las combina en una sola lista ordenada. Fue desarrollado por John Von Neumann en 1945 y tiene una complejidad de O(n log n). Divide la lista en partes iguales hasta que cada parte contenga un solo elemento y luego las vuelve a unir en orden mediante comparaciones y movimientos.

Cargado por

Luis Rodrigo Martinez Lopez
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

Estructura de Datos

Mtodo de Ordenamiento de Mezcla Merge Sort

El algoritmo de ordenamiento por mezcla (merge sort en ingls) es un algoritmo de ordenamiento externo estable basado en la tcnica divide y vencers. Es de complejidad O(n log n).
Fue desarrollado en 1945 por John Von Neumann

Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera: Si la longitud de la lista es 0 1, entonces ya est ordenada. En otro caso: Dividir la lista desordenada en dos sublistas de aproximadamente la mitad del tamao. Ordenar cada sublista recursivamente aplicando el ordenamiento por mezcla. Mezclar las dos sublistas en una sola lista ordenada.

El ordenamiento por mezcla incorpora dos ideas principales para mejorar su tiempo de ejecucin: Una lista pequea necesitar menos pasos para ordenarse que una lista grande. Se necesitan menos pasos para construir una lista ordenada a partir de dos listas tambin ordenadas, que a partir de dos listas desordenadas. Por ejemplo, slo ser necesario entrelazar cada lista una vez que estn ordenadas.

[Link]

También podría gustarte