Push all zeros to one side of the list

Question

Hello I'm trying to push all zeros in a list to one side without altering the rest of it:
[0,2,0,0,9] -> [0,0,0,2,9]
[3,4,0,1,0] -> [0,0,3,4,1]

My solution:

def getNonZeros(self, tup):
    for i in tup:
        if i != 0:
            yield i;

def pushZeros(self, tup, side):
    if side==Side.End:
        return [i for i in self.getNonZeros(tup)] + [0]*tup.count(0);
    else:
        return [0]*tup.count(0) + [i for i in self.getNonZeros(tup)];

And I get this error in ipython:

ERROR: Internal Python error in the inspect module.
Below is the traceback from this internal error.
Traceback (most recent call last):
  File "/usr/lib/python2.7/site-packages/IPython/core/ultratb.py", line 760, in     structured_traceback
    records = _fixed_getinnerframes(etb, context, tb_offset)
  File "/usr/lib/python2.7/site-packages/IPython/core/ultratb.py", line 242, in     _fixed_getinnerframes
    records  = fix_frame_records_filenames(inspect.getinnerframes(etb, context))
  File "/usr/lib64/python2.7/inspect.py", line 1043, in getinnerframes
    framelist.append((tb.tb_frame,) + getframeinfo(tb, context))
  File "/usr/lib64/python2.7/inspect.py", line 1007, in getframeinfo
    lines, lnum = findsource(frame)
  File "/usr/lib64/python2.7/inspect.py", line 580, in findsource
    if pat.match(lines[lnum]): break
IndexError: list index out of range

Unfortunately, your original traceback can not be constructed.

score 10 · Accepted Answer · answered Jun 08 '14 at 13:34

10

Since Python sorts are intrinsically stable, you could simple do this

>>> sorted([0,2,0,0,9], key=lambda x: x != 0)
[0, 0, 0, 2, 9]
>>> sorted([3,4,0,1,0], key=lambda x: x != 0)
[0, 0, 3, 4, 1]

answered Jun 08 '14 at 13:34

iruvar

22,736
7
53
82

+1 for not reinventing the wheel & knowing what the language does on its own. – bgporter Jun 08 '14 at 13:35
also has nice potential for an in-place sort if that's applicable – cmh Jun 08 '14 at 13:36

Padraic Cunningham · Answer 2 · 2014-06-08T13:53:28.797

2

l=[3,4,0,1,0]

new_l = [x for x in l if x!=0]+[0 for y in range(l.count(0))]
[3, 4, 1, 0, 0]

The timing:

In [23]: %timeit [x for x in l if x!=0]+[0 for y in range(l.count(0))]
1000000 loops, best of 3: 752 ns per loop

In [24]: %timeit sorted([3,4,0,1,0], key=lambda x: x != 0)
1000000 loops, best of 3: 1.41 µs per loop

Or:

In [25]: %timeit [x for x in l if x != 0] + [0]*  l.count(0)
1000000 loops, best of 3: 582 ns per loop

edited Jun 08 '14 at 13:53

answered Jun 08 '14 at 13:31

Padraic Cunningham

176,452
29
245
321

Can't I write `[0]*l.count(0)`? – haansn08 Jun 08 '14 at 13:45
In [107]: %timeit [x for x in l if x!=0]+[0 for y in range(l.count(0))] 1000000 loops, best of 3: 907 ns per loop In [108]: %timeit [x for x in l if x!=0]+[0] * l.count(0) 1000000 loops, best of 3: 726 ns per loop – volcano Jun 08 '14 at 13:45
@haansn08, yes, I was being explicit. If you want it the other way around obviously change the order. I added it to the answer. – Padraic Cunningham Jun 08 '14 at 13:50

score 1 · Answer 3 · answered Jun 08 '14 at 13:36

Just sort the list with a custom key:

In [1]: L = [3, 4, 0, 1, 0]

In [2]: L.sort(key=lambda x: -1 if x == 0 else 1)

In [3]: L
Out[3]: [0, 0, 3, 4, 1]

Note:

Sorting is guaranteed to be stable, so all the numbers relative order is retained
Sorting uses tim-sort which is O(n) when the input is almost already sorted, and this is the case (remember that only the keys are compared, which means that the only non-ordered points are when you have a 0 followed by a different number or the opposite).

Push all zeros to one side of the list

3 Answers3

Linked

Related