максимальная ошибка глубины рекурсии в рандомизированной быстрой сортировке - PullRequest
Новая
       8

максимальная ошибка глубины рекурсии в рандомизированной быстрой сортировке

0 голосов
/ 06 июля 2018

Я написал рекурсивную рандомизированную функцию быстрой сортировки, как показано ниже: 

def randomized_quick_sort(a, l, r):
    if l >= r:
        return
    k = random.randint(l, r)

    a[l], a[k] = a[k], a[l]

    m1, m2 = partition3(a, l, r)
    randomized_quick_sort(a,l,m1-1)
    randomized_quick_sort(a,m2+1,r)

Ниже приведена используемая функция разбиения, которая разбивает список на три части: меньше, чем точка, равна точке и больше, чем точка, где точка является первым элементом в списке ввода. 

def partition3(a, l, r):
    x = a[l]
    less, equal, greater = [], [], []
    for val in a[l:r+1]:
        if val < x: 
            less.append(val)
        if val == x: 
            equal.append(val)
        if val > x: 
            greater.append(val)

    a[l:r+1] = less + equal + greater
    m1 = len(less)
    m2 = m1 + len(equal) - 1
    return m1, m2

если я запускаю эту функцию быстрой сортировки несколько раз на простом вводе, таком как 

a = [2,2,3,3]
randomized_quick_sort(a,0,len(a)-1)

после всего лишь нескольких попыток я получаю ошибку «превышена максимальная глубина рекурсии». Пожалуйста, помогите!

Ответы [ 2 ]

0 голосов
/ 05 февраля 2019

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

import random
def partition(arr, start, end):
    pivot = arr[end]
    ix = start
    for i in range(start, end):
        if arr[i] <= pivot:
            arr[i], arr[ix] = arr[ix], arr[i]
            ix += 1
    arr[ix], arr[end] = arr[end], arr[ix]
    return ix

def quick_sort(arr, start, end):
    if start > end: return
    rand_num = random.randint(start, end)
    arr[rand_num], arr[end] = arr[end], arr[rand_num]
    ix = partition(arr, start, end)
    quick_sort(arr, start, ix-1)
    quick_sort(arr, ix+1, end)

arr = [2,4,7,8,9,1,3,5,6,12,32]
quick_sort(arr, 0, len(ans)-1)

output:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 32]
0 голосов
/ 06 июля 2018

Это на самом деле довольно близко, но я рекомендую протестировать def partition3(a, l, r) само по себе. Вы увидите, что возвращаемые значения на самом деле не имеют смысла.

Однако, с небольшим изменением, мы можем заставить его работать: 

m1 = len(less)

должно быть: 

m1 = len(less) + l # l for left, not 1 for one

Вы не хотите, чтобы m1 была просто длиной элементов в less, потому что, если бы вы сравнивали 9-й и 11-й элементы, вы бы вернули 1, когда хотите вернуть 10.

Кроме того, в общем, старайтесь избегать однобуквенных имен переменных (особенно l, который легко спутать с 1). Людям, незнакомым с вашим кодом, трудно читать и видеть, что происходит.

...