Mergesort

El algoritmo de ordenamiento por mezcla (merge sort en inglés) es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n).**Fue desarrollado en 1945 por John Von Neumann.

Con0ceptualmente, una especie de fusión funciona de la siguiente manera 

Si la lista tiene una longitud de 0 o 1, entonces ya está ordenado.

De lo contrario:

Divide la lista sin ordenar en dos sublistas de la mitad del tamaño.

Ordenar cada sublista recursivamente por volver a aplicar el tipo de fusión.

Combinar las dos sublistas de nuevo en una lista ordenada.

Combinar especie incorpora dos ideas principales para mejorar su tiempo de ejecución:

Una pequeña lista tendrá menos pasos para ordenar a una larga lista.

Menos pasos son necesarios para construir una lista ordenada a partir de dos listas ordenadas que a partir de dos listas sin ordenar. Por ejemplo, sólo tiene que recorrer cada lista una vez que si ya están clasificados (ver la combinación de funcionalidad por debajo de una implementación de ejemplo).

Ejemplo: Uso de combinación de clasificación para ordenar una lista de números enteros contenidos en una serie :

Supongamos que tenemos un conjunto A con n índices que van desde un 0 a un n – 1. Aplicamos fusión tipo A (A 0 .. A c – 1) y A (c .. A n – 1) donde c es la parte entera de n / 2. Cuando las dos mitades son devueltos ya que han sido ordenados. En la actualidad, se pueden combinar entre sí para formar una matriz ordenada.

Un ejemplo de tipo de mezcla. En primer lugar dividir la lista en la unidad más pequeña (un elemento), a continuación, comparar cada elemento de la lista junto a clasificar y combinar la lista de dos adyacentes. Finalmente, todos los elementos se ordenan y se fusionaron.

Conceptualmente, una especie de fusión funciona de la siguiente manera

  1. Si la lista tiene una longitud de 0 o 1, entonces ya está ordenado. De lo contrario:
  2. Divide la lista sin ordenar en dos sublistas de la mitad del tamaño.
  3. Ordenar cada sublista recursivamente por volver a aplicar el tipo de fusión.
  4. Combinar las dos sublistas de nuevo en una lista ordenada.

Combinar especie incorpora dos ideas principales para mejorar su tiempo de ejecución:

  1. Una pequeña lista tendrá menos pasos para ordenar a una larga lista.
  2. Menos pasos son necesarios para construir una lista ordenada a partir de dos listas ordenadas que a partir de dos listas sin ordenar. Por ejemplo, sólo tiene que recorrer cada lista una vez que si ya están clasificados (ver la combinación de funcionalidad por debajo de una implementación de ejemplo).

Ejemplo: Uso de combinación de clasificación para ordenar una lista de números enteros contenidos en una serie :

Supongamos que tenemos un conjunto A con n índices que van desde un 0 a un n – 1. Aplicamos fusión tipo A (A 0 .. A c – 1) y (c .. A n – 1) donde c es la parte entera de n / 2. Cuando las dos mitades son devueltos ya que han sido ordenados. En la actualidad, se pueden combinar entre sí para formar una matriz ordenada.

pseudocodigo🙂

MERGESORT(array Input; int left; int right)
1 if (left < right)
2   int mid = (right + left) / 2
3   MERGESORT(Input, left, mid)
4   MERGESORT(Input, mid+1, right)
5   Merge Input[left..mid] and Input[mid+1..right] into Auxiliary Table
6   Move Auxiliary Table to Input[left..right]

Ejemplo de Árbol de llamadas para la ordenación por fusiónCada nodo del árbol de llamadas se divide en dos:
– Lado izquierdo: Entrada parámetro de la matriz [izquierda, derecha]
– Lado derecho: Entrada array [izquierda, derecha] después de una llamada recursiva.Ejemplo: serie de clasificación de tamaño 4 con los artículos 6,9,7,1.
Primera llamada: la ordenación por fusión (de entrada, 0, 3).
Dos llamadas recursivas finales de árbol de llamadas binario.
  6971:1679
/   \
69:69          71:17
/    \               /     \
6:6  9:9              7:7  1:1

En el que los árboles a fin de llamadas son atravesadas durante la recursividad? Comparar mergesort con el correspondiente (recursiva) de árboles algoritmo de recorrido.

http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/RecursiveMergeSort-42.html

http://www.cse.hut.fi/en/research/SVG/TRAKLA2/exercises/IteratedMergeSort-41.html

http://en.wikipedia.org/wiki/Merge_sort

1 comentario (+¿añadir los tuyos?)

  1. Elisa Schaeffer
    Jul 07, 2011 @ 13:39:24

    Bien; 4.

    Responder

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: