jumblesort

gistfile1.py

#!/usr/bin/env python

'''
    JumbleSorter.py

    sorts a list of strings and integers, but keeps types at nth element
    in list constant in result.

    only implement for stdin for now, i.e.,

        ./jumblesort.py car truck 8 4 bus 6 1

        > bus car 1 4 truck 6 8
'''
import sys

#TEST = "car truck 8 4 bus 6 1"

class JumbleSorter():
    MAX_LINE_N = 10000

    ''' may want to expand to other types of input,
        i.e. a list that can be sorted in place '''
    def __init__(self, inplace=False):
        self.inplace = inplace
        self.latest_result_cache = []

    def _list_to_line(self, word_list): return ' '.join(word_list)

    @staticmethod
    def is_integer(s):
        return s[1:].isdigit() if (s[0] in ('+', '-')) else s.isdigit()

    ''' main algorithm
        O(nlogn) time and O(n) space, where n is # words
        could alter for constant space with non-inplace. '''
    def _jumble_sort(self, words):
        N = len(words)
        # initialize map of words. True if non-numeric.
        # don't need to store indices in addtional set

        # constant space --  know max words is < 1000
        word_map = [True] * N

        # O(n) space
        integers = []
        alphas = []

        # O(n) time
        for i, word in enumerate(words):
            if self.is_integer(word):
                word_map[i] = False
                integers.append(word)
            else:
                alphas.append(word)

        # O(nlogn) time. sort in reverse so that elements
        # can be popped to amortize space.
        integers.sort(reverse=True)
        alphas.sort(reverse=True)

        for i in range(N):
            if word_map[i]:
                word_map[i] = alphas.pop()
            else:
                word_map[i] = integers.pop()

        self.latest_result_cache = word_map
        return word_map

    def sort(self, words):
        words = self._jumble_sort(words)
        return self._list_to_line(words)

def main():

    worker = JumbleSorter()
    words = sys.argv[1:]
    output = worker.sort(words)
    print output

main()