For example, I have a list with many many elements
x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8], ...]
each element has already sorted.
How can I get a list named y
that is from x
's elements and sorted it?
For example, I have a list with many many elements
x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8], ...]
each element has already sorted.
How can I get a list named y
that is from x
's elements and sorted it?
If I understand your question correctly, you should look into heapq.merge
:
>>> import heapq
>>> lists = x = [[1, 2, 3], [3, 4, 5], [2, 3, 4], [4, 7, 8]]
>>> list(heapq.merge(*lists))
[1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 7, 8]
Here is a simple solution without any library:
x = [[1,2,3], [3,4,5], [2,3,4], [4,7,8]]
print(sorted([item for sublist in x for item in sublist]))
Returns: [1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 7, 8]
If you just want to sort use sorted
,try this
x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8]]
y = sorted(x)
print y
If you want to get all elements in sorted way,try this
x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8]]
y = sorted([item for sublist in x for item in sublist])
print y
You need a "merge" operation: just start with two lists and keep taking the element that is smaller; when one list is completed copy the eventually remaining elements from the other one...
def merge(A, B):
result = []
ia = ib = 0
while ia < len(A) and ib < len(B):
if a[ia] < b[ib]:
result.append(A[ia])
ia += 1
else:
result.append(B[ib])
ib += 1
# copy "tail"
while ia < len(A):
result.append(A[ia])
ia += 1
while ib < len(B):
result.append(B[ib])
ib += 1
return result
If you have a collection of N
lists just merge them in pairs and you will end up with half of them. Repeat until you get just one list.
[[1], [2], [3], ..., [100]]
. Your algorithm which is to merge them 2 at a time will produce [1, 2]
which needs to be merged with [3]
, then [4]
, then ... At each point, you need to look at all of the numbers that you've already merged before you can start putting in the new data. I think this leads to an O(N^2) merging time. If you know the mins from all of the lists, you can put them in a heap ...
[[1], [2], [3], [4], [5], [6], ...]
to [[1,2], [3,4], [5, 6], ...]
, not keeping merging the same list with all the other ones.
I am going to give you some pointers.
First, define a function merge(x, y)
that gets two sorted lists and returns a combined sorted list.
Then, run merge on couples
[merge(lst[i], lst[i+1] ) for i in range(0,len(lst),2) ]
This process should be repeated as long as the list has more than two elements, and if the number of elements is odd, append [] to it
Method 1:
import heapq
x = [[1, 2, 3], [3, 4, 5],[2, 3, 4], [4, 7, 8]]
y = list(heapq.merge(*x))
Method 2:
import itertools
y = sorted(itertools.chain(*x))
itertools.chain.from_iterable(x)
(just to get in the habit)