Сортировка слиянием в связанном списке - PullRequest
Новая
       28

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

0 голосов
/ 10 марта 2020

Объединить функции сортировки только с некоторыми входами при запуске в связанном списке. Если я включаю 0 в список входных данных, только 0 возвращается из последнего вызова print (). Я не знаю, что я делаю неправильно 

class StackNode(object):
    def __init__(self, data):
        self.data = data
        self.prev = None

class Stack(object):
    def __init__(self):
        self.head = None
        self.count = 0

    def push(self, data):
        if (self.head == None):
            self.head = StackNode(data)
            self.count += 1
            return
        node = StackNode(data)
        node.prev = self.head
        self.head = node
        self.count += 1
        return

    def pop(self):
        node = self.head
        self.head = self.head.prev
        self.count -= 1
        return node

    def print(self):
        node = self.head
        if(node == None):
            return
        print(node.data)
        while(node.prev):
            node = node.prev
            print(node.data)

    def MergeSort(self, h):
        if h == None or h.prev == None:
            return h
        middle = self.GetMiddle(h)
        nextToMiddle = middle.prev
        middle.prev = None
        left = self.MergeSort(h)
        right = self.MergeSort(nextToMiddle)
        sortedList = self.SortedMerge(left, right)
        return sortedList


     def SortedMerge(self, a, b):
        if a is None:
            return b
        if b is None:
            return a
        if(a.data > b.data):
            result = a
            a.prev = self.SortedMerge(a.prev, b)
        else:
            result = b
            b.prev = self.SortedMerge(b.prev, a)
        return result

    def GetMiddle(self, head):
        if head == None:
            return head
        slow = head
        fast = head
        while(fast.prev != None and fast.prev.prev != None):
            slow = slow.prev
            fast = fast.prev.prev
        return slow

a = Stack()
a.push(2)
a.push(5)
a.push(1)
a.push(4)
a.push(3)
a.push(7)
a.print()
a.MergeSort(a.head)
print("after: ")
a.print()

Я транскрибировал свой код непосредственно из примера сортировки слиянием связанного списка, приведенного на geeksforgeeks.com, с той лишь разницей, что мой код вместо этого создает стек очереди

1 Ответ

1 голос
/ 10 марта 2020

MergeSort возвращает заголовок отсортированного списка, поэтому вызов в основном коде должен быть: 

a.head = a.MergeSort(a.head)

Для отсортированного стека может показаться, что результат выполнения последовательного list.pop () должен возвращать узлы в порядке данных, но код использует «>» вместо «<=» в сравнении, в обратном порядке. </p>

Python 2.7 жаловался на использование имени для печати функция печати класса, а также жаловалась на 5 (вместо 4) пробелов перед "def SortedMerge (self, a, b):"

SortedMerge () выполняет один уровень рекурсии для каждого узла слиты. Для большого списка программа получит переполнение стека. Поскольку класс списка включает счетчик, код может использовать list.count // 2 для определения количества узлов, которые необходимо продвинуться, чтобы достичь средней точки, а затем использовать (count // 2) для размера левой половины и (count- (count // 2)) для размера правой половины. Сортировка снизу вверх еще быстрее. Однако с python накладные расходы на интерпретацию кода настолько велики, что я не знаю, будет ли это иметь значение. Вот ссылка на сортировку слиянием сверху вниз и снизу вверх для связанного списка, в java, использующего общую функцию слияния:

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

Я преобразовал код в python. Функция слияния одинакова для обоих примеров. Обратите внимание, что сортировка logi c одинакова, только функции pu sh и pop приводят к тому, что связанный список действует как стек. Функция слияния: 

    def Merge(self, a, b):
        if a is None:
            return b
        if b is None:
            return a
        r = StackNode(0)                    # dummy node
        d = r
        while(True):
            if(a.data <= b.data):
                d.prev = a
                d = a
                a = a.prev
                if(a == None):
                    d.prev = b
                    break
            else:
                d.prev = b
                d = b
                b = b.prev
                if(b == None):
                    d.prev = a
                    break
        return r.prev

Пример сверху вниз: 

    def MergeSort(self):
        if(self.count < 2):
            return
        self.head = self.MergeSortR(self.head, self.count)

    def MergeSortR(self, h, n):
        if(n < 2):
            return h
        n2 = n//2
        t = self.Scan(h, n2-1)
        m = t.prev
        t.prev = None
        h = self.MergeSortR(h, n2)
        m = self.MergeSortR(m, n-n2)
        h = self.Merge(h, m)
        return h

    def Scan(self, h, n):
        while(n > 0):
            h = h.prev
            n = n-1
        return h

Пример снизу: 

    def MergeSort(self):
        if(self.count < 2):
            return
        an = [None] * 32
        node = self.head
        while(node != None):
            prev = node.prev
            node.prev = None
            i = 0
            while((i < 32) and (an[i] != None)):
                node = self.Merge(an[i], node)
                an[i] = None
                i = i+1
            if(i == 32):
                i = i-1
            an[i] = node
            node = prev
        for i in xrange (0, 32):
            node = self.Merge(an[i], node)
        self.head = node

Тестовый код для узлов 512K. В моей системе, сверху вниз занимает около 4,5 секунд, снизу вверх около 3,9 секунд. Чтобы понять издержки Python, снизу вверх C требуется около 0,06 секунды. 

import random
from time import time
p = [random.randint(0, 2147483647) for r in xrange(512*1024)]
a = Stack()
for i in xrange (0, len(p)):
    a.push(p[i])
s = time()
a.MergeSort()
e = time()
print e - s
for i in xrange (0, len(p)):
    p[i] = a.pop().data
for i in xrange (1, len(p)):
    if(p[i-1] > p[i]):
        print("error")
        break
...