Python - TypeError при реализации алгоритма сортировки слиянием

Итак, я новичок в python и в настоящее время изучаю манипуляции со списками. Ниже приведена программа, которую я написал для выполнения сортировки слиянием в моем списке. Однако при компиляции я получаю сообщение об ошибке в строке 3-

while len(lista) != 0 and len(listb) != 0:
    TypeError: object of type 'NoneType' has no len()

Как я могу это исправить?

def mergesort(lista, listb):
    listc = []
    while len(lista) != 0 and len(listb) != 0:
        if lista[0] > listb[0]:
            listc.append(listb[0])
            listb.remove(listb[0])
        else:
            listc.append(lista[0])
            lista.remove(lista[0])

    if len(lista) == 0:
        listc += listb
    else:
        listc += lista

    print(listc)

def merge(list):
    if len(list) == 0 or len(list) == 1:
        return list
    else:
        mid = len(list) // 2
        lista = merge(list[:mid])
        listb = merge(list[mid:])
        return mergesort(lista, listb)

list = [15, 12, 14, 17, 13, 11, 12, 16, 15]
merge(list)

python algorithm mergesort
person zsasz    schedule 01.05.2020    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Ваш код запутан и ошибочен:

  • функция сортировки называется merge, а функция слияния - mergesort. Это полная противоположность любой классической реализации.

  • функция слияния ничего не возвращает, поэтому lista и listb получают значение None из рекурсивных вызовов, а mergesort применяет len к аргументам, которые не являются списками.

Вот модифицированная версия:

def merge(lista, listb):
    listc = []
    while len(lista) != 0 and len(listb) != 0:
        if lista[0] > listb[0]:
            listc.append(listb[0])
            listb.remove(listb[0])
        else:
            listc.append(lista[0])
            lista.remove(lista[0])

    if len(lista) == 0:
        listc += listb
    else:
        listc += lista

    return listc

def mergesort(list):
    if len(list) < 2:
        return list
    else:
        mid = len(list) // 2
        lista = mergesort(list[:mid])
        listb = mergesort(list[mid:])
        return merge(lista, listb)

list = [15, 12, 14, 17, 13, 11, 12, 16, 15]
mergesort(list)
person chqrlie    schedule 01.05.2020
comment
Спасибо, что работает сейчас. Позже я использовал оператор return раньше в функции слияния, но отступ был неправильным, но теперь он работает плавно - person zsasz; 01.05.2020
comment
@zsasz: стиль Python, в котором структура определяется отступом, имеет высокую цену: он делает код очень хрупким (легко ломается). - person chqrlie; 01.05.2020

arrow_upward
0
arrow_downward

Во-первых, не используйте list в качестве идентификатора.

В вашей функции слияния в блоке else вы возвращаете то, что возвращает функция слияния. А в функции mergesort вы ничего не возвращаете.

Кроме того, из-за рекурсии в функции слияния вы заканчиваете установку переменных lista и listb на возвращаемые значения функции слияния, которые могут быть нулевыми, поскольку mergesort ничего не возвращает (таким образом, None).

Когда вы отправляете эти lista и listb при сортировке слиянием в качестве аргументов, вы фактически отправляете None в таких случаях, и, таким образом, вы получаете ошибку, когда пытаетесь получить их длину с помощью функции len.

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

person Vicrobot    schedule 01.05.2020

arrow_upward
0
arrow_downward

Это потому, что в вашей функции слияния lista и listb становятся None и передаются функции. Также ваша функция merge_sort неверна. Вы можете справиться со своей ошибкой, используя следующий код:

def mergesort(lista, listb):
    listc = []
    if not lista or not listb:
        return None
    while len(lista) != 0 and len(listb) != 0:
        if lista[0] > listb[0]:
            listc.append(listb[0])
            listb.remove(listb[0])
        else:
            listc.append(lista[0])
            lista.remove(lista[0])


    if len(lista) == 0:
        listc += listb
    else:
        listc += lista

    print(listc)

def merge(list):
    if len(list) == 0 or len(list) == 1:
        return list
    else:
        mid = len(list) // 2
        lista = merge(list[:mid])
        listb = merge(list[mid:])
        return mergesort(lista,listb)


list = [15, 12, 14, 17, 13, 11, 12, 16, 15]
merge(list)
person Abhishek Kulkarni    schedule 01.05.2020
comment
что именно делает оператор if not lista или not listb? Ваша версия работает, но возвращает ее в виде нескольких отсортированных списков из 2 элементов. - person zsasz; 01.05.2020
comment
Это то, что я сказал, я только что сказал вам, как обрабатывать такие ошибки, функцию списка слияния необходимо изменить, not lista или not listb проверяет, есть ли какой-либо из них None, и если это так, он возвращает - person Abhishek Kulkarni; 01.05.2020
comment
вы можете принять ответы, если сочли их полезными - person Abhishek Kulkarni; 01.05.2020