Функция Python Quicksort переходит в бесконечный цикл - PullRequest
Новая
       33

Функция Python Quicksort переходит в бесконечный цикл

0 голосов
/ 17 октября 2019

у меня есть список контактов словарей. 

contacts = [{'first':'asasdasd', 'last':'sddafs','email':'asdsadas'},
{'first':'asasdasd', 'last':'sddafs','email':'asdsadas'}]

Я бы хотел отсортировать словари в списке по ключу 'last', используя алгоритм быстрой сортировки. 

less = []
greater = []

def qsort_last(listD):
    if len(listD) < 2:
        return listD
    else:
        pivot = contacts[0]['last']
        for i in range(len(listD)):
            if listD[i]['last'] <= pivot:
                less.append(listD[i])
            else:
                greater.append(listD[i])
        return qsort_last(less) + [contacts[0]] + qsort_last(greater)

print(qsort_last(contacts))

Теперь функцияидет в бесконечный цикл. Пожалуйста, сообщите.

Ответы [ 2 ]

0 голосов
/ 17 октября 2019

обновлен. Теперь это работает. Спасибо всем за помощь. 

def qsort_last(listD):
    less = []
    greater = []
    middle=[]
    if len(listD) < 2:
        return listD
    else:
        pivot = listD[0]['last']
        for i in range(len(listD)):
            if listD[i]['last'] < pivot:
                less.append(listD[i])
            elif listD[i]['last'] > pivot:
                greater.append(listD[i])
            elif listD[i]['last'] == pivot:
                middle.append(listD[i])

        return qsort_last(less) + middle + qsort_last(greater)
0 голосов
/ 17 октября 2019

Проблема в том, что вы продолжаете добавлять элементы в свои списки less и greater, чтобы они продолжали расти без ограничений.

Кроме того, вы дублируете элемент pivot из-за <= в предложении if.

Попробуйте: 

def qsort_last(listD):
    less = []
    greater = []

    if len(listD) < 2:
        return listD
    else:
        pivot = listD[0]['last']
        for i in range(len(listD)):
            if listD[i]['last'] < pivot:
                less.append(listD[i])
            elif listD[i]['last'] > pivot:
                greater.append(listD[i])
        return qsort_last(less) + [contacts[0]] + qsort_last(greater)
...