Как реализовать сортировку по определенному атрибуту объекта в пользовательской функции сортировки?

Question

Я пытаюсь сделать быструю сортировку списка объектов по одному из атрибутов объекта. (например, объект 2D точки, сортировка по x или y)

У меня есть домашняя работа, чтобы написать quicksort и heapsort, а затем использовать ее в списке 2d точек.

QuickSort:

def quick_sort(a):  # interface
    quick_sort2(a, 0, len(a)-1)


def quick_sort2(a, low, high):  # split list
    if low < high:  # stop call for list of 1
        split = partition(a, low, high)  # split index
        quick_sort2(a, low, split-1)  # left side
        quick_sort2(a, split + 1, high)  # right side


def partition(a, low, high):  # setting the pivot
    pivot_idx = get_pivot(a, low, high)
    pivot_val = a[pivot_idx]
    a[pivot_idx], a[low] = a[low], a[pivot_idx]  # swap
    border = low

    for i in range(low, high+1):  # comparing to pivot
        if a[i] < pivot_val:
            border += 1
            a[i], a[border] = a[border], a[i]
    a[low], a[border] = a[border], a[low]
    return border


def get_pivot(a, low, high):  # selecting best pivot
    middle = (high + low) // 2
    pivot = high
    if a[low] < a[middle]:
        if a[middle] < a[high]:
            pivot = middle
    elif a[low] < a[high]:
        pivot = low
    return pivot

Point2D класс:

class Point2D:
    def __init__(self, id_initial: int, x_initial: float, y_initial: float):

        self.id = id_initial
        self.x = x_initial
        self.y = y_initial

    @property
    def id(self):
        return self._id

    @id.setter
    def id(self, value):
        self._id = value

    @property
    def x(self):
        return self._x

    @x.setter
    def x(self, value):
        self._x = value

    @property
    def y(self):
        return self._y

    @y.setter
    def y(self, value):
        self._y = value

    def __repr__(self):
        return repr((self._id, self._x, self._y))

эта строка будет работать для sorted ():

QuickSort.quick_sort(mylist, key=lambda point: point.x)

Я пытался найти решение для моей пользовательской функции сортировки, но безуспешно, пожалуйста, помогите мне ...

Код для сортировки ():

mylist = []
for i in range(0, 3):
    x = random.randint(1, 10)
    y = random.randint(1, 10)
    mylist.append(Geometry.Point2D(i, x, y))

for point in mylist:
    print("P", point.id+1, "(", point.x, ",", point.y, ") ")

mylist2 = sorted(mylist, key=lambda point2d: point2d.x)

for point in mylist2:
    print("P", point.id+1, "(", point.x, ",", point.y, ") ")

Выход:

P 1 ( 1 , 6 ) 
P 2 ( 9 , 9 ) 
P 3 ( 3 , 2 ) 
P 1 ( 1 , 6 ) 
P 3 ( 3 , 2 ) 
P 2 ( 9 , 9 )

Answer 1

Если вы хотите использовать key, вам придется соответствующим образом изменить свои функции, добавив аргумент key и используя его каждый раз, когда вы сравниваете элементы списка (например, a[middle] < a[high] должно быть key(a[middle]) < key(a[high]) или key(a[i]) < key(pivot_val) и т. Д.):

Как пример:

def default_key(x): # default key: use the value as-is
    return x

def quick_sort(a, key=default_key):  # accept keyword argument `key`
    quick_sort2(a, 0, len(a)-1, key=key) # pass on the key

def quick_sort2(a, low, high, key=default_key):
    if low < high:
        split = partition(a, low, high, key=key)  # pass the key
        quick_sort2(a, low, split-1, key=key)
        quick_sort2(a, split + 1, high, key=key)


def partition(a, low, high, key):
    pivot_idx = get_pivot(a, low, high, key=key)
    ...
        if key(a[i]) < key(pivot_val):
            ...


def get_pivot(a, low, high, key=default_key):  # selecting best pivot
...
    if key(a[low]) < key(a[middle]):
        if key(a[middle]) < key(a[high]):
...

Answer 2

Вам нужно добавить компаратор в ваш класс Poin2D def __lt__(self,other). Таким образом, оператор < в getpivot() знает, как сравнивать два экземпляра класса Point2D.

class Point2D:
    def __init__(self, id_initial: int, x_initial: float, y_initial: float):
        self.id = id_initial
        self.x = x_initial
        self.y = y_initial

    def __lt__(self, other):
        return self.x < other.x

[...]

После этого вы можете вызывать свою функцию quicksort() следующим образом:

mylist = []
for i in range(0, 5):
    x = random.randint(1, 10)
    y = random.randint(1, 10)
    mylist.append(Point2D(i, x, y))

for point in mylist:
    print("P", point.id + 1, "(", point.x, ",", point.y, ") ")

quick_sort(mylist)

print('x' * 20)
for point in mylist:
    print("P", point.id + 1, "(", point.x, ",", point.y, ") ")