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
Advertisement
Answer
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}',
*(' %3d ms' % (t * 1e3) for t in times[sort]))