La clasificación por combinación es similar al algoritmo de clasificación rápida, ya que funciona con el concepto de divide y vencerás. Es uno de los algoritmos de clasificación más populares y eficientes. Es el mejor ejemplo de la categoría de algoritmos divide y vencerás.
Divide la lista dada en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas. Definimos el unir() Función utilizada para fusionar dos mitades.
Las sublistas se dividen una y otra vez en mitades hasta obtener un único elemento cada una. Luego combinamos el par de listas de un elemento en listas de dos elementos, clasificándolas en el proceso. Los dos pares de elementos ordenados se fusionan en las listas de cuatro elementos, y así sucesivamente hasta obtener la lista ordenada.
Combinar concepto de ordenación
Veamos el siguiente diagrama de ordenación por fusión.
Hemos dividido la lista dada en dos mitades. La lista no se puede dividir en partes iguales, no importa en absoluto.
La ordenación por combinación se puede implementar de dos maneras: enfoque de arriba hacia abajo y enfoque de abajo hacia arriba. Usamos el enfoque de arriba hacia abajo en el ejemplo anterior, que es el tipo de combinación más utilizado.
El enfoque ascendente proporciona una mayor optimización que definiremos más adelante.
La parte principal del algoritmo es cómo combinamos las dos sublistas ordenadas. Fusionemos las dos listas de combinación ordenadas.
- A : [ 2 , 4, 7, 8]
- B : [ 1 , 3, 11]
- ordenado: vacío
Primero, observamos el primer elemento de ambas listas. Encontramos que el primer elemento de B es más pequeño, por lo que lo agregamos en nuestra lista ordenada y avanzamos en la lista B.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , 11]
- Ordenado: 1
Ahora miramos el siguiente par de elementos 2 y 3. 2 es más pequeño, así que lo agregamos a nuestra lista ordenada y avanzamos a la lista.
- A : [ 2 , 4, 7, 8]
- B: [1, 3 , 11]
- Ordenado: 1
Continúe este proceso y terminaremos con la lista ordenada de {1, 2, 3, 4, 7, 8, 11}. Puede haber dos casos especiales.
selección de tabla múltiple sql
¿Qué pasa si ambas sublistas tienen los mismos elementos? En tal caso, podemos mover cualquiera de las sublistas y agregar el elemento a la lista ordenada. Técnicamente, podemos avanzar en ambas sublistas y agregar los elementos a la lista ordenada.
No nos queda ningún elemento en una sublista. Cuando nos quedemos sin una sublista, simplemente agregue el elemento de la segunda, uno tras otro.
Debemos recordar que podemos ordenar el elemento en cualquier orden. Ordenamos la lista dada en orden ascendente, pero podemos ordenarla fácilmente en orden descendente.
Implementación
El algoritmo de clasificación por combinación se implementa mediante el enfoque de arriba hacia abajo. Puede parecer un poco difícil, por lo que elaboraremos los detalles de cada paso. Aquí, implementaremos este algoritmo en dos tipos de colecciones: lista de elementos enteros (normalmente utilizada para introducir la clasificación) y un objeto personalizado (un escenario más práctico y realista).
Ordenar matriz
El concepto principal del algoritmo es dividir (sub)listas en mitades y ordenarlas de forma recursiva. Continuamos el proceso hasta terminar con listas que tienen un solo elemento. Entendamos la siguiente función para la división:
def merge_sort(array, left_index, right_index): if left_index >= right_index: return middle = (left_index + right_index)//2 merge_sort(array, left_index, middle) merge_sort(array, middle + 1, right_index) merge(array, left_index, right_index, middle)
Nuestro objetivo principal es dividir la lista en subpartes antes de que se realice la clasificación. Necesitamos obtener el valor entero, por eso usamos el operador // para nuestros índices.
Entendamos el procedimiento anterior siguiendo los pasos.
- El primer paso es crear copias de listas. La primera lista contiene las listas de [índice_izquierdo,...,medio] y el segundo de [medio+1,?,índice_derecho] .
- Recorremos ambas copias de la lista usando el puntero, seleccionamos el valor más pequeño de los dos valores y los agregamos a la lista ordenada. Una vez que agregamos el elemento a la lista, avanzamos en la lista ordenada independientemente.
- Agregue los elementos restantes de la otra copia a la matriz ordenada.
Implementemos la ordenación por combinación en el programa Python.
Programa Python
# Here, we are declaring the function to divide the lists in to the two sub lists # Here, we are passing the list1, left index, right index as the parameters def merge_sort(list1, left_index, right_index): if left_index >= right_index: # here, we are checking the if condition return middle = (left_index + right_index)//2 # Here, we are finding the middle of the given two numbers merge_sort(list1, left_index, middle) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, middle + 1, right_index) # Here, we are calling the merge sort function till the end of the list i.e., right index merge(list1, left_index, right_index, middle) # Here, we are calling the merge function to merge the divided list using the merge # sort function above # Here, we are defining a function for merge the list after dividing def merge(list1, left_index, right_index, middle): # Here, we are creating subparts of a lists left_sublist = list1[left_index:middle + 1] right_sublist = list1[middle+1:right_index+1] # Here, we are initializing the values for variables that we use to keep # track of where we are in each list1 left_sublist_index = 0 right_sublist_index = 0 sorted_index = left_index # Here, we are traversing the both copies until we get run out one element while left_sublist_index <len(left_sublist) 1 and right_sublist_index < len(right_sublist): # here, we are declaring a while loop if our left_sublist has the smaller element, put it in sorted part then move forward (by increasing pointer) left_sublist[left_sublist_index] checking condition, is true will enter block list1[sorted_index]="left_sublist[left_sublist_index]" left_sublist_index="left_sublist_index" + otherwise add into right sublist else: moving sorted_index="sorted_index" go through remaining elements them len(left_sublist): len(right_sublist):# list1="[44," 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] print('the given list before performing merge sort is: ', list1) this input unsorted array by user merge_sort(list1, 0, len(list1) -1) after is:', printing amd functions pre> <p> <strong>Output:</strong> </p> <pre> The given list before performing the merge sort is: [44, 65, 2, 3, 58, 14, 57, 23, 10, 1, 7, 74, 48] The given list after performing the merge sort is: [1, 2, 3, 7, 10, 14, 23, 44, 48, 57, 58, 65, 74] </pre> <h2>Sorting Custom Objects</h2> <p>We can also sort the custom objects by using the <a href="/python-tutorial-python-programming-language">Python</a> class. This algorithm is almost similar to the above but we need to make it more versatile and pass the comparison function.</p> <p>We will create a custom class, Car and add a few fields to it. We make few changes in the below algorithm to make it more versatile. We can do this by using the lambda functions.</p> <p>Let's understand the following example.</p> <h3>Python Program</h3> <pre> class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format('Make: {}, Model: {}, Year: {}', self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car('Renault', '33 Duster', 2001) car2 = Car('Maruti', 'Maruti Suzuki Dzire', 2015) car3 = Car('Tata motor', 'Jaguar', 2004) car4 = Car('Cadillac', 'Seville Sedan', 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print('cars sorted by year:') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let's understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)></pre></len(left_sublist)> Ordenar objetos personalizados
También podemos ordenar los objetos personalizados usando el Pitón clase. Este algoritmo es casi similar al anterior, pero debemos hacerlo más versátil y pasar la función de comparación.
Crearemos una clase personalizada, Auto y le agregaremos algunos campos. Realizamos algunos cambios en el siguiente algoritmo para hacerlo más versátil. Podemos hacer esto usando las funciones lambda.
Entendamos el siguiente ejemplo.
jquery al hacer clic
Programa Python
class Car: # here, we are declaring a class named car def __init__(self, make, model, year): self.make = make # Here, we are using the self to declare the make variables locally self.model = model # Here, we are using the self to declare the model variables locally self.year = year # Here, we are using the self to declare the year variables locally def __str__(self): return str.format('Make: {}, Model: {}, Year: {}', self.make, self.model, self.year) # Here, we are returning the format of the strings given def merge(list1, l, r, m, comp_fun): # Here, we are defining a function for merge the list using the compound function left_copy = list1[l:m + 1] # here, we are coping the left part of the list r_sublist = list1[m+1:r+1] # here, we are coping the right part of the list left_copy_index = 0 # here, we are coping the left part indexes of the list r_sublist_index = 0 # here, we are coping the right part indexes of the list sorted_index = l while left_copy_index <len(left_copy) 1 and r_sublist_index < len(r_sublist): # here, we are declaring a while loop using the comp_fun instead of simple comparison operator if comp_fun(left_copy[left_copy_index], r_sublist[r_sublist_index]): checking condition, it is true then will enter block list1[sorted_index]="left_copy[left_copy_index]" left_copy_index="left_copy_index" + else: condition false else sorted_index="sorted_index" len(left_copy): <len(r_sublist): def merge_sort(list1, l, r, comp_fun): merge sort function to given list l>= r: # Here, we are checking the if condition, if it is true then we will enter the block return m = (l + r)//2 # here, we are finding the middle element of the list merge_sort(list1, l, m, comp_fun) # Here, we are calling the merge sort function till the middle number we got merge_sort(list1, m + 1, r, comp_fun) # Here, we are calling the merge sort function from the middle number we got merge(list1, l, r, m, comp_fun) # Here, we are calling the merge function to merge the divided list using the merge # sort function above car1 = Car('Renault', '33 Duster', 2001) car2 = Car('Maruti', 'Maruti Suzuki Dzire', 2015) car3 = Car('Tata motor', 'Jaguar', 2004) car4 = Car('Cadillac', 'Seville Sedan', 1995) list1 = [car1, car2, car3, car4] merge_sort(list1, 0, len(list1) -1, lambda carA, carB: carA.year <carb.year) print(\'cars sorted by year:\') for car in list1: # here, we are declaring the loop to iterate through list1 print(car) printing all data of and list print() merge_sort(list1, 0, len(list1) -1, lambda cara, carb: cara.make < carb.make) make:\') pre> <p> <strong>Output:</strong> </p> <pre> Cars sorted by year: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Renault, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Cars sorted by make: Make: Cadillac, Model: Seville Sedan, Year: 1995 Make: Maruti, Model: Maruti Suzuki Dzire, Year: 2015 Make: Renualt, Model: 33 Duster, Year: 2001 Make: Tata motor, Model: Jaguar, Year: 2004 </pre> <h2>Optimization</h2> <p>We can improve the performance of the merge sort algorithm. First let's understand the difference between the top-down and bottom-up merge sort. The bottom-up approach sorts the elements of adjacent lists iteratively where the top-down approach breaks down the lists into the two halves.</p> <p>The given list is [10, 4, 2, 12, 1, 3], instead of breaking it down into [10], [4], [2], [12], [1], [3] - we divide into the sub lists which may already sorted: [10, 4], [2], [1, 12], [3] and now are ready to sort them.</p> <p>Merge sort is inefficient algorithm in both time and space for the smaller sub lists. So, insertion sort is more efficient algorithm than the merge sort for the smaller sub lists.</p> <h2>Conclusion</h2> <p>Merge sort is popular and efficient algorithm. It is more efficient algorithm for the large lists. It does not depend on the any unfortunate decisions that lead to bad runtimes.</p> <p>There is one major demerit in the merge sort. It uses the additional memory that is used to store the temporary copies of lists before merging them. However Merge sort is widely used in the software. Its performance is fast and produces the excellent result.</p> <p>We have discussed the merge sort concept in brief and implement it both on simple integer list and on custom objects via a lambda function used for comparison.</p> <hr></carb.year)></len(left_copy)> Mejoramiento
Podemos mejorar el rendimiento del algoritmo de clasificación por combinación. Primero, comprendamos la diferencia entre el orden de combinación de arriba hacia abajo y de abajo hacia arriba. El enfoque ascendente clasifica los elementos de listas adyacentes de forma iterativa, mientras que el enfoque descendente divide las listas en dos mitades.
La lista dada es [10, 4, 2, 12, 1, 3], en lugar de dividirla en [10], [4], [2], [12], [1], [3] - dividimos en las sublistas que pueden ya estar ordenadas: [10, 4], [2], [1, 12], [3] y ahora están listas para ordenarlas.
La ordenación por combinación es un algoritmo ineficiente tanto en el tiempo como en el espacio para las sublistas más pequeñas. Por lo tanto, la ordenación por inserción es un algoritmo más eficiente que la ordenación por combinación para las sublistas más pequeñas.
Conclusión
La clasificación por combinación es un algoritmo popular y eficiente. Es un algoritmo más eficiente para listas grandes. No depende de decisiones desafortunadas que conduzcan a malos tiempos de ejecución.
Hay un gran inconveniente en el tipo de fusión. Utiliza la memoria adicional que se utiliza para almacenar las copias temporales de las listas antes de fusionarlas. Sin embargo, la ordenación por combinación se usa ampliamente en el software. Su rendimiento es rápido y produce un resultado excelente.
Hemos analizado brevemente el concepto de ordenación por combinación y lo implementamos tanto en una lista de enteros simples como en objetos personalizados a través de una función lambda utilizada para la comparación.