nat-sorts/nat_sort.py

# Copyright (c) 2013, Lily Carpenter
# All rights reserved.
#
# Redistribution and use in source and binary forms, with or without modification,
# are permitted provided that the following conditions are met:
#
#   Redistributions of source code must retain the above copyright notice, this
#   list of conditions and the following disclaimer.
#
#   Redistributions in binary form must reproduce the above copyright notice, this
#   list of conditions and the following disclaimer in the documentation and/or
#   other materials provided with the distribution.
#
#   Neither the name of Lily Carpenter nor the names of its
#   contributors may be used to endorse or promote products derived from
#   this software without specific prior written permission.
#
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
# WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
# DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR
# ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
# (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
# LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
# ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
# SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

from itertools import groupby
from natsort import natsorted

def is_int(i):
    return i.isdigit()

str_join = "".join

def nat_sort(strings):
    to_be_sorted = list()
    sorted_list = list()
    for list_elem in strings:
        nums = []
        chars = []

        for group_key, elems in groupby(list_elem, key=is_int):
            if group_key:
                nums = list(elems)
            else:
                chars = list(elems)

        to_be_sorted.append([str_join(chars),int(str_join(nums))])

    to_be_sorted.sort()

    for elems in to_be_sorted:
        elems[1] = str(elems[1])
        sorted_list.append(str_join(elems))

    return sorted_list


to_sort = [str_join(["eth",str(i)]) for i in reversed(xrange(100000))]

print nat_sort(to_sort)[-1]
#print natsorted(to_sort)[-1]