Combinar dos listas ordenadas en Python

1. Combinar dos listas ordenadas en Python
2. Enfoque ingenuo para fusionar dos listas ordenadas en Python
3. Combinar dos listas ordenadas usando el método heapq.merge() en Python
4. Combinar dos listas ordenadas usando la función sorted() en Python
5. Conclusión

Las listas ordenadas son las que están organizadas en orden ascendente o descendente, y fusionar estas listas ordenadas se refiere a combinar ambas listas de tal manera que permanezcan ordenadas.

Hay varios métodos en Python en los que podemos fusionar las dos listas ordenadas. Python tiene funciones integradas para realizar esta tarea, pero también discutiremos el enfoque ingenuo utilizado para diseñar estas funciones integradas.

Combinar dos listas ordenadas en Python

En este artículo, se nos da una declaración del problema y se nos pide que diseñemos una solución para el mismo. El problema es que tenemos dos listas ordenadas individualmente, pero necesitamos fusionarlas para que permanezcan ordenadas después de la fusión.

Entendamos esto con un ejemplo.

list1 = [2, 5, 7, 8, 9]
list2 = [0, 1, 3, 4, 6]

Producción :

Sorted List: [0,1,2,3,4,5,6,7,8,9]

La lista ordenada en la salida se compone de los elementos de las listas lista1 y lista2. Después de fusionarse, se organizan de modo que la lista combinada aún esté ordenada.

Este problema es el mismo que diseñar la función merge utilizada en el merge sort. Por lo tanto, a menudo nos encontramos con este tipo de problemas al resolver estas preguntas.

Por lo tanto, debemos tener una idea básica sobre cómo abordarlo. Ahora, comprendamos cómo resolveremos este problema.

Enfoque ingenuo para fusionar dos listas ordenadas en Python

La solución que discutiremos es un enfoque ingenuo que fusionará las dos listas ordenadas en Python. En este enfoque, recorremos ambas listas simultáneamente y buscamos el elemento más pequeño entre los dos elementos en la posición actual.

El elemento más pequeño se adjunta a la respuesta. Sin embargo, si una de las dos listas se recorre por completo, la otra lista se agrega al resultado después de los elementos combinados.

Veamos el código para entenderlo mejor.

firstList = [2, 7, 8, 9]
secondList = [0, 1, 4, 6]
result = []
i, j = 0, 0

while i < len(firstList) and j < len(secondList):
    if firstList[i] < secondList[j]:
        result.append(firstList[i])
        i = i + 1
    else:
        result.append(secondList[j])
        j = j + 1

result = result + firstList[i:] + secondList[j:]
print("Sorted List: " + str(result))

Producción :

Sorted List: [0, 1, 2, 4, 6, 7, 8, 9]

Hemos declarado una lista vacía resultado en el código anterior, que almacenará nuestra lista fusionada. Luego hemos iterado a través de ambas listas hasta que cualquiera de ellas o ambas se agotan.

Dentro del bucle, comparamos los elementos de ambas listas y agregamos el elemento más pequeño a nuestra variable de resultado, después de lo cual incrementamos el índice actual en 1.

Si alguna de las listas tiene elementos que no están incluidos en nuestro resultado, fusionamos los elementos restantes en nuestra respuesta usando el operador de corte en Python.

En este enfoque, hemos iterado solo una vez a través de las listas; por lo tanto, tiene una complejidad temporal de O(n1+n2), mientras que la complejidad espacial para el enfoque anterior también es O(n1+n2), donde n1 y n2 se refieren a los tamaños de los elementos ordenados. liza.

Combinar dos listas ordenadas usando el método heapq.merge() en Python

El módulo heapq en Python se refiere a la cola Heap. Sin embargo, este módulo, Heapq, se usa principalmente para implementar la cola de prioridad en Python.

El módulo heapq contiene la función merge() en Python que toma varias listas ordenadas como argumento y devuelve una sola lista combinada y fusionada.

Veamos cómo podemos realizar la operación de fusión usando la función heapq.merge() en Python.

from heapq import merge

first = [2, 7, 8, 9]
second = [0, 1, 4, 6]

res = list(merge(first, second))

print("Merged Sorted list: ", str(res))

Producción :

Merged Sorted list:  [0, 1, 2, 4, 6, 7, 8, 9]

En el código anterior, hemos pasado las dos listas ordenadas “primero” y “segundo” en la función “combinar ()” como argumento, después de lo cual las convertimos en una lista explícitamente. Como resultado, la lista ordenada fusionada se almacenará en la variable ans.

Como podemos ver, podemos usar la función merge() del módulo heapq para fusionar dos listas ordenadas en Python.

Combinar dos listas ordenadas usando la función sorted() en Python

La función sorted() de Python ordena las listas o tuplas proporcionadas como parámetro. Siempre devuelve una lista que se ordenará sin cambiar la secuencia original.

Podemos usar esta función para resolver nuestro problema en una sola línea. Agregamos ambas listas juntas y luego aplicamos la función sorted() a la lista resultante.

Entendámoslo con un ejemplo.

first = [2, 7, 9]
second = [0, 1, 4]

result = sorted(first + second)

print("List after sorting: ", str(result))

Producción :

List after sorting:  [0, 1, 2, 4, 7, 9]

En el programa anterior, hemos utilizado el operador + para unir las dos listas. El operador de concatenación + se usa para agregar varias listas en una sola lista combinada en el orden en que se ingresaron en el código.

Después de lo cual, hemos aplicado la función sorted() a la lista adjunta, que ordena la secuencia e imprime el resultado.

Este enfoque puede llevar más tiempo porque internamente estamos agregando dos listas en una sola lista, lo que llevará más tiempo que los otros dos enfoques discutidos anteriormente.

Conclusión

Este artículo analiza los diferentes enfoques en los que podemos fusionar dos listas ordenadas en Python. Dos de ellos son métodos integrados en Python, mientras que el otro es un enfoque detallado del problema.

La función sorted() es una de las funciones incorporadas que se usan para ordenar las listas adjuntas, mientras que la otra heapq.merge() es un método que se usa para fusionar las dos listas ordenadas en Python. Ambas funciones pueden realizar las operaciones en una sola línea.

El enfoque detallado es iterar a través de las listas, comparar cada elemento en el índice actual, agregar el elemento más pequeño a la respuesta y luego incrementar el índice actual en 1. Este bucle se ejecuta hasta que una o ambas listas se agotan, después de lo cual el resto los elementos se agregan a través del operador de corte de Python.

Puede usar cualquiera de los métodos discutidos anteriormente para resolver el problema.