Сортировка кортежей в LinkedList, сформированном с помощью конструктора класса без использования встроенных функций — Python

Я думаю, что MergeSort может работать лучше всего?

Да, это хороший кандидат.

большинство примеров, которые я вижу в Интернете, добавляются к LinkedList, используя функцию addNode вместе с отдельным классом Node

Вам не нужна функция addNode, так как функция __init__ уже имеет дело с добавлением узлов. Ваша работа будет заключаться в том, чтобы перемонтировать существующие узлы, изменив их tail ссылки.

Упражнение дает вам только один класс, в то время как другие реализации используют два класса: один для экземпляров узла и один для экземпляра связанного списка, имеющего ссылку на головной узел связанного списка. Однако здесь единственный класс соответствует тому, что другие реализации называют классом Node, несмотря на название LinkedList. Здесь нет класса-контейнера, который содержит ссылку на головной узел. Это вы должны управлять "самим собой". Но это не главная проблема.

решения, которые я пробовал, включали преобразование в список или использование встроенных функций сортировки Python.

Вам не нужно добавлять код в метод __init__. Идея состоит в том, что вы создаете другой метод, который будет выполнять сортировку.

Этот метод не должен создавать список, подобный self.result = [], так как тогда вы просто переносите проблему сортировки в стандартный список, и вам все равно не разрешено использовать его, пусть вы можете вызвать sort или sorted для него. Более того, конечным результатом должен быть отсортированный связанный список, поэтому вам все равно придется копировать данные отсортированного списка обратно в связанный список. Идея этого упражнения состоит в том, что вы сортируете связанный список без этой дополнительной структуры данных.

вероятно, это легко исправить

Нет, так как вы не должны использовать какой-либо код, который создает и повторяет стандартный список. Так что этот код нужно сбросить.

Вы можете облегчить себе работу, сначала создав метод __iter__ в своем классе. Это не обязательно, но немного упрощает работу над этим упражнением, так как его можно использовать для печати списка или преобразования его в стандартный список для целей отладки. В связи с этим у нас есть содержимое узла, состоящее из двух компонентов: имени и количества. Поскольку мы хотим сортировать по количеству, кажется хорошей идеей иметь метод, который возвращает эти данные в виде кортежа: кортежи можно сравнивать при сортировке. Это также дает способ решить «связи» — когда два узла имеют одинаковое количество, мы, возможно, захотим использовать имя, чтобы определить, какой из них будет первым.

Вот два метода, которые я бы добавил в класс:

    def tuple(self):  # To get the content of a node as a tuple, easing comparisons
        return self.quantity, self.name
    
    def __iter__(self):  # This helps to visualise the linked list
        yield self.tuple()
        if self.tail:
            yield from self.tail

Имея это на месте, вы можете делать такие вещи, как:

fruits = LinkedList([("Apples",7),("Bananas",2),("Dragon Fruit",1),("Pomelo",14),("Grapes",65),("Cherries",43),("Pears",6),("Mangoes",31)])
print(*fruits)

... и он напечатает записи в связанном списке (с количеством в качестве первого члена кортежа). Это очень полезно при отладке.

Сортировка слиянием

Как вы предложили, давайте перейдем к сортировке слиянием. Это рекурсивный алгоритм, поэтому вам нужен базовый случай. В базовом случае список состоит только из одного элемента, т. е. когда его атрибут tail равен None. В этом случае список уже отсортирован и может быть возвращен без каких-либо дополнительных действий.

В рекурсивном случае вам необходимо:

• Разделить список на две половины (partition):
  • Первая половина будет начинаться с того же узла, что и до разделения, поэтому единственная информация, которая нам нужна после этого разделения, — это ссылка на первый узел второй половины.
• Отсортировать каждую из половин рекурсивно
• Объедините две отсортированные половины

Давайте сделаем метод partition. Нам нужно найти средний узел, и для этого мы можем использовать подход черепахи и зайца:

    def partition(self):
        # Use Tortoise and Hare approach to find (almost) middle node
        slow = self
        fast = self.tail  # Start one step ahead
        while fast and fast.tail:
            fast = fast.tail.tail
            slow = slow.tail
        head2 = slow.tail  # Second half starts after the middle node
        slow.tail = None  # Disconnect the first half of the list from the second half
        return head2  # Return start of second half

Затем нам нужен метод merge, который получает второй отсортированный связанный список в качестве аргумента, а затем объединяет узлы обоих связанных списков в один связанный список. Мы можем сначала упорядочить два списка по их головным узлам, взять первый, а затем объединить остальную часть этого первого списка со вторым, пока в одном из списков не останется узлов:

    @classmethod
    def merge(Cls, head1, head2):
        if not (head1 and head2):  # Base case: If at least one of the lists is empty,
            # ...return the other one
            return head1 or head2
        # Order the lists so that head1 has the node that should come first
        if head1.tuple() > head2.tuple():
            head1, head2 = head2, head1
        head1.tail = Cls.merge(head1.tail, head2)  # Merge rest and prepend head1
        return head1

Наконец, нам нужно реализовать алгоритм mergesort:

    def mergesort(self):
        if not self.tail:  # Base case. When list has just one node, then it is sorted. 
            return self
        # Split list into two, sort the two halves recursively 
        #    and then merge the sorted halves
        return LinkedList.merge(self.partition().mergesort(), self.mergesort())

Вот и все. Беги как:

fruits = LinkedList([("Apples",7),("Bananas",2),("Dragon Fruit",1),("Pomelo",14),("Grapes",65),("Cherries",43),("Pears",6),("Mangoes",31)])
print(*fruits)
sortedfruits = fruits.mergesort()
print("sorted:")
print(*sortedfruits)

Простое решение для сортировки выбором, которое всегда заменяет наименьшие данные на текущую позицию, а затем переходит к следующей позиции. Это занимает квадратичное время, но вы отметили, что у вас нет ограничений по сложности, и ваш __init__, а также __iter__ тринкота также требует квадратичного времени.

def print_list(lst):
    print('LinkedList:')
    while lst:
        print(' ', lst.name, lst.quantity)
        lst = lst.tail
    print()

def sort_list(lst):
    while lst:
        mini = curr = lst
        while curr:
            if curr.quantity < mini.quantity:
                mini = curr
            curr = curr.tail
        lst.name, mini.name = mini.name, lst.name
        lst.quantity, mini.quantity = mini.quantity, lst.quantity
        lst = lst.tail

print_list(fruits)
sort_list(fruits)
print_list(fruits)

Вывод (Попробуйте онлайн!):

LinkedList:
  Apples 7
  Bananas 2
  Dragon Fruit 1
  Pomelo 14
  Grapes 65
  Cherries 43
  Pears 6
  Mangoes 31

LinkedList:
  Dragon Fruit 1
  Bananas 2
  Pears 6
  Apples 7
  Pomelo 14
  Mangoes 31
  Cherries 43
  Grapes 65