How to sort even/odd numbers separately in a list?

Question

I have list with both even and odd numbers. I want to sort the positions with even, odd distinct numbers together. It's like:

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]
#    5        7  11          1  3
#       6  4         14  12
#Now sort it
#    1        3  5          7  11
#       4  6        12  14
#   [1, 4, 6, 3, 5, 12, 14, 7, 11] -> result list

I read two posts here and here but it different with my case.

Is there any way to sort it this way?

please post the code that you are executing based on the solutions you linked, so we can take a look at the actual code you are using. — Sembei Norimaki, Mar 16 '23 at 09:42
@SembeiNorimaki sorry with my bad english, when i try find some way to solve it, i only find two post relate but it different with my case — manh3, Mar 16 '23 at 09:46
You found a post with a similar question, then you took some code from that post and executed it. You need to post here the code you are executing, the problems that is giving you and how the results are different from the expected ones. We need the exact code you are executing so we can see what is the problem with that particular code. @Stef has provided you a good algorithm for you to try in case the linked ones don't work. — Sembei Norimaki, Mar 16 '23 at 09:47
@SembeiNorimaki ok, i think we can skip those two posts. My mistake when link two post different with my case. i want to sort but even numbers are only put in place where there are already even numbers and the same goes for odd numbers. Algorithm of Stef is what i want — manh3, Mar 16 '23 at 09:51
@SembeiNorimaki The two linked questions are actually about different problems. I don't think trying random code is a good idea. — Stef, Mar 16 '23 at 09:51
Does this answer your question? [How to list out odd and even numbers from a list of numbers using if and else statement under list comprehensions in Python?](https://stackoverflow.com/questions/56890791/how-to-list-out-odd-and-even-numbers-from-a-list-of-numbers-using-if-and-else-st) — Robin De Schepper, Mar 16 '23 at 10:32

Stef · Accepted Answer · 2023-03-16T10:18:37.017

I suggest the following algorithm:

(1) Build a list with the odd values, and a list with the even values;
(2) Sort these two lists separately;
(3) Build a new list by iterating on the original list, picking the next even number when the original list has an even number, picking the next odd number when the original list has an odd number.

I encourage you to try implementing it yourself first, without looking at the code below.

def sorted_oddsevens(seq):
    # (1) Build a list with the odd values, and a list with the even values
    evens = [x for x in seq if x % 2 == 0]
    odds = [x for x in seq if x % 2 != 0]
    # (2) Sort these two lists separately
    evens.sort()
    odds.sort()
    # (3) Build a new list by iterating on the original list
    #     picking the next even number when the original list has an even number
    #     picking the next odd number when the original list has an odd number
    iter_evens = iter(evens)
    iter_odds = iter(odds)
    return [(next(iter_evens) if x % 2 == 0 else next(iter_odds)) for x in seq]

sortedlist = sorted_oddsevens([5, 6, 4, 7, 11, 14, 12, 1, 3])
print(sortedlist)
# [1, 4, 6, 3, 5, 12, 14, 7, 11]

The compact version, doing steps 1 and 2 on the same line:

def sorted_oddsevens(seq):
    iter_evens = iter(sorted(x for x in seq if x % 2 == 0))
    iter_odds = iter(sorted(x for x in seq if x % 2 != 0))
    return [(next(iter_evens) if x % 2 == 0 else next(iter_odds)) for x in seq]

A different version by Tomerikoo, inverting steps 1 and 2:

def sorted_oddsevens(seq):
    sorted_seq = sorted(seq)
    evens = (x for x in sorted_seq if x % 2 == 0)
    odds = (x for x in sorted_seq if x % 2 != 0)
    return [(next(evens) if x % 2 == 0 else next(odds)) for x in seq]

Berni · Answer 2 · 2023-03-16T10:01:44.223

i do this, i think it could be done properly but it works:

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]
odd = [i if i % 2 == 1 else " " for i in s]
even = [i if i % 2 == 0 else " " for i in s]


print(odd)
print(even)


for i in range(len(odd)):
    for j in range(i + 1, len(odd)):
        tmp = odd[j]
        if tmp != " " and odd[i] != " " and odd[i] > tmp:
            odd[j] = odd[i]
            odd[i] = tmp

for i in range(len(even)):
    for j in range(i + 1, len(even)):
        tmp = even[j]
        if tmp != " " and even[i] != " " and even[i] > tmp:
            even[j] = even[i]
            even[i] = tmp

print(odd)
print(even)

final = [odd[i] if odd[i] != " " else even[i] for i in range(len(odd))]

print(final)

first i separate odd / even number, but keeping initial index in lists. After that i sort the list, still keeping inital index.

Finally, i could merge the two sorted lists.

Hope it will help you

Output: [1, 4, 6, 3, 5, 12, 14, 7, 11]

Edit: Another option is to make 2 consecutive sort: The first one on odd numbers, second one on even:

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]


for i in range(len(s)):
    for j in range(i + 1, len(s)):
        tmp = s[j]
        if tmp % 2 == 1 and s[i] % 2 == 1 and s[i] > tmp:
            s[j] = s[i]
            s[i] = tmp

for i in range(len(s)):
    for j in range(i + 1, len(s)):
        tmp = s[j]
        if tmp % 2 == 0 and s[i] % 2 == 0 and s[i] > tmp:
            s[j] = s[i]
            s[i] = tmp


print(s)

score 1 · Answer 3 · edited Mar 16 '23 at 19:15

I think the way you want to sort can be done with the help of this function.

def sorting_even_odd(s):
    pos_list = []
    evens = []
    odds = []
    for i in range(len(s)):
        if s[i]%2==0:
            pos_list.append(0)
            evens.append(s[i])
        else:
            pos_list.append(1)
            odds.append(s[i])

    evens.sort()
    odds.sort()
    e=0
    o=0
    for i in range(len(s)):
        if pos_list[i]==0:
            s[i]=evens[e]
            e=e+1
        else:
            s[i]=odds[o]
            o+=1

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]
sorting_even_odd(s)
print(s)

output -> [1, 4, 6, 3, 5, 12, 14, 7, 11]

Kelly Bundy · Answer 4 · 2023-03-17T16:17:13.040

One pass to separate, one pass to bring back together:

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]

a = [], []
for x in s:
    a[x%2].append(x)
a = [b.sort() or iter(b) for b in a]
s = [next(a[x%2]) for x in s]

print(s)

Or using one of my favorite sorting algorithms:

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]

for i in range(len(s)):
    for j in range(len(s)):
        if s[i] < s[j] and s[i]%2 == s[j]%2:
            s[i], s[j] = s[j], s[i]

print(s)

Or a funky more-itertools solution, first splitting at the even numbers and sorting them, then doing the same with the odds:

from more_itertools import split_at, flatten

s = [5, 6, 4, 7, 11, 14, 12, 1, 3]

for i in range(2):
    s = list(split_at(s, lambda x: x%2 == i, keep_separator=True))
    s[1::2] = sorted(s[1::2])
    s = list(flatten(s))

print(s)

gog · Answer 5 · 2023-03-16T10:15:23.890

You can try a variation of selection sort so that we only consider elements with the same parity when looking for a minimal element:

a = [5, 6, 4, 7, 11, 14, 12, 1, 3]
N = len(a)

for m in range(N):
    bit = a[m] & 1

    k = m
    for j in range(m + 1, N):
        if a[j] & 1 == bit and a[j] < a[k]:
            k = j

    a[m], a[k] = a[k], a[m]

Another, faster, but less memory-efficient idea is to

sort the list
separate evens and odds from the sorted list
for each item in the original list, add an element from evens or odds

buf = [[], []]
res = []

for x in sorted(a):
    buf[x % 2].append(x)

for x in a:
    res.append(buf[x % 2].pop(0))

Ah, I overlooked your second solution. The pop(0) makes it quadratic, though. If you collect over `reversed(sorted(a))`, you could do pop(). — Kelly Bundy, Mar 17 '23 at 14:10

How to sort even/odd numbers separately in a list?

5 Answers5