Cómo implementar la ordenación por combinación en C ++ con ejemplos

¿Qué es el tipo de combinación? La ordenación por combinación es un algoritmo de ordenación basado en la comparación que pertenece a la categoría divide y vencerás. La ordenación por fusión se usa para ordenar una matriz basada en la estrategia de dividir y conquistar que se cubrirá brevemente en esta publicación junto con otros conceptos, como su algoritmo, con un ejemplo. También veremos la complejidad de tiempo del tipo de combinación en C ++

En este artículo se cubrirán los siguientes consejos,

• Algoritmo de dividir y conquistar
• Comprender el algoritmo de ordenación de fusión con un ejemplo
• Pseudocódigo para clasificación por fusión
• Programa en C ++ para Merge Sort
• La complejidad del tiempo para Merge Sort

Continuando con este artículo sobre Merge Sort en C ++

fusionar ordenación en c ++

Algoritmo Divide and Conquer

Si ya está familiarizado con el funcionamiento de la ordenación rápida, es posible que conozca la estrategia de dividir y conquistar. Dividir y conquistar implica tres pasos principales. Para comprender estos pasos, consideremos una matriz Hola [] que tiene un índice inicial 'a' y un índice final 'n', por lo que podemos escribir nuestra matriz de la siguiente manera Hola [a & hellip..n]

Dividir: el movimiento principal o el paso principal de dividir y conquistar es dividir el problema dado en subproblemas o subpartes. El problema aquí es que los subproblemas deberían ser similares al problema original y de menor tamaño. En nuestro caso, dividiremos nuestra matriz en 2 mitades [a & hellip.m] [m + 1 & hellip..n] m se encuentra en el medio de los índices ayn

Conquistar: una vez que hayamos terminado de dividir nuestro problema en subproblemas. Resolvemos estos subproblemas de forma recursiva.

Combinar: en este paso, combinamos todas las soluciones de nuestros subproblemas de una manera adecuada. En otras palabras, combinamos 2 matrices ordenadas diferentes para formar una matriz ordenada. Allí tenemos nuestra matriz ordenada.

Continuando con este artículo sobre Merge Sort en C ++

Comprender el algoritmo de clasificación por fusión con un ejemplo

En este punto, sabemos qué enfoque utilizará el tipo de combinación. Por lo tanto, consideremos un ejemplo y repasemos cada paso desde Hello [] sin clasificar hasta una matriz ordenada.
Ejemplo: Hola [10, 3, 7, 1, 15, 14, 9, 22]

cómo configurar classpath en Windows

En la imagen de arriba, consideramos una matriz sin clasificar y usamos la ordenación combinada para obtener una matriz ordenada. Ahora, veamos cada paso y comprendamos todo el algoritmo

1. Primero, consideramos una matriz Hola [10, 3, 7, 1, 15, 14, 9, 22] en esta matriz hay un total de 8 elementos

2. Como vimos anteriormente, la ordenación por combinación utiliza el enfoque de dividir y conquistar para ordenar los elementos. Encontramos m que se encuentra en el medio de nuestra matriz y dividimos nuestra matriz desde el medio donde m = (a - n) / 2 'a' es el índice del elemento más a la izquierda yn es el índice del elemento más a la derecha de nuestra matriz .

3. Después de la primera división, tenemos 2 partes que constan de 4 elementos cada una. Veamos la primera mitad [10, 3, 7, 1].

4. Dividimos [10, 3, 7, 1] en 2 partes [10, 3] y [7, 1]. Después de eso, los dividimos en [10], [3], [7], [1]. No es posible realizar más divisiones porque no podemos calcular m. una lista que contiene un solo elemento siempre se considera ordenada.

5. ¿Cómo se produce la fusión? Vamos a averiguar. Primero se comparan [10] y [3] y se fusionan en orden ascendente [3, 10] de la misma manera que obtenemos [1, 7]

6. Después de eso, comparamos [3, 10] y [1, 7]. Una vez comparados, los fusionamos en orden ascendente y obtenemos [1, 3, 7, 10].

7. [15, 14, 9, 2] también se divide y combina de forma similar para formar [9, 14, 15, 22].

8. En el último paso, comparamos y combinamos [15, 14, 9, 2] [9, 14, 15, 22] para obtener nuestra matriz ordenada.es decir, [1, 3, 7, 9, 10, 14, 15, 22].

Continuando con este artículo sobre Merge Sort en C ++

Pseudocódigo para clasificación por fusión

Empiece si se deja
La función mergeSort () se llama a sí misma recursivamente para dividir nuestra matriz hasta que se convierte en un solo elemento y la función merge () se usa para fusionar las matrices ordenadas.
  Continuando con este artículo sobre Merge Sort en C ++
 Combinar el programa de ordenación en C ++ 
#include #include #include usando el espacio de nombres std void merge (int a [], int Firstindex, int m, int Lastindex) // fusiona las submatrices que se crean mientras la división void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindextamaño int Hola [tamaño], no puedo<<'Enter the elements of the array one by one:n' for(i=0 i>Hola [i] mergeSort (Hola, 0, tamaño - 1) cout<<'The Sorted List isn' for(i=0 i
 Salida- 
Continuando con este artículo sobre Merge Sort en C ++
¿Dónde deben declararse las variables de instancia en Java?
 Complejidad del tiempo 
La complejidad del tiempo es un aspecto importante a considerar cuando hablamos de algoritmos. Se considera que la ordenación por combinación tiene una gran complejidad de tiempo en comparación con otros algoritmos de ordenación.
Tiempo de ejecución en el peor de los casos: O (n log n) 
Mejor tiempo de ejecución del caso: O (n log n) 
Tiempo promedio de ejecución - O (n log n)
Con esto, llegamos al final de este artículo Merge Sort in C ++. Si desea obtener más información, consulte el   por Edureka, una empresa de aprendizaje en línea de confianza. El curso de certificación y capacitación Java J2EE y SOA de Edureka está diseñado para capacitarlo en conceptos básicos y avanzados de Java junto con varios marcos de Java como Hibernate y Spring.
 Tienes una pregunta para nosotros? Menciónelo en la sección de comentarios de este blog y nos pondremos en contacto con usted lo antes posible.