[Tutor] to place all zeros of an existing list in the starting of a new list

[Roel Schroeven]

Manprit Singh schreef op 31/05/2021 om 1:56:
> Consider a list ls = [2, 5, 0, 9, 0, 8], now i have to generate a new list
> from this existing list , new list must contain all zeros in the starting,
> all other elements of the existing list must be placed after zeros in new
> list . So new list must be :
> new = [0, 0, 2, 5, 9, 8]
> 
> The way I am doing it is :
>>>> ls = [2, 5, 0, 9, 0, 8]
>>>> sorted(ls, key=lambda x: x != 0)
> [0, 0, 2, 5, 9, 8]
>>>>
> Is this the correct way ? or is there something better that can be done ?

First, a note about correctness:

Your approach is fine if the sort function you use is stable, meaning 
that it doesn't change the relative order of elements that compare equal 
(i.e. in this case: keep 2, 5, 9 and  in the correct order). It just so 
happens that Python's sorted() function, and the sort() method on lists, 
are guaranteed to be stable, so your approach works just fine.

Just remember that that doesn't necessarily translate to other 
environments. For example, std::sort() in C++ is *not* guaranteed to 
preserve the order of equal elements (I know because I got bitten by 
that some time ago). When you ever face a similar problem using another 
sort function, be sure to read the documentation to find out if the sort 
function is stable.


Secondly, an alternative approach, with different performance:

Python uses Timsort (so called because it's written by Python dev Tim 
Peters); see https://en.wikipedia.org/wiki/Timsort. Timsort is pretty 
efficient as sorting algorithms go; in fact it is adopted in the sorting 
functions in other programming languages. Even so, it may be that 
another approach may be faster.

You could do two passes over the original list: first to collect the 
zeros, next to collect all the other numbers, and then put them all 
together:

     [n for n in ls if n == 0] + [n for n in ls if n != 0]

Or a variation that prevents building two possibly large temporary list 
through the use of generator expressions and itertools.chain to combine 
them:

     from itertools import chain
     list(chain((n for n in ls if n == 0), (n for n in ls if n != 0)))

The sorting approach has complexity O(n log n), my alternative has 
complexity O(n). O(n) is better all else being equal, but simply 
comparing the complexities isn't the whole story. It's very well 
possible that my alternative has a high constant factor, meaning that is 
slower for small lists and only gets faster than your approach for very 
large lists.

I don't really think it's something to worry about, unless this is 
something you are going to use in a time-sensitive situation with large 
lists, in which case you should benchmark different approaches. Mainly I 
just wanted to show you a possible alternative solution.

-- 
"Honest criticism is hard to take, particularly from a relative, a
friend, an acquaintance, or a stranger."
         -- Franklin P. Jones

Roel Schroeven