merge sort java program implement mergesort
Este tutorial explica qué es Merge Sort en Java, algoritmo MergeSort, pseudocódigo, implementación de Merge Sort, ejemplos de MergeSort iterativo y recursivo:
La técnica de clasificación por fusión utiliza una estrategia de 'divide y vencerás'. En esta técnica, el conjunto de datos que se va a clasificar se divide en unidades más pequeñas para clasificarlo.
=> Lea la serie de formación Easy Java.
Lo que vas a aprender:
- Combinar Ordenar en Java
- Conclusión
Combinar Ordenar en Java
Por ejemplo, si una matriz se va a ordenar usando mergesort, entonces la matriz se divide alrededor de su elemento central en dos submatrices. Estas dos submatrices se dividen aún más en unidades más pequeñas hasta que tengamos solo 1 elemento por unidad.
Una vez que se realiza la división, esta técnica fusiona estas unidades individuales comparando cada elemento y clasificándolos al fusionarlos. De esta forma, cuando se vuelva a fusionar toda la matriz, obtenemos una matriz ordenada.
En este tutorial, discutiremos todos los detalles de esta técnica de clasificación en general, incluido su algoritmo y pseudo códigos, así como la implementación de la técnica en Java.
Algoritmo MergeSort en Java
A continuación se muestra el algoritmo de la técnica.
#1) Declare una matriz myArray de longitud N
#2) Compruebe si N = 1, myArray ya está ordenado
#3) Si N es mayor que 1,
- establecer izquierda = 0, derecha = N-1
- calcular el medio = (izquierda + derecha) / 2
- Llame a la subrutina merge_sort (myArray, left, middle) => esto ordena la primera mitad de la matriz
- Llame a la subrutina merge_sort (myArray, middle + 1, right) => esto ordenará la segunda mitad de la matriz
- Llame a la combinación de subrutinas (myArray, left, middle, right) para combinar las matrices ordenadas en los pasos anteriores.
#4) Salida
Como se ve en los pasos del algoritmo, la matriz se divide en dos en el medio. Luego ordenamos de forma recursiva la mitad izquierda de la matriz y luego la mitad derecha. Una vez que clasificamos individualmente ambas mitades, se fusionan para obtener una matriz ordenada.
Fusionar ordenar pseudocódigo
Veamos el pseudocódigo de la técnica Mergesort. Como ya se ha comentado, dado que se trata de una técnica de 'divide y vencerás', presentaremos las rutinas para dividir el conjunto de datos y luego fusionar los conjuntos de datos ordenados.
|_+_|En el pseudocódigo anterior, tenemos dos rutinas, es decir, Mergesort y merge. La rutina Mergesort divide la matriz de entrada en una matriz individual que es bastante fácil de ordenar. Luego llama a la rutina de combinación.
La rutina de combinación fusiona las submatrices individuales y devuelve una matriz ordenada resultante. Habiendo visto el algoritmo y el pseudocódigo para la ordenación por fusión, ilustremos ahora esta técnica con un ejemplo.
Ilustración MergeSort
Considere la siguiente matriz que se ordenará mediante esta técnica.
Ahora, de acuerdo con el algoritmo de clasificación Merge, dividiremos esta matriz en su elemento medio en dos submatrices. Luego continuaremos dividiendo las sub-matrices en matrices más pequeñas hasta que obtengamos un solo elemento en cada matriz.
Una vez que cada submatriz tiene solo un elemento, fusionamos los elementos. Mientras fusionamos, comparamos los elementos y nos aseguramos de que estén en orden en la matriz fusionada. Así que trabajamos nuestro camino hacia arriba para obtener una matriz fusionada que está ordenada.
El proceso se muestra a continuación:
Como se muestra en la ilustración anterior, vemos que la matriz se divide repetidamente y luego se fusiona para obtener una matriz ordenada. Con este concepto en mente, pasemos a la implementación de Mergesort en el lenguaje de programación Java.
Implementación de Merge Sort en Java
Podemos implementar la técnica en Java usando dos enfoques.
Orden de fusión iterativo
Este es un enfoque de abajo hacia arriba. Cada una de las submatrices de un elemento se ordena y combina para formar matrices de dos elementos. Luego, estas matrices se fusionan para formar matrices de cuatro elementos y así sucesivamente. De esta forma, la matriz ordenada se construye yendo hacia arriba.
El siguiente ejemplo de Java muestra la técnica iterativa Merge Sort.
|_+_|Producción:
Matriz original: (10, 23, -11, 54, 2, 9, -10, 45)
Matriz ordenada: (-11, -10, 2, 9, 10, 23, 45, 54)
Orden de combinación recursiva
Este es un enfoque de arriba hacia abajo. En este enfoque, la matriz que se va a clasificar se divide en matrices más pequeñas hasta que cada matriz contenga solo un elemento. Entonces, la clasificación se vuelve fácil de implementar.
El siguiente código Java implementa el enfoque recursivo de la técnica de clasificación Merge.
|_+_|Producción:
Matriz original: (10, 23, -11, 54, 2, 9, -10, 45)
Matriz ordenada: (- 11, -10, 2, 9, 10, 23, 45, 54)
En la siguiente sección, cambiemos de matrices y usemos la técnica para ordenar la lista enlazada y las estructuras de datos de la lista de matrices.
Ordenar lista enlazada usando la ordenación combinada en Java
La técnica Mergesort es la más preferida para ordenar listas enlazadas. Otras técnicas de clasificación funcionan mal cuando se trata de la lista vinculada debido a su acceso mayoritariamente secuencial.
El siguiente programa ordena una lista enlazada utilizando esta técnica.
|_+_|Producción:
Lista vinculada original:
8 -> 3 -> 7 -> 2 -> 6 -> 1 -> 4 -> nulo
Lista vinculada ordenada:
1 -> 2 -> 3 -> 4 -> 6 -> 7 -> 8 -> nulo
copiar dvd a disco duro gratis
Ordenar ArrayList usando Merge Sort en Java
Al igual que las matrices y las listas vinculadas, también podemos utilizar esta técnica para ordenar una lista de matrices. Usaremos rutinas similares para dividir ArrayList de forma recursiva y luego fusionar las sublistas.
El siguiente código Java implementa la técnica de clasificación Merge para ArrayList.
|_+_|Producción:
ArrayList original:
17 40 36 7 6 23 35 2 38
ArrayList ordenado:
2 6 7 17 23 35 36 38 40
Preguntas frecuentes
P # 1) ¿Se puede realizar la ordenación por combinación sin recurrencia?
Responder: Si. Podemos realizar una clasificación de fusión no recursiva llamada 'clasificación de fusión iterativa'. Este es un enfoque de abajo hacia arriba que comienza fusionando submatrices con un solo elemento en una submatriz de dos elementos.
Luego, estas submatrices de 2 elementos se fusionan en submatrices de 4 elementos y así sucesivamente utilizando construcciones iterativas. Este proceso continúa hasta que tengamos una matriz ordenada.
Q #2) ¿Se puede realizar la ordenación por combinación en el lugar?
Responder: Por lo general, la ordenación por combinación no está en su lugar. Pero podemos hacerlo en su lugar utilizando alguna implementación inteligente. Por ejemplo, almacenando el valor de dos elementos en una posición. Esto se puede extraer posteriormente mediante módulo y división.
Q #3) ¿Qué es un ordenamiento combinado de 3 vías?
Responder: La técnica que hemos visto anteriormente es una clasificación de combinación de 2 vías en la que dividimos la matriz para clasificarla en dos partes. Luego ordenamos y fusionamos la matriz.
En una clasificación de combinación de 3 vías, en lugar de dividir la matriz en 2 partes, la dividimos en 3 partes, luego la ordenamos y finalmente la fusionamos.
Q #4) ¿Cuál es la complejidad temporal de Mergesort?
Responder: La complejidad de tiempo general de la ordenación por fusión en todos los casos es O (nlogn).
Q #5) ¿Dónde se utiliza el ordenamiento Merge?
Responder: Se utiliza principalmente para ordenar la lista enlazada en tiempo O (nlogn). También se utiliza en escenarios distribuidos en los que los datos nuevos llegan al sistema antes o después de la clasificación. Esto también se utiliza en varios escenarios de bases de datos.
Conclusión
La clasificación por fusión es una clasificación estable y se realiza primero dividiendo el conjunto de datos repetidamente en subconjuntos y luego clasificando y fusionando estos subconjuntos para formar un conjunto de datos ordenados. El conjunto de datos se divide hasta que cada conjunto de datos sea trivial y fácil de ordenar.
Hemos visto los enfoques repetitivos e iterativos de la técnica de clasificación. También hemos discutido la ordenación de la estructura de datos Linked List y ArrayList usando Mergesort.
Continuaremos con la discusión de más técnicas de clasificación en nuestros próximos tutoriales. ¡Manténganse al tanto!
=> Visite aquí para ver la serie exclusiva de tutoriales de formación en Java.
Lectura recomendada
- Combinar ordenación en C ++ con ejemplos
- Cómo ordenar una matriz en Java - Tutorial con ejemplos
- Clasificación de burbujas en Java: algoritmos de clasificación de Java y ejemplos de código
- Clasificación de selección en Java: algoritmo de clasificación de selección y ejemplos
- Ordenación por inserción en Java: algoritmo y ejemplos de ordenación por inserción
- QuickSort en Java - Algoritmo, ilustración e implementación
- Matrices en Java 8 - Clase de flujo y método ParallelSort
- Introducción a las técnicas de ordenación en C ++