Sorting a list: numbers in ascending, letters in descending

Question

This question is actually adapted from one previously asked by Mat.S (image). Although it was deleted, I thought it was a good question, so I am reposting it with clearer requirements and my own solution.

---

Given a list of letters and numbers, say

['a', 2, 'b', 1, 'c', 3]

The requirement is to sort the numbers in ascending and letters in descending, without altering the relative position of letters and numbers. By this I mean if the unsorted list is:

[L, D, L, L, D]    # L -> letter; # D -> digit 

Then, the sorted list must also be

[L, D, L, L, D] 

1. The letters and digits do not necessarily alternate in a regular pattern - they can appear in any arbitrary order

2. After sorting - numbers are ascending, letters are descending.

So for the example above the output is

['c', 1, 'b', 2, 'a', 3]

Another example:

 In[]: [5, 'a', 'x', 3, 6, 'b']
Out[]: [3, 'x', 'b', 5, 6, 'a']

What would be a good way to do this?

Answer 1

Here is an optimized approach using defaultdict() and bisect():

In [14]: lst = [5, 'a', 'x', 3, 6, 'b']
In [15]: from collections import defaultdict       
In [16]: import bisect

In [17]: def use_dict_with_bisect(lst):
             d = defaultdict(list)
             for i in lst:
                 bisect.insort(d[type(i)], i)
             # since bisect doesn't accept key we need to reverse the sorted integers
             d[int].sort(reverse=True)
             return [d[type(i)].pop() for i in lst]
   .....:  

Demo :

In [18]: lst
Out[18]: [5, 'a', 'x', 3, 6, 'b']

In [19]: use_dict_with_bisect(lst)
Out[19]: [3, 'x', 'b', 5, 6, 'a']

In case you're dealing with larger lists it's more optimized to drop using bisect which has a complexity about O(n²)and just use python built-in sort() function with Nlog(n) complexity.

In [26]: def use_dict(lst):
             d = defaultdict(list)
             for i in lst:
                 d[type(i)].append(i)
             d[int].sort(reverse=True); d[str].sort()
             return [d[type(i)].pop() for i in lst]

Benchmark with other answers that shows the latest approach using dict and built-in sort is almost 1ms faster than the other approaches:

In [29]: def use_sorted1(lst):
              letters = sorted(let for let in lst if isinstance(let,str))
              numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True)
              return [letters.pop() if isinstance(elt,str) else numbers.pop() for elt in lst]
   .....: 

In [31]: def use_sorted2(lst):
              f1 = iter(sorted(filter(lambda x: isinstance(x, str), lst), reverse=True))
              f2 = iter(sorted(filter(lambda x: not isinstance(x, str), lst)))
              return [next(f1) if isinstance(x, str) else next(f2) for x in lst]
   .....: 

In [32]: %timeit use_sorted1(lst * 1000)
100 loops, best of 3: 3.05 ms per loop

In [33]: %timeit use_sorted2(lst * 1000)
100 loops, best of 3: 3.63 ms per loop

In [34]: %timeit use_dict(lst * 1000)   # <-- WINNER
100 loops, best of 3: 2.15 ms per loop

Here is a benchmark that shows how using bisect can slow down the process for long lists:

In [37]: %timeit use_dict_with_bisect(lst * 1000)
100 loops, best of 3: 4.46 ms per loop

Answer 2

Look ma, no iter:

lst = ['a', 2, 'b', 1, 'c', 3]
letters = sorted(let for let in lst if isinstance(let,str))
numbers = sorted((num for num in lst if not isinstance(num,str)), reverse = True)
lst = [(letters if isinstance(elt,str) else numbers).pop()for elt in lst]

I'm looking for a way to turn this into a (horrible) one-liner, but no luck so far - suggestions welcome!