Sort string with integers and words without any change in their positions

Question

Say I have a string a.

a = "12 I have car 8 200 a"

I need to sort this string in such a way that the output should be

8 a car have 12 200 I

ie, Sort the string in such a way that all words are in alphabetical order and all integers are in numerical order. Furthermore, if the nth element in the string is an integer it must remain an integer, and if it is a word it must remain a word.

This is what I tried.

a = "12 I have car 8 200 a"


def is_digit(element_):
    """
    Function to check the item is a number. We can make using of default isdigit function
    but it will not work with negative numbers.
    :param element_:
    :return: is_digit_
    """
    try:
        int(element_)
        is_digit_ = True
    except ValueError:
        is_digit_ = False

    return is_digit_



space_separated = a.split()

integers = [int(i) for i in space_separated if is_digit(i)]
strings = [i for i in space_separated if i.isalpha()]

# sort list in place
integers.sort()
strings.sort(key=str.lower)

# This conversion to iter is to make use of next method.
int_iter = iter(integers)
st_iter = iter(strings)

final = [next(int_iter) if is_digit(element) else next(st_iter) if element.isalpha() else element for element in
         space_separated]

print " ".join(map(str, final))
# 8 a car have 12 200 I

I am getting the right output. But I am using two separate sorting function for sorting integers and the words(which I think is expensive).

Is it possible to do the entire sorting using a single sort function?.

Answer 1

numpy allows to write it more concisely, though doesn't eliminate the need for two separate sorts:

$ python3
Python 3.5.2 (default, Nov 23 2017, 16:37:01) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> from numpy.core.defchararray import isdecimal, lower
>>> 
>>> s = "12 I have car 8 200 a"
>>> 
>>> a = np.array(s.split())
>>> 
>>> integer_mask = isdecimal(a)
>>> string_mask = ~integer_mask
>>> strings = a[string_mask]
>>> 
>>> a[integer_mask] = np.sort(np.int_(a[integer_mask]))
>>> a[string_mask]  = strings[np.argsort(lower(strings))]
>>> 
>>> ' '.join(a)
'8 a car have 12 200 I'

Answer 2

Is it possible to do the entire sorting using a single sort function?.

No, not really.

Why not? It turns out the answer is already in your code.

integers.sort()
strings.sort(key=str.lower)

Notice how you need to sort by two different functions here. The first is an integer sort, the second is a lowercase string sort. We could try something like this:

def get_sort_order(element):
    try:
        value = int(element)
    except ValueError:
        value = element.lower()
    return value

a.sort(key=get_sort_order)

But that doesn't work either; it just gives us the result

['8', '12', '200', 'a', 'car', 'have', 'I']

You could probably force this into a solution, but it isn't going to be pretty.

However, there is another point I'd like to address:

But I am using two separate sorting function for sorting integers and the words (which I think is expensive).

Sorting two distinct lists is basically always going to be faster anyway. To find out why, just look at the time complexity of the two tasks:

Assuming a list of length 1000, exactly half integer and half strings, and a sorting algorithm of O(nlog(n)):

One single sort: 1000 * log(1000) = 3000

Two separate sorts: 2 * (500 * log(500) = ~2699

So sorting the list in a single run is both more difficult to implement and slower!