Python with two iterators increments one at a time
I am new to python.
I tried to implement something like merge sort in python. I used a single list from https://pythonhosted.org/llist/#sllist-objects . To combine two sorted lists, I need to traverse both lists using an iterator. The pseudocode looks something like this:
n3 = sllist()
for n1 in list1 and n2 in list2:
if (n1 > n2):
n3.append(n1)
n1++ # c way of doing thing
else:
n3.append(n2)
n2++ # c way of doing thing
But I don't know how to get this to work in python. Any pointer or hint would help.
Edit: After all the discussions and suggestions, I came up with a code like this. Can anyone tell me how to get rid of the last two loops. I was planning on using "extension" but was unable to use it.
final_list = sllist()
node1 = list1.first
node2 = list2.first
while node1 and node2:
if node1.value < node2.value:
final_list.append(node1)
node1 = node1.next
else:
final_list.append(node2)
node2 = node2.next
while node1:
final_list.append(node1)
node1 = node1.next
while node2:
final_list.append(node2)
node2 = node2.next
return final_list
source to share
I usually do this with iteration and next
:
lst1 = iter(list1) lst2 = iter(list2) out = sllist() sentinel = object() n1 = next(lst1, sentinel) n2 = next(lst2, sentinel) while n1 is not sentinel and n2 is not sentinel: if n1 > n2: out.append(n2) n2 = next(lst2, sentinel) elif n2 >= n1: out.append(n1) n1 = next(lst1, sentinel) out.extend(lst1) out.extend(lst2)
As pointed out in the comments, you can also write it like:
lst1 = iter(list1)
lst2 = iter(list2)
out = sllist()
try:
n1 = next(lst1)
n2 = next(lst2)
while True:
if n1 > n2:
out.append(n2)
n2 = next(lst2)
elif n2 >= n1:
out.append(n1)
n1 = next(lst1)
except StopIteration: # raised when next(...) fails.
out.extend(lst1)
out.extend(lst2)
It is functionally equivalent. Pick your choice :-)
source to share