Sort a number by its digits-CodePudding

I have to sort a vector of integers (all integers have the same length). Integers with the same first digit must be sorted in relation to the second digits, and numbers with the same: first and second digits are sorted by third digit etc. Also, the subsequent digits are sorted alternately (once ascending and once descending)

So when I have lis = [137, 944, 972, 978, 986], I should get sorted_lis = [137, 986, 972, 978, 944]

I know how to sort by selecting digit (a)

lis.sort(key=lambda x: int(str(x)[a]))

I've tried using insertion sort, (since I have to use a stable sorting algorithm)

def insertion_sort(list):
    for i in range(len(list)):
        key = list[i]
        j = i-1
        while j >= 0 and key < list[j]:
            list[j 1] = list[j]
            j -= 1
        list[j 1] = key

    return list

CodePudding user response：

You can define a key as follows:

lis = [137, 944, 972, 978, 986]

def alternate_digits(x):
    return [-d if i % 2 else d for i, d in enumerate(map(int, str(x)))]

output = sorted(lis, key=alternate_digits)
print(output) # [137, 986, 972, 978, 944]

The key alternate_digits, for example, converts 12345 into [1, -2, 3, -4, 5].

CodePudding user response：

Solution 1: multisort with ints

A fun multisort taking advantage of list.sort being stable (as explained in that sorting howto section):

lis = [137, 944, 972, 978, 986]

pow10 = 1
while pow10 <= lis[0]:
    lis.reverse()
    lis.sort(key=lambda x: x // pow10 % 10)
    pow10 *= 10

print(lis)  # [137, 986, 972, 978, 944]

This first sorts by last digit, then by second-to-last, etc, until sorting by first digit. And reverse between the sorts.

Solution 2: "negate" every second digit

Another method, turning for example 1234 into 1735 (every second digit gets "negated", i.e., subtracted from 9):

def negate_every_second_digit(x):
    result = 0
    pow10 = 1
    while x:
        result = (x % 10   1) * pow10 - (result   1)
        pow10 *= 10
        x //= 10
    return result
lis.sort(key=negate_every_second_digit)

Solution 3: multisort with characters

Similar to your attempt, but converting to strings only once (at the expense of once converting back to ints at the end):

lis[:] = map(str, lis)
for i in reversed(range(len(lis[0]))):
    lis.reverse()
    lis.sort(key=itemgetter(i))
lis[:] = map(int, lis)

Your solution, completed

Like you said you already know how to sort by a certain digit. You just need to do that for each:

digits = len(str(lis[0]))
for a in reversed(range(digits)):
    lis.sort(key=lambda x: int(str(x)[a]),
             reverse=a % 2)

Benchmark

Benchmark with 100,000 random six-digit numbers:

Kelly1  201 ms  192 ms  196 ms
Kelly2  160 ms  154 ms  157 ms
Kelly3  248 ms  237 ms  243 ms
j1_lee  394 ms  396 ms  404 ms
OSA     409 ms  405 ms  419 ms

Benchmark code (Try it online!):

def Kelly1(lis):
    pow10 = 1
    while pow10 <= lis[0]:
        lis.reverse()
        lis.sort(key=lambda x: x // pow10 % 10)
        pow10 *= 10

def Kelly2(lis):
    def negate_every_second_digit(x):
        result = 0
        pow10 = 1
        while x:
            result = (x % 10   1) * pow10 - (result   1)
            pow10 *= 10
            x //= 10
        return result
    lis.sort(key=negate_every_second_digit)

def Kelly3(lis):
    lis[:] = map(str, lis)
    for i in reversed(range(len(lis[0]))):
        lis.reverse()
        lis.sort(key=itemgetter(i))
    lis[:] = map(int, lis)

# Modified by Kelly to sort in-place, as the question and my solutions do
def j1_lee(lis):
    def alternate_digits(x):
        return [-d if i % 2 else d for i, d in enumerate(map(int, str(x)))]
    lis.sort(key=alternate_digits)

# The question's attempt, completed by Kelly.
def OSA(lis):
    digits = len(str(lis[0]))
    for a in reversed(range(digits)):
        lis.sort(key=lambda x: int(str(x)[a]),
                 reverse=a % 2)

sorts = Kelly1, Kelly2, Kelly3, j1_lee, OSA

from timeit import timeit
import random
from operator import itemgetter

n = 100_000
digits = 6

times = {sort: [] for sort in sorts}
for _ in range(3):
    lis = random.choices(range(10**(digits-1), 10**digits), k=n)
    expect = None
    for sort in sorts:
        copy = lis.copy()
        time = timeit(lambda: sort(copy), number=1)
        times[sort].append(time)
        if expect is None:
            expect = copy
        else:
            assert copy == expect
for sort in sorts:
    print(f'{sort.__name__:6}',
          *(' = ms' % (t * 1e3) for t in times[sort]))