Как создать собственную функцию сортировки со сложной логикой?

Question

Я пытаюсь отсортировать список объектов на основе некоторой нетривиальной логики сравнения, но мне сложно, потому что в Python пользовательская функция сортировки принимает только 1 аргумент. Например, в Java функция сортировки имеет ссылки на object1 и object2, что упрощает их сравнение.

class Point:
    def __init__(self, char, num, pt_type):
        self.char = char
        self.num = num
        self.pt_type = pt_type  # 'start' or 'end'

    def __str__(self):
        return str([self.char, str(self.num), self.pt_type])
    def __repr__(self):
        return str(self)

arr = [Point('C', 1, 'end'), Point('C', 9, 'start'),
       Point('B', 7, 'end'), Point('B', 2, 'end'),
       Point('A', 3, 'start'), Point('A', 6, 'start')]

def my_sort(key):
    # Sort by first element (letter). 
    #
    # If the letter is the same, fallback to sorting by the
    # 2nd element (number), but the logic of this comparison depends
    # on `pt_type`:
    #   -If Point1 and Point2 both have type 'start', pick the higher number first.
    #   -If Point1 and Point2 both have type 'end', pick the lower number first.
    #   -If Point1 and Point2 have different types, pick the 'start' type first.
    return key.char

print(sorted(arr, key=my_sort))

Ожидаемый отсортированный заказ должен быть:

[Point('A', 6, 'start'), Point('A', 3, 'start')
 Point('B', 2, 'end'), Point('B', 7, 'end'),
 Point('C', 9, 'start'), Point('C', 1, 'end')]

Я не знаю, как даже начать реализовывать требуемую логику, поэтому я был бы благодарен за толчок в правильном направлении.

Answer 1

Я бы использовал следующую key функцию:

class Point:
    def __init__(self, char, num, pt_type):
        self.char = char
        self.num = num
        self.pt_type = pt_type  # 'start' or 'end'

    def __str__(self):
        return str([self.char, str(self.num), self.pt_type])

    def __repr__(self):
        return str(self)


arr = [Point('C', 1, 'end'), Point('C', 9, 'start'),
       Point('B', 7, 'end'), Point('B', 2, 'end'),
       Point('A', 3, 'start'), Point('A', 6, 'start')]


def key(p):
    return p.char, int(p.pt_type != 'start'), p.num if p.pt_type == 'end' else -1 * p.num


result = sorted(arr, key=key)
print(result)

выход

[['A', '6', 'start'], ['A', '3', 'start'], ['B', '2', 'end'], ['B', '7', 'end'], ['C', '9', 'start'], ['C', '1', 'end']]

Функция key создает кортеж для использования в качестве ключа, первый элемент - буква, второй элемент - 0, если узел имеет тип 'start', 1, если он имеет тип 'end'. Последний элемент является отрицательным, если он имеет тип «начало», и положительным, если он имеет тип «конец».

Answer 2

Вы можете сделать сортировку свойством своего класса, затем использовать sorted. Преимущество этого метода: без дополнительных усилий вы можете сравнивать объекты друг с другом с помощью таких операторов сравнения, как >, <, ==.

Укажите __eq__ и __lt__ методы

Как минимум, вы должны указать __eq__ и __lt__ методы:

class Point:
    def __init__(self, char, num, pt_type):
        self.char = char
        self.num = num
        self.pt_type = pt_type  # 'start' or 'end'

    def __str__(self):
        return str([self.char, str(self.num), self.pt_type])

    def __repr__(self):
        return str(self)

    def __eq__(self, other):
        return self.char == other.char and self.pt_type == other.pt_type

    def __lt__(self, other):
        if self.char != other.char:
            return self.char < other.char
        if (self.pt_type == 'start') and (other.pt_type == 'start'):
            return self.num > other.num
        elif (self.pt_type == 'end') and (other.pt_type == 'end'):
            return self.num < other.num
        else:
            return self.pt_type == 'start'

Добавление других методов сравнения, таких как __gt__, __ge__ и т. Д., Может быть упрощено с помощью functools.total_ordering:

from functools import total_ordering

@total_ordering
class Point:
    def __init__(self, ...):
        # initialization logic
    def __eq__(self, other):
        # as before
    def __lt__(self, other):
        # as before

Пример

arr = [Point('C', 1, 'end'), Point('C', 9, 'start'),
       Point('B', 7, 'end'), Point('B', 2, 'end'),
       Point('A', 3, 'start'), Point('A', 6, 'start')]

print(sorted(arr))

[['A', '6', 'start'],
 ['A', '3', 'start'],
 ['B', '2', 'end'],
 ['B', '7', 'end'],
 ['C', '9', 'start'],
 ['C', '1', 'end']]

Answer 3

Вы хотите использовать аргумент cmp для sorted, который принимает функцию сравнения из 2 аргументов: https://docs.python.org/2/library/functions.html#sorted

Для справки: функция key будет вычислять производное значение для каждого сортируемого элемента и сортировать в соответствии с этим значением, например, отсортировать список пар по второму значению в паре, которое вы можете сделать: sorted(items, key=lambda x: x[1])