Рубрики
Без рубрики

Сортировка и слияние Одного связанного списка

Автор оригинала: Usman Malik.

Сортировка и слияние Одного связанного списка

В предыдущей статье мы начали обсуждение связанного списка. Мы увидели, что такое связанный список, а также его преимущества и недостатки. Мы также изучили некоторые наиболее часто используемые методы связанных списков, такие как обход, вставка, удаление, поиск и подсчет элементов. Наконец, мы увидели, как перевернуть связанный список.

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

Прежде чем мы продолжим, необходимо упомянуть, что вы должны создать классы Node и LinkedList , которые мы создали в предыдущей статье.

Сортировка связанного списка с помощью пузырьковой сортировки

Существует два способа сортировки связанного списка с помощью bubble sort :

  1. Обмен данными между узлами
  2. Изменение связей между узлами

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

Сортировка Связанного списка путем обмена данными

Чтобы отсортировать связанный список путем обмена данными, нам нужно объявить три переменные p , q и end .

Переменная p будет инициализирована начальным узлом, в то время как end будет иметь значение None .

Важно помнить, что для сортировки списка с n элементами с помощью пузырьковой сортировки требуется n-1 итераций.

Для реализации пузырьковой сортировки нам нужны два цикла while. Внешний цикл while выполняется до тех пор, пока значение переменной end не будет равно self.start_node .

Внутренний цикл while выполняется до тех пор, пока p не станет равным переменной end . Внутри внешнего цикла while значение p будет установлено в self.start_node , который является первым узлом. Внутри внутреннего цикла while значение q будет установлено в p.link , который на самом деле является узлом рядом с q . Затем значения p и q будут сравниваться , если p больше q значения обеих переменных будут поменяны местами, а затем p укажет на p.ref , который является следующим узлом. Наконец, end будет присвоено значение p . Этот процесс продолжается до тех пор, пока связанный список не будет отсортирован.

Давайте разберемся в этом процессе на примере. Предположим, у нас есть следующий список:

8,7,1,6,9

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

Перед выполнением цикла значение end устанавливается равным None .

На первой итерации p будет установлено значение 8, а q – значение 7 . Поскольку p больше, чем q , значения будут поменяны местами, и p станет p.ref . В этот момент времени связанный список будет выглядеть следующим образом:

7,8,1,6,9

Поскольку в этот момент времени p не равно end , цикл будет продолжаться , и теперь p станет 8, а q станет 1. Поскольку снова p больше , чем q , значения будут снова поменяны местами, и p снова станет p.ref . Список будет выглядеть так:

7,1,8,6,9

Здесь снова p не равно end , цикл будет продолжаться , и теперь p станет 8 , а q станет 6. Поскольку снова p больше q , значения будут снова поменяны местами, и p снова станет p.ref . Список будет выглядеть так:

7,1,6,8,9

Снова p не равно end , цикл будет продолжаться, и теперь p станет 8, а q станет 9. Здесь, поскольку p не больше q , значения не будут заменены и p станет p.ref . В этот момент времени ссылка p будет указывать на None , а end также указывает на None . Следовательно, внутренний цикл while будет разорван и end будет установлен в p .

В следующем наборе итераций цикл будет выполняться до 8, так как 9 уже находится в конце. Процесс продолжается до тех пор, пока список не будет полностью отсортирован.

Код Python для сортировки связанного списка с помощью пузырьковой сортировки путем обмена данными выглядит следующим образом:

    def bub_sort_datachange(self):
        end = None
        while end != self.start_node:
            p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.item, q.item = q.item, p.item
                p = p.ref
            end = p

Добавьте метод bub_sort_data exchange() в класс LinkedList , созданный в предыдущей статье.

После добавления метода в связанный список создайте любой набор узлов с помощью функции make_new_list () , а затем используйте функцию bub_sort_dataexchange() для сортировки списка. Вы должны увидеть отсортированный список при выполнении функции traverse_list () .

Сортировка Связанного списка путем изменения ссылок

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

Давайте возьмем простой пример того, как мы поменяем местами два узла, изменив ссылки. Предположим, у нас есть связанный список со следующими элементами:

10,45,65,35,1

И мы хотим поменять местами 65 и 35. В данный момент времени p соответствует узлу 65, а q соответствует узлу 35. Переменная r будет соответствовать узлу 45 (предшествующему узлу p ). Теперь , если узел p больше узла q , что имеет место здесь, то p.ref будет установлен в q.ref и q.ref будет установлен в p . Аналогично, r.ref будет установлен в q . Это приведет к замене узлов 65 и 35.

Следующий метод реализует пузырьковую сортировку для связанного списка путем изменения ссылок:

    def bub_sort_linkchange(self):
        end = None
        while end != self.start_node:
            r = p = self.start_node
            while p.ref != end:
                q = p.ref
                if p.item > q.item:
                    p.ref = q.ref
                    q.ref = p
                    if p != self.start_node:
                        r.ref = q
                    else:
                        self.start_node = q
                    p,q = q,p
                r = p
                p = p.ref
            end = p

Добавьте метод bub_sort_link change() в класс LinkedList , созданный в предыдущей статье.

После добавления метода в связанный список создайте любой набор узлов с помощью функции make_new_list () , а затем используйте функцию bub_sort_linkchange() для сортировки списка. Вы должны увидеть отсортированный список при выполнении функции traverse_list () .

Слияние Отсортированного Связанного списка

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

Давайте сначала посмотрим, как мы можем объединить два связанных списка, создав новый список.

Объединение отсортированных связанных списков путем создания нового списка

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

Предположим, у нас есть следующие два отсортированных связанных списка:

список 1:

10,45,65,

список 2:

5,15,35,68

Это два списка, которые мы хотим объединить. Алгоритм прост. Все, что нам понадобится, – это три переменные: p , q и em , а также пустой список новый список .

В начале алгоритма p будет указывать на первый элемент списка 1 тогда как q будет указывать на первый элемент списка 2 . Переменная em будет пустой. В начале алгоритма мы будем иметь следующие значения:

p = 10
q = 5
em = none
newlist = none

Далее мы сравним первый элемент list1 с первым элементом list2 , другими словами , сравним значения p и q и меньшее значение будет сохранено в переменной em , которая станет первым узлом нового списка. Значение em будет добавлено в конец нового списка .

После первого сравнения мы получим следующие значения:

p = 10
q = 15
em = 5
newlist = 5

Поскольку q был меньше p , следовательно, мы сохраняем значение q в em переместили ‘q’ на один индекс вправо. Во втором проходе мы будем иметь следующие значения:

p = 45
q = 15
em = 10
newlist = 5, 10

Здесь, поскольку p был меньше, мы добавляем значение p в новый список и устанавливаем em в p , а затем перемещаем p один индекс вправо. В следующей итерации мы имеем:

p = 45
q = 35
em = 15
newlist = 5, 10, 15

Аналогично, в следующей итерации:

p = 45
q = 68
em = 35
newlist = 5, 10, 15, 35

И на следующей итерации p снова будет меньше , чем q , следовательно:

p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45

Окончательно,

p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65

Когда один из списков становится None , все элементы второго списка добавляются в конец нового списка. Таким образом, окончательный список будет:

p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68

Скрипт Python для объединения двух отсортированных списков выглядит следующим образом:

    def merge_helper(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_newlist(self.start_node, list2.start_node)
        return merged_list

    def merge_by_newlist(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                p = p.ref
            else:
                em.ref = Node(q.item)
                q = q.ref
            em = em.ref

        while p is not None:
            em.ref = Node(p.item)
            p = p.ref
            em = em.ref

        while q is not None:
            em.ref = Node(q.item)
            q = q.ref
            em = em.ref

        return startNode

В приведенном выше скрипте у нас есть два метода: merge_helper() и merge_by_new list() . Первый метод merge_helper() принимает связанный список в качестве параметра, а затем передает класс self , который является самим связанным списком и связанным списком, переданным ему в качестве параметра, методу merge_by_newlist () .

Метод merge_by_newlist() объединяет два связанных списка, создавая новый связанный список, и возвращает начальный узел нового связанного списка. Добавьте эти два метода в класс LinkedList . Создайте два новых связанных списка, отсортируйте их с помощью методов bub_sort_datachange() или bub_sort_linkchange () , созданных в предыдущем разделе, а затем используйте метод merge_by_newlist () , чтобы узнать, можно ли объединить два отсортированных связанных списка или нет.

Объединение Отсортированных Связанных списков путем перестановки ссылок

При таком подходе новый связанный список не используется для хранения слияния двух отсортированных связанных списков. Скорее всего, ссылки двух связанных списков изменяются таким образом, что два связанных списка объединяются сортированным образом.

Давайте рассмотрим простой пример того, как мы можем это сделать. Предположим, у нас есть те же два списка list1 и list2 :

список 1:

10,45,65,

список 2:

5,15,35,68

Мы хотим объединить их отсортированным образом, переставив ссылки. Для этого нам нужны переменные p , q и em . Изначально они будут иметь следующие значения:

p = 10
q = 5
em = none
newlist = none

Далее мы сравним первый элемент list1 с первым элементом list2 , другими словами , сравним значения p и q и меньшее значение будет сохранено в переменной em , которая станет первым узлом нового списка.

После первого сравнения мы получим следующие значения:

p = 10
q = 15
start = 5
em = start

После первой итерации, поскольку q меньше p , начальный узел будет указывать на q и q станет q.ref . em будет равно start. em всегда будет ссылаться на вновь вставленный узел в объединенном списке.

p = 45
q = 15
em = 10

Здесь, поскольку p был меньше, чем q , переменная em теперь указывает на исходное значение p и p становится p.ref .

p = 45
q = 35
em = 15

Здесь, поскольку q был меньше p , em указывает на q и q становится q.ref .

p = 45
q = 68
em = 35

Аналогично em здесь указывает на q .

p = 65
q = 68
em = 45
newlist = 5, 10, 15, 35, 45

И вот em указывает в сторону становится p .

p = None
q = 68
em = 65
newlist = 5, 10, 15, 35, 45, 65

Когда один из списков становится None , элементы из второго списка просто добавляются в конце.

p = None
q = None
em = 68
newlist = 5, 10, 15, 35, 45, 65, 68

Сценарий, содержащий функции для объединения двух списков без создания нового списка, выглядит следующим образом:

    def merge_helper2(self, list2):
        merged_list = LinkedList()
        merged_list.start_node = self.merge_by_linkChange(self.start_node, list2.start_node)
        return merged_list

    def merge_by_linkChange(self, p, q):
        if p.item <= q.item:
            startNode = Node(p.item)
            p = p.ref
        else:
            startNode = Node(q.item)
            q = q.ref

        em = startNode

        while p is not None and q is not None:
            if p.item <= q.item:
                em.ref = Node(p.item)
                em = em.ref
                p = p.ref
            else:
                em.ref = Node(q.item)
                em = em.ref
                q = q.ref


        if p is None:
            em.ref = q
        else:
            em.ref = p

        return startNode

В приведенном выше скрипте у нас есть два метода: merge_helper 2() и merge_by_link Change() . Первый метод merge_helper2() принимает связанный список в качестве параметра, а затем передает класс self , который сам является связанным списком, и связанный список, переданный ему в качестве параметра, в merge_by_linkChange () , который объединяет два связанных путем изменения ссылок и возвращает начальный узел объединенного списка. Добавьте эти два метода в класс LinkedList . Создайте два новых связанных списка, отсортируйте их с помощью методов bub_sort_datachange() или bub_sort_linkchange () , созданных в предыдущем разделе, а затем используйте merge_by_newlist () , чтобы узнать, можно ли объединить два отсортированных связанных списка или нет. Давайте посмотрим на этот процесс в действии.

Создайте новый связанный список с помощью следующего скрипта:

new_linked_list1 = LinkedList()
new_linked_list1.make_new_list()

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

How many nodes do you want to create: 4
Enter the value for the node:12
Enter the value for the node:45
Enter the value for the node:32
Enter the value for the node:61

Затем создайте еще один связанный список, повторяя описанный выше процесс:

new_linked_list2 = LinkedList()
new_linked_list2.make_new_list()

Затем добавьте несколько фиктивных узлов с помощью следующего скрипта:

How many nodes do you want to create: 4
Enter the value for the node:36
Enter the value for the node:41
Enter the value for the node:25
Enter the value for the node:9

Следующий шаг-сортировка обоих списков. Выполните следующий сценарий:

new_linked_list1. bub_sort_datachange()
new_linked_list2. bub_sort_datachange()

Наконец, следующий сценарий объединяет два связанных списка:

list3 = new_linked_list1.merge_helper2(new_linked_list2)

Чтобы проверить, действительно ли списки были объединены, выполните следующий сценарий:

list3.traverse_list()

Вывод выглядит следующим образом:

9
12
25
32
36
41
45
61

Вывод

В этой статье мы продолжили с того места, на котором остановились в предыдущей статье . Мы видели, как мы можем сортировать списки слияний, изменяя данные, а затем мои модифицирующие ссылки. Наконец, мы также изучили различные способы объединения двух отсортированных связанных списков.

В следующей статье мы рассмотрим, как создавать и выполнять операции с двусвязными списками.