Stitching two lists together

Dev Shed Forums Sponsor:

October 3rd, 2012, 04:28 AM

jepot

Registered User

Join Date: Dec 2008

Posts: 17

Time spent in forums: 5 h 17 m 23 sec
Reputation Power: 0

Stitching two lists together

say i have two sorted lists, list1 and list2. i would like to stitch these two lists together to another list, list3. This list would have all items on list1 and list2 sorted in order. How would i go about doing it? I think the way i approached this problem is wrong, below is my trial:

Code:

    a, b, result = 0, 0, []
    
    while a != len(list1) or b != len(list2):
        if list1[a] <= list2[b]:
            result.append(list1[a])
            a += 1
        else:
            result.append(list2[b])
            b += 1

I would like to see a correct implementation so I can see which assumption is wrong in my approach

October 3rd, 2012, 06:44 AM

SuperOscar

Contributing User

Join Date: Jul 2007

Location: Joensuu, Finland

Posts: 412

Time spent in forums: 1 Week 7 h 14 m 58 sec
Reputation Power: 65

Quote:

Originally Posted by jepot

say i have two sorted lists, list1 and list2. i would like to stitch these two lists together to another list, list3.

Is it really necessary to “stitch” them together? If the lists aren’t inordinately long, the easiest way would be to combine them and then sort.

Code:

>>> l1 = ['a', 'd', 'q']
>>> l2 = ['b', 'c', 'f']
>>> l1 + l2
['a', 'd', 'q', 'b', 'c', 'f']
>>> sorted(l1 + l2)
['a', 'b', 'c', 'd', 'f', 'q']

Otherwise, at least if the lists are of equal length, you might do:

Code:

l3 = []
for x, y in zip(l1, l2):
    l3.append(x if x < y else y)
    l3.append(y if x < y else x)

Comments on this post

b49P23TIvg disagrees:

Code:

&gt;&gt;&gt; l3 = [] &gt;&gt;&gt; for x, y in zip([1,2,3], [4,5,6]): ...     l3.append(x if x
&lt; y else y) ...     l3.append(y if x &lt; y else x) ...   &gt;&gt;&gt; l3 [1, 4, 2, 5, 3,
6]

__________________
My armada: openSUSE 12.3 (home desktop, laptop, work desktop), Ubuntu 12.04 LTS (mini laptop), Debian GNU/Linux 7.0 (server), Mythbuntu 12.04 LTS (HTPC), Bodhi Linux 2.0 & Windows 7 Ultimate (test desktop), FreeBSD 9.1 (test server)

October 3rd, 2012, 09:06 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,460

Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 56 m 42 sec
Reputation Power: 403

I'm astounded that my merge function performs almost as well as combining the lists, then using lists's sort method. p.py uses list.sort(), q.py uses merge. Timings and tests are shown.

p.py

Code:

#$ time python /tmp/p.py
#
#real	0m0.532s
#user	0m0.504s
#sys	0m0.020s

import random

N = 100000

def IsSorted(L):
    '''
        $ python -m doctest p.py
        >>> IsSorted(list('acx'))
        True
        >>> IsSorted(list('cax'))
        False
    '''
    return all(x<=y for (x,y,) in zip(L[:-1],L[1:]))

a = list(random.random() for i in range(N))
b = list(random.random() for i in range(N))
a.sort()
b.sort()
c = a+b
c.sort()
assert IsSorted(c)

q.py

Code:

#$ time python /tmp/q.py
#
#real	0m0.589s
#user	0m0.540s
#sys	0m0.040s

import random

N = 100000

def IsSorted(L):
    '''
        $ python -m doctest p.py
        >>> IsSorted(list('acx'))
        True
        >>> IsSorted(list('cax'))
        False
    '''
    return all(x<=y for (x,y,) in zip(L[:-1],L[1:]))

a = list(random.random() for i in range(N))
b = list(random.random() for i in range(N))
a.sort()
b.sort()

def merge(a,b):
    '''
        >>> ''.join(merge(list('Abf'),list('CDEfnp')))
        'ACDEbffnp'
    '''
    c = []
    i = j = 0
    La = len(a)
    Lb = len(b)
    while (i < La) and (j < Lb):
        if a[i] < b[j]:
            c.append(a[i])
            i += 1
        else:
            c.append(b[j])
            j += 1
    if i < La:
        c.extend(a[i:])
    elif j < Lb:
        c.extend(b[j:])
    return c

c = merge(a,b)
c.sort()
assert IsSorted(c)

__________________
[code]Code tags[/code] are essential for python code!

October 3rd, 2012, 09:15 AM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,460

Time spent in forums: 1 Month 2 Weeks 4 Days 6 h 56 m 42 sec
Reputation Power: 403

(Point was to use SuperOscar's second code with the lists
[1,2,3] and [4,5,6])

(answering jepot's question,

the != len tests should be < len

and then jepot must account for remainder of list, that's what my extend business handles.
)

Stitching two lists together

Developer Shed Advertisers and Affiliates