Проблемы с реализацией рекурсии в моей попытке быстрого алгоритма сортировки в Python - PullRequest
Новая
       18

Проблемы с реализацией рекурсии в моей попытке быстрого алгоритма сортировки в Python

0 голосов
/ 29 января 2019

Я пытаюсь написать свой собственный алгоритм быстрой сортировки на Python, не глядя, как это делается профессионально (я узнаю больше так).Если моя идея о том, как я собираюсь реализовать эту быструю сортировку, кажется вам глупой (я знаю, что, вероятно, так и будет), пожалуйста, не предлагайте мне совершенно другой способ сделать это, если мой метод никогда не будет успешным или, по крайней мере, нетбез нелепых мер, пожалуйста, помогите мне найти решение с помощью моего желаемого метода:)

В настоящее время у меня есть определенная функция "pivot", которая будет принимать входной список и выводить три списка, список чисел, меньший, чемpivot (выбранный в этом случае, чтобы быть первым числом в списке каждый раз), список чисел, равных pivot, и список чисел, больших, чем pivot.

Мой следующий шаг должен был определить функцию"q_sort".Сначала эта функция создает список с именем «finalList» и заполняет его нулями, так что он имеет ту же длину, что и сортируемый список.Затем он поворачивает список и добавляет числа, равные pivot, к finalList в том, что уже является их правильной позицией (поскольку есть 0, чтобы представить число элементов, меньших его, и 0 как заполнители вместо вместоэлементы больше, чем сводная)

Все это прекрасно работает.

То, что не работает нормально, это следующий шаг.Я написал, что я хочу, чтобы происходило дальше, в каком-то плохо продуманном псевдокоде ниже: 

numList = [3, 5, 3, 1, 12, 65, 2, 11, 32]

def pivot(aList):
    biggerNum =[]
    smallerNum = []
    equalNum = [aList[0]]
    for x in range(1, len(aList)):
        if aList[0]<aList[x]:
            biggerNum.append(aList[x])
        elif aList[0]>aList[x]:
            smallerNum.append(aList[x])
        elif aList[0] == aList[x]:
            equalNum.append(aList[x])
    pivoted = [smallerNum, equalNum, biggerNum]
    return pivoted

def q_sort(aList):
    finalList = []
    for x in range(len(aList)):
        finalList.append(0)
    pivot(aList)
    for i in range(len(pivot(aList)[1])):
        finalList[len(pivot(aList)[0])+i] = pivot(aList)[1][i]

Псевдокод: 

    #if len(smallerNum) != 0:
        #q_sort(smallerNum) <--- I want this to add it's pivot to finalList
    #if len(biggerNum) != 0:
        #q_sort(biggerNum) <--- Again I want this to add it's pivot to finalList
#return finalList <--- Now after all the recursion every number has been pivoted and added

Что я собираюсь сделать, так это если списокиз чисел, меньших, чем у сводной точки, на самом деле есть какие-либо элементы, тогда она будет q_sort этого списка.Это означает, что он найдет новый стержень и добавит его значение к правильной позиции в finalList.Я думаю, что это работает так, что функция достигает «return finalList» только после того, как каждое число из «numList» будет помещено в правильную позицию.Поскольку рекурсивный характер включения q_sort в q_sort означает, что после поворота «lowerNum» (и добавления сводки в finalList) у него будет еще один список для сводки.

1 Ответ

0 голосов
/ 29 января 2019

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

def q_sort(aList, low, high):
    if low >= high:
        return

    # find pivot position, "pivot"
    ...
    # arrange list on either side of pivot
    ...
    # recur on each part of list. 
    q_sort(alist, low_index, pivot-1)
    q_sort(alist, pivot+1, high_index)

Достаточно ли этого контура, чтобы заставить вас двигаться?

Если нет, попробуйтепоиск в браузере по "Python quicksort", и вы найдете много помощи, более полной, чем мы можем описать здесь.

...