CODEWITHSUNDEEP
pythonlistsorting
Codelyf
Codelyf

Reputation: 17

List sorting except zero in python

i have a list [5,3,0,0,4,1,4,0,7] and i want to sort the list in someway that zeros remain in their position and others be sorted the answer is like this [1,3,0,0,4,4,5,0,7]

i wrote this code but i cant fix the zeros in their place

def except_zero(items: list) -> Iterable: 
    ans=[] 
    for i in range(len(items)): 
        if (items[i] != 0): 
            ans.append(items[i]) 
            ans = sorted(ans) 

    j = 0 
    for i in range(len(items)): 
        if (items[i] >= 0): 
            items[i] = ans[j] 
            j += 1 
            return ans

Upvotes: 2

Views: 2521

Answers (8)

Mous
Mous

Reputation: 1047

Here's a concise, elegant and fast way to do it.

def except_zero(items):
    nonzero = iter(sorted(filter(bool, items)))
    return [i and next(nonzero) for i in items]

How does it compare?

For all these tests, I used a list with a million elements, of which 10% were each integer from 0 to 9, running on Python 3.11.4.

It's 2837x faster than Mr Felix U's solution.

It's 2805x faster than Onilol's solution.

It's 109x faster than FAL's solution.

It's 108x faster than Daweo's solution (the accepted answer).

It's 39% faster than blhsing's solution.

It's 34% faster than Nikos M's solution.

Prasad Shembekar's solution doesn't work.

How does it work?

The filter takes advantage of the fact that, for float and int, the only value that will return False when passed to bool is 0 - so all other values will be True. This gives us our nonzero values, which we then sort (with sorted) and convert to an iterable (with iter) so that we can use next on it.

The list comprehension utilises a short-circuit - if i is 0, the and short-circuits, returning the last evaluated value (0). This has the effect of placing the zeroes in their original positions. The next fills in the spaces which weren't zeroes with the sorted values, which we generated earlier.

Upvotes: 0

Prasad Shembekar
Prasad Shembekar

Reputation: 19

this solution might help you

my_list = [3, 0, 1, 0, 5, 2, 0, 4]

# Sort the list, excluding zeros
sorted_list = sorted(my_list, key=lambda x: (x == 0, x))

print(sorted_list)

Upvotes: 0

Nikos M.
Nikos M.

Reputation: 8345

def except_zero(items: list) -> Iterable: 
    ans=[]
    ind=[]
    for i in range(len(items)): 
        if (items[i] != 0): 
            ans.append(items[i]) 
            ind.append(i)

    ans = list(sorted(ans))
    for i in range(len(ind)): 
            items[ind[i]] = ans[i] 
    return items

Something like the above would work, you simply store the index positions of non-zero values and then placve the sorted values into the corresponding index positions

Even your own approach can work if you fix a couple of issues, for example:

def except_zero(items: list) -> Iterable: 
    # get and sort non zero values
    non_zero = list(sorted([x for x in items if x!=0]))
    j = 0 
    # place them in correct position
    for i in range(len(items)): 
        if (items[i] != 0): 
            items[i] = non_zero[j]  # get next sorted non_zero value for this position
            j += 1 # update index

    return items

Upvotes: 1

FAL
FAL

Reputation: 163

You should first save the index position of zero values:

zero_positions = [i for i, this in enum(mylist) if this == 0]

then you could sort the list without the zero values:

ordered = [this for this in mylist if this != 0].sorted()

and finally you could insert zeros in the correct positions:

for i in zero_positions:
    ordered.insert(i, 0)

That's all. Maybe there is a faster way, this is the first that came to my mind.

Hope that helps Francesco

Upvotes: 1

blhsing
blhsing

Reputation: 106658

A more efficient approach that solves the problem in O(n) time complexity is to store the indices of zeroes in a set, sort the rest of the items, and then iterate an index over the length of the input list to output zeroes if the index is in the set, or the next item in the sorted list if not:

def except_zero(items):
    zeroes = {i for i, v in enumerate(items) if v == 0}
    others = iter(sorted(v for v in items if v != 0))
    return [0 if i in zeroes else next(others) for i in range(len(items))]

so that:

except_zero([5,3,0,0,4,1,4,0,7])

returns:

[1, 3, 0, 0, 4, 4, 5, 0, 7]

Upvotes: 2

Onilol
Onilol

Reputation: 1339

You can try this:

def sort_and_extract_non_zero_items(items: list) -> Iterable:
  return sorted([n for n in l if n != 0])

def replace_non_zero_items(original: list, non_zeroes: list) -> Iterable:
  return [non_zeroes.pop(0) if n != 0 else 0 for n in original]

non_zero_list = sort_and_extract_non_zero_items(items)

items = replace_non_zero_items(items, non_zero_list)

Upvotes: 3

Daweo
Daweo

Reputation: 36550

I would do:

orig_list = [5,3,0,0,4,1,4,0,7]
result = sorted([i for i in orig_list if i!=0])
for inx, elem in enumerate(orig_list):
    if elem == 0:
        result.insert(inx, 0)
print(result)  # [1,3,0,0,4,4,5,0,7]

Firstly I sort nonzeros, then insert zero in result list in places where it appear in orig_list.

Upvotes: 3

Mr Felix U
Mr Felix U

Reputation: 335

Not elegant, but seems to work:

l_in = [5,3,0,0,4,1,4,0,7]
l_out = []

# grab and sort all your non-zero values
nonz = sorted([x for x in l_in if x!=0])

# build your new list, adding a zero if there was one in that
# position, else poppping off the first item in the sorted
# non-zero list
for i in range(len(l_in)):
    l_out.append(0 if l_in[i]==0 else nonz.pop(0))

print(l_out)

Upvotes: 1

Related Questions