Sort a list of integers on absolute values with higher precedence positive number

Viewed 143

How do I sort a list of integers based on their absolute values such that the positive number gets a higher precedence -

Sample Input

lst = [1, -3, 3, -3, 12, 10]

Expected Output

[1, 3, -3, -3, 10, 12]

I am able to do it right now with a code like this, but I am bothered by that arbitrary 0.1 in the function and wonder if there is a cleaner way

My code

sorted(lst, key=lambda x: abs(x) if x >= 0 else abs(x) + 0.1)
# [1, 3, -3, -3, 10, 12]
3 Answers

Another solution is having a tuple as a sorting key:

sorted(lst, key=lambda x: (abs(x), x < 0))

To understand it better:

 1 ~ (1, False)  ~ (1, 0)
-3 ~ (3, True)   ~ (3, 1)
 3 ~ (3, False)  ~ (3, 0)
-3 ~ (3, True)   ~ (3, 1)
12 ~ (12, False) ~ (12, 0)
10 ~ (10, False) ~ (10, 0)

Create a custom comparator function which returns a tuple of size 2. The first value of the tuple is for absolute value and the second value is for ordering negative and positive values with the same absolute value.

sorted(lst, key=lambda x: (abs(x), -x))
# [1, 3, -3, -3, 10, 12]

For each value in the list values compared would be:

1  -> (1, -1)
3  -> (3, -3)
-3 -> (3,  3)
10 -> (10, -10)
12 -> (12, -12)

This way positive values are pushed to the beginning and negatives values to the end in each group.

As often the case, two simple sorts are probably more efficient here than one sort using tuples:

lst.sort(reverse=True)
lst.sort(key=abs)

This takes advantage of the sort function being stable, so the order from the first sort is preserved to break ties in the second sort. Also see Python's Sorting HOW TO about this technique.

Btw yours would be a bit shorter and faster without the unnecessary abs (you already know the sign):

sorted(lst, key=lambda x: x if x >= 0 else 0.5 - x)

Also, the sort function is optimized for cases where all values have the same type, so if we simply add 0.0 to non-negative x to make it a float as well, this optimization gets used. Btw adding a single . to Jupri's currently deleted answer fixes it and then it's quite neat and similarly fast.

Benchmark for something like your "few 100 elements long" lists and also longer lists:

500 random integers from -500 to 500
 82.9 μs ± 0.2 μs  Kelly
113.6 μs ± 0.5 μs  original_mod2
117.5 μs ± 0.4 μs  Jupri
191.7 μs ± 0.3 μs  Yevhen
196.2 μs ± 0.6 μs  Ch3ster
215.0 μs ± 0.7 μs  original_mod1
233.5 μs ± 0.5 μs  original

100,000 random integers from -100,000 to 100,000
 39.4 ms ± 0.1 ms  Kelly
 40.2 ms ± 0.4 ms  original_mod2
 41.6 ms ± 0.3 ms  Jupri
 90.2 ms ± 0.5 ms  original_mod1
 94.9 ms ± 0.4 ms  original
115.9 ms ± 2.7 ms  Yevhen
131.5 ms ± 2.6 ms  Ch3ster

Benchmark code (Try it online!):

def original(lst):
    return sorted(lst, key=lambda x: abs(x) if x >= 0 else abs(x) + 0.1)

def original_mod1(lst):
    return sorted(lst, key=lambda x: x if x >= 0 else 0.5-x)

def original_mod2(lst):
    return sorted(lst, key=lambda x: x+0.0 if x >= 0 else 0.5-x)

def Kelly(lst):
    lst = sorted(lst, reverse=True)
    lst.sort(key=abs)
    return lst

def Yevhen(lst):
    return sorted(lst, key=lambda x: (abs(x), x < 0))

def Ch3ster(lst):
    return sorted(lst, key=lambda x: (abs(x), -x))

def Jupri(lst):
    return sorted(lst, key=lambda x: abs(x-.1))

funcs = [original, original_mod1, original_mod2, Kelly, Yevhen, Ch3ster, Jupri]

import random
from timeit import default_timer as timer
from statistics import mean, stdev

def test(n, repeats, unit):
    print(f'{n:,} random integers from {-n:,} to {n:,}')

    times = {func: [] for func in funcs}
    def stats(func):
        ts = sorted(times[func])[:3]
        mn = mean(ts)
        sd = stdev(ts)
        return f'{mn*1e3:5.1f} ms ± {sd*1e3:3.1f} ms ' if unit == 'ms' else f'{mn*1e6:5.1f} μs ± {sd*1e6:3.1f} μs '

    for _ in range(15):
        lst = random.choices(range(-n, n+1), k=n)
        expect = original(lst)
        random.shuffle(funcs)
        for func in funcs:
            t = 0
            for _ in range(repeats):
                t0 = timer()
                result = func(lst)
                t += (timer() - t0) / repeats
                assert result == expect
                del result
            times[func].append(t)

    for func in sorted(funcs, key=stats):
        print(stats(func), func.__name__)
    print()

test(500, 500, 'μs')
test(10**5, 1, 'ms')
Related