Как реализовать схему разделов Hoare в Quickselect? - PullRequest
Новая
       38

Как реализовать схему разделов Hoare в Quickselect?

0 голосов
/ 10 апреля 2019

Я пытаюсь реализовать схему Hoare как часть алгоритма Quickselect, но, похоже, каждый раз дает мне разные ответы.

Это функция findKthBest, которая находит K-е наибольшее число в массиве, заданном массиве (data) и количество элементов в нем (low = 0, high = 4 в случае 5 элементов): 

def findKthBest(k, data, low, high):
    # choose random pivot
    pivotindex = random.randint(low, high)

    # move the pivot to the end
    data[pivotindex], data[high] = data[high], data[pivotindex]

    # partition
    pivotmid = partition(data, low, high, data[high])

    # move the pivot back
    data[pivotmid], data[high] = data[high], data[pivotmid]

    # continue with the relevant part of the list
    if pivotmid == k:
        return data[pivotmid]
    elif k < pivotmid:
        return findKthBest(k, data, low, pivotmid - 1)
    else:
        return findKthBest(k, data, pivotmid + 1, high)

Функция partition() получает четыре переменные:

  • data (список, например, из 5 элементов),
  • l (начальная позиция соответствующей детали в списке, например, 0)
  • r (конечная позиция соответствующей детали в списке, где также расположена ось, например 4)
  • pivot (значение пивота) 
def partition(data, l, r, pivot):
    while True:
        while data[l] < pivot:
            #statistik.nrComparisons += 1
            l = l + 1
        r = r - 1    # skip the pivot
        while r != 0 and data[r] > pivot:
            #statistik.nrComparisons += 1
            r = r - 1
        if r > l:
            data[r], data[l] = data[l], data[r]
        return r

Сейчас я просто каждый раз получаю различные результаты, и кажется, что рекурсия работает не так хорошо (иногда она заканчивается достижением ошибки максимальной рекурсии) вместо того, чтобы каждый раз давать постоянный результат. Что я делаю не так?

1 Ответ

0 голосов
/ 11 апреля 2019

Во-первых, в функции partition()

появляется ошибка. Если вы тщательно сравните свой код с кодом в вики, вы найдете разницу.Функция должна быть: 

def partition(data, l, r, pivot):
    while True:
        while data[l] < pivot:
            #statistik.nrComparisons += 1
            l = l + 1
        r = r - 1    # skip the pivot
        while r != 0 and data[r] > pivot:
            #statistik.nrComparisons += 1
            r = r - 1
        if r >= l:
            return r

        data[r], data[l] = data[l], data[r]

Секунда, например:

  • Вы получаете массив data = [1, 0, 2, 4, 3] с pivotmid=3 после разделения
  • Вы хотитенайдите 4-е наибольшее значение (k=4), которое равно 1

Следующий массив data с парсингом к findKthBest() станет [1, 0].
Следовательно, следующее findKthBest() должно найти наибольшее значение массива [1, 0]: 

def findKthBest(k, data, low, high):
    ......

    # continue with the relevant part of the list
    if pivotmid == k:
        return data[pivotmid]
    elif k < pivotmid:
        #Corrected
        return findKthBest(k-pivotmid, data, low, pivotmid - 1)
    else:
        return findKthBest(k, data, pivotmid + 1, high)
...