Sort only the odd numbers

[tomhuang]

my question here
Define a function that takes an array of numbers and sorts only the odd ones in ascending order, leaving the even ones in their places. No need to move the number 0 should it occur. Here is an example:

sort_odds([1,5,3,2,7,7,3,2,7]) -> [1, 3, 3, 2, 5, 7, 7, 2, 7]

How can I add the even # back to their original positions?

[
python]my code here[/python]
def sort_odds(arr):
return sorted([i for i in arr if i%2!= 0])

[Bass]

My thoughts.

Once the odd numbers have been sorted.
Scan the original array, search for even numbers, once you have an even number, calculate its position and then insert it into the new array in that position.

Is this what you are looking for?

Bass

[nilamo]

Sorting the odd numbers, and then inserting the evens at their original index, would probably be the easiest way, but my guess is that it'd also be the slowest, since you're effectively sorting the list twice. How important is efficiency? How big are the lists you're sorting?

[ichabod801]

I was thinking scan the original array, and whenever there is an odd number, replace it with the next number from the sorted array.

Thinking through it I think Bass's solution would be easier to implement, especially using enumerate.

[ichabod801]

Sorting the odd numbers, and then inserting the evens at their original index, would probably be the easiest way, but my guess is that it'd also be the slowest, since you're effectively sorting the list twice.

What would be faster? It's not double sorting, it's sorting once and making one pass. Anything quicker would require keeping the evens in place while sorting once. That would require rewriting the sort algorithm, which I expect would be slower than the optimized sort method.

[buran]

#!/usr/bin/env/python3

original_list = [1,5,3,2,7,7,3,2,7]

def sort_odds(lst):
    sorted_odds = sorted([n for n in lst if n%2])
    new_list = []
    for n in lst:
        if n%2:
            new_list.append(sorted_odds.pop(0))
        else:
            new_list.append(n)
    return list(new_list)
print(sort_odds(original_list))

if efficiency is concern, you may use collections.deque to optimize the popleft operation

#!/usr/bin/env/python3

from collections import deque

original_list = [1,5,3,2,7,7,3,2,7]

def sort_odds(lst):
    sorted_odds = deque(sorted([n for n in lst if n%2])) #using deque to optimize pop
    new_list = []
    for n in lst:
        if n%2:
            new_list.append(sorted_odds.popleft())
        else:
            new_list.append(n)
    return list(new_list)
print(sort_odds(original_list))