Sorting strings with certain restrictions

Question

I want to sort a string which contains words and integers with the restriction that if the nth element in the list is an integer it must remain an integer and if it is a word, it must remain a word.

Currently, what I am doing is splitting the input string on spaces, putting the words and integers into their own lists, sorting them appropriately by mapping to a different list, and then injecting the sorted words/integers back into the original input list.

I am trying to find comments on improve the code or looking for a different approach to the problem if there is a better one. Does anyone have any comments?

http://ideone.com/X2pPfg

justWords   = {}
words       = []

justNums    = {}
nums        = []

# Check if value in the input is an integer or a word
def is_number(s):
    try:
        float(s)
        return True
    except ValueError:
        return False

# Replace the values in the dictionary with the correctly sorted words/integers       
def go_through(theDict, theList):
    counter = 0
    for k,v in theDict.iteritems():
        theDict[k]   = theList[counter]
        counter      = counter + 1
    return theDict

# Replace the values in the original input 
 # list with correctly sorted values of the word/int dicts
def inject(theDict, theList):
    for k,v in theDict.iteritems():
        theList[k] = v
    return theList

if __name__ == "__main__":

    splitInput  = (raw_input("")).split()

    # Sort the words and numbers into their own lists as tuples
    for i,j in enumerate(splitInput):
        if is_number(j):
            justNums[i]  = j
            nums.append(j)
        elif not is_number(j):
            justWords[i] = j
            words.append(j)

    print("%s\n%s\n" % (justWords, justNums))

    words = sorted(words)
    nums  = sorted(nums)

    print("%s\n%s\n" % (words, nums))

    # Replace the values in the dictionaries with the values in the sorted list
    justWords = go_through(justWords, words)
    justNums  = go_through(justNums, nums)

    print("%s\n%s\n" % (justWords, justNums))

    # Inject correctly maped sorted words into the original list
    splitInput = inject(justWords, splitInput)
    splitInput = inject(justNums, splitInput)

    print("%s" % (' '.join(splitInput)))

Input:

car truck 8 4 bus 6 1

Output:

{0: 'car', 1: 'truck', 4: 'bus'}
{2: '8', 3: '4', 5: '6', 6: '1'}

['bus', 'car', 'truck']
['1', '4', '6', '8']

{0: 'bus', 1: 'car', 4: 'truck'}
{2: '1', 3: '4', 5: '6', 6: '8'}

bus car 1 4 truck 6 8

Answer 1

Numeric vs. lexicographic sort

Given this input: 8 4 6 1 12 55,
the output will be 1 12 4 55 6 8.

The question did not explicitly state so, but in the absence of specific instructions, I would have expected a numeric sort to be more appropriate for the numbers.

The root cause of the bug (if you do consider it to be a bug, that is) is that you detect whether each word looks like it could be a float, but you don't actually convert it to a float. Therefore, the numbers are sorted as if they were strings.

I'm going to assume that numeric sorting is desired.

Style

Whenever you start with an empty list or dict, then populate it using a loop, consider using a list comprehension or dict comprehension instead. Defining a variable "all at once" using a comprehension is more elegant, and possibly faster as well.

It's worth packaging the solution to the problem in a function, rather as freely floating code. I suggest calling the function segregated_sort().

Suggested solution

Here's a much shorter way to write it. Useful techniques include:

• Use list comprehensions and dict comprehensions, as mentioned.
• Use filter() to help build the equivalent of your nums and words. (Here, I've generalized support beyond the two types int and str. Note, however, that float and int would not intermingle with this approach.)
• Use iter() to form a queue of sorted items for each type. Each queue is drained by calling next() on it.

def segregated_sort(input_list):
    """Returns a sorted copy of the input list that maintains the same
    type of data at each index of the output as the type of data at that
    index in the input."""
    types = [type(datum) for datum in input_list]
    sorted_data_by_type = {
        t: iter(sorted(filter(lambda datum: type(datum) == t, input_list)))
        for t in set(types)
    }
    return [next(sorted_data_by_type[t]) for t in types]

def to_int_where_possible(words):
    """Returns a copy of the input list in which any word that can be
    an int is replaced with its int value."""
    def convert(word):
        try:
            return int(word)
        except ValueError:
            return word
    return [convert(word) for word in words]

if __name__ == '__main__':
    split_input = raw_input().split()
    result = segregated_sort(to_int_where_possible(split_input))
    print(' '.join(str(r) for r in result))

Addressing float/int lossiness

To address allow floats and ints to mingle, and to output the strings exactly as they were input, you can convert all numeric values into a Number class.

I've also incorporated @Veedrac's suggestion to abandon filter() in favour of a list comprehension.

class Number:
    def __init__(self, string):
        self.value = float(string)
        self.string = string

    def __str__(self):
        return self.string

    def __cmp__(self, other):
        return cmp(self.value, other.value) or cmp(self.string, other.string)


def segregated_sort(input_list):
    """Returns a sorted copy of the input list that maintains the same
    type of data at each index of the output as the type of data at that
    index in the input."""
    types = [type(datum) for datum in input_list]
    sorted_data_by_type = {
        t: iter(sorted(datum for datum in input_list if type(datum) == t))
        for t in set(types)
    }
    return [next(sorted_data_by_type[t]) for t in types]

def to_number_where_possible(words):
    """Returns a copy of the input list in which any word that looks
    numeric is converted to a Number."""
    def convert(word):
        try:
            return Number(word)
        except ValueError:
            return word
    return [convert(word) for word in words]

if __name__ == '__main__':
    split_input = raw_input().split()
    result = segregated_sort(to_number_where_possible(split_input))
    print(' '.join(str(r) for r in result))

Answer 2

At first glance, the primary problem is that you have too much in the global scope. Ideally, the only globals you have should be constants. This is as simple as

def main():
    justWords   = {}
    words       = []

    justNums    = {}
    nums        = []

    splitInput  = (raw_input("")).split()
    ...

You should then convert your comments where applicable to doc-comments.

def is_number(s):
    """
    Check if value in the input is an integer or a word.
    """

A quick style point:

splitInput  = (raw_input("")).split()

has superfluous brackets and a superfluous argument. It should just be

splitInput  = raw_input().split()

Your use of dictionaries to map makes sense, but it's not obvious how to implement go_through. Your version seems incorrect:

counter = 0
for k,v in theDict.iteritems():
    theDict[k]   = theList[counter]
    counter      = counter + 1
return theDict

This assumes theDict is in order. Although this is true for your examples, it isn't always. For example:

"a a a a 5 a a a 9"

gets "sorted" as

"a a a a 9 a a a 5"

!

This is fixable. The neatest way I can think of is to use an OrderedDict, which fixes insertion order. All you would have to do is

from collections import OrderedDict

justWords = OrderedDict()
justNums  = OrderedDict()

Note that this orders by insertion order, not by keys. So you have to be sure to insert keys in order.

One alternative is, instead of building a dictionary, 200_success's strategy of keeping a list of what list to take from:

# Sort the words and numbers into their own lists as tuples
for i, j in enumerate(splitInput):
    if is_number(j):
        each_is_number.append(True)
        nums.append(j)
    elif not is_number(j):
        each_is_number.append(False)
        words.append(j)

Then when building we take from the appropriate list:

def take(each_is_left, lefts, rights):
    leftidx = rightidx = 0

    for is_left in each_is_left:
        if is_left:
            yield lefts[leftidx]
            leftidx += 1

        else:
            yield rights[rightidx]
            rightidx += 1

When you call words = sorted(words) you should also sort by the transformed value.

Finally, you should consider using decimal.Decimal to store numbers instead of float; Decimals will be lossless for any numbers passed in on the command line.

My attempt would look like:

from __future__ import print_function
from collections import defaultdict, namedtuple
from decimal import Decimal, InvalidOperation

KeyValue = namedtuple("KeyValue", ["key", "value"])

def get_keys(value):
    """
    Get the type and value to sort a string by.
    This will attempt to find a sensible match,
    such as Decimal for numeric strings.

    Currently only returns Decimal or str keys.
    """
    try:
        return Decimal, Decimal(value)
    except InvalidOperation:
        return str, value

def segregated_sort(items):
    """
    Sort items in a list of string, sorting numbers
    separately from other strings. If a string
    had a numeric form before, the same position
    must have a numeric form after being sorted
    by this function, and vice-versa.

    For example, 

        'car', 'truck', '8', '4', 'bus', '6', '0.0000000'

    will get sorted to

        'bus' 'car' '0.0000000' '4' 'truck' '6' '8'
    """
    types = []
    data_by_type = defaultdict(list)

    # Gather items
    for item in items:
        type, key = get_keys(item)
        types.append(type)
        data_by_type[type].append(KeyValue(key, item))

    # Sort each list
    for data in data_by_type.values():
        data.sort(key=lambda kv: kv.key, reverse=True)

    # Return the values
    for type in types:
        yield data_by_type[type].pop().value

def main():
    split_input = raw_input().split()
    result = segregated_sort(split_input)
    print(*result)

main()

Instead of checking if it's a float, I try to make a Decimal from the number. If this suceeds, instead of returing True I return the type I have casted to (Decimal) and the value, which I later sort by. If it fails, the type is str and I sort by the string itself.

Instead of using two lists, words and nums, I have a dictionary mapping types to the sublist.

I used the decorate-undecorate idiom to sort the keys while retaining their string form; namely I sort KeyValue objects of the form KeyValue(key=Decimal('23.3'), value='23.3') by their keys.

I use KeyValue objects instead of tuples to aid comprehension, since namedtuples are so easy to create.

Instead of using iter() and next, I use pop on lists. There isn't much advantage either way, but this seems cleaner to me. I use yield instead of a comprehension because I don't like mutating within a comprehension.

I backport Python 3's print function with from __future__ import print_function. This allows me to just write print(*result). This is basically the same as print " ".join(map(str, result)).

Answer 3

The approach seems right; I don't see how it can be improved algorithmically. However I don't think you need the dictionary or anything to that effect. Given an original list of items, I'd go with something along the lines of a pseudocode

build words and numbers lists out of original
sort them

scan original:
    if it is a number, merge an item from numbers into result
    otherwise, merge an item from words into result
return result