How can I get 2.x-like sorting behaviour in Python 3.x?

by

Stupid idea: make a first pass to divide all the different items in groups that can be compared between each other, sort the individual groups and finally concatenate them. I assume that an item is comparable to all members of a group, if it is comparable with the first member of a group. Something like this (Python3):

import itertools

def python2sort(x):
    it = iter(x)
    groups = [[next(it)]]
    for item in it:
        for group in groups:
            try:
                item < group[0]  # exception if not comparable
                group.append(item)
                break
            except TypeError:
                continue
        else:  # did not break, make new group
            groups.append([item])
    print(groups)  # for debugging
    return itertools.chain.from_iterable(sorted(group) for group in groups)

This will have quadratic running time in the pathetic case that none of the items are comparable, but I guess the only way to know that for sure is to check all possible combinations. See the quadratic behavior as a deserved punishment for anyone trying to sort a long list of unsortable items, like complex numbers. In a more common case of a mix of some strings and some integers, the speed should be similar to the speed of a normal sort. Quick test:

In [19]: x = [0, 'one', 2.3, 'four', -5, 1j, 2j,  -5.5, 13 , 15.3, 'aa', 'zz']

In [20]: list(python2sort(x))
[[0, 2.3, -5, -5.5, 13, 15.3], ['one', 'four', 'aa', 'zz'], [1j], [2j]]
Out[20]: [-5.5, -5, 0, 2.3, 13, 15.3, 'aa', 'four', 'one', 'zz', 1j, 2j]

It seems to be a ‘stable sort’ as well, since the groups are formed in the order the incomparable items are encountered.

More Related Contents:

  1. What arguments does Python sort() function have?
  2. What is the best way to remove accents (normalize) in a Python unicode string?
  3. How can I concatenate str and int objects?
  4. How to return dictionary keys as a list in Python?
  5. How to run multiple Python versions on Windows
  6. Nested arguments not compiling
  7. Combine several images horizontally with Python
  8. Django TemplateDoesNotExist?
  9. How to use a custom comparison function in Python 3?
  10. Why can’t I use the method __cmp__ in Python 3 as for Python 2?
  11. How dangerous is setting self.__class__ to something else?
  12. How do you use subprocess.check_output() in Python?
  13. Convert float to string in positional format (without scientific notation and false precision)
  14. Sorting by absolute value without changing to absolute value
  15. What is a “callable” in Python?
  16. Is super() broken in Python-2.x? [closed]
  17. Sort a list of tuples depending on two elements [duplicate]
  18. How to sort a list of strings in reverse order without using reverse=True parameter?
  19. Nested lambda statements when sorting lists
  20. Mergesort with Python
  21. How to add an element to the beginning of an OrderedDict?
  22. How to run Spyder in virtual environment?
  23. Scrolling to element using webdriver?
  24. Dangers of sys.setdefaultencoding(‘utf-8’)
  25. List sorting with multiple attributes and mixed order
  26. How to make unicode string with python3
  27. How to accomplish relative import in python
  28. Finding the nearest value and return the index of array in Python
  29. Pythonic way to sorting list of namedtuples by field name
  30. Fast string array – Cython

Leave a Comment