Понимание рекурсивных функций - Быстрый выбор - Найти медиану за линейное время - PullRequest
Новая
       51

Понимание рекурсивных функций - Быстрый выбор - Найти медиану за линейное время

0 голосов
/ 03 июня 2019

Я пытаюсь реализовать этот алгоритм (с этого сайта: https://sarielhp.org/research/CG/applets/linear_prog/median.html).

FindKMedian (A, K) // Возвращаем число в A, которое является K-м по размеру.

  1. Случайно выберите число a из A = {a1, ..., an}.
  2. Разделите n чисел на два набора:
    • S - все числа меньшечем
    • B - все числа, превышающие
  3. Если | S | = K-1, то a является необходимой K-медианой. Возвращает a
  4. Если | S |
  5. Иначе, рекурсивно вызывать FindKMedian (S, K).

После ответа @mikake я получаю сообщение об ошибке при вызове функции с параметрами в конце кода. 

import random


def quick_select(A, k, s, d):
    r = random.choice(range(s, d))
    pivot = partition(A, r, s, d)
    if pivot == k:
        return A[pivot]
    elif k < pivot:
        return quick_select(A, k, s, pivot-1)
    else:
        return quick_select(A, k, pivot + 1, d)


def partition(A, r, s, d):
    j = s-1
    assert s <= r
    assert r <= d
    temp = A[d]
    A[d] = A[r]
    A[r] = temp
    for i in range(s, d):
        if A[i] <= A[d]:
            j = j+1
            temp = A[j]
            A[j] = A[i]
            A[i] = temp
    j = j+1
    temp = A[j]
    A[j] = A[d]
    A[d] = temp
    return j


random.seed(0)
A = [4, 7, 7, 2, 2, 0, 9, 8, 1, 8]
print(quick_select(A, 5, 0, 9))

Я ожидаю, что число 7выйти из возврата quickselect (так что quick_select (A, 5, 0, 9) означает «найти A [5] после сортировки подмассива A [0, ..., 5] или после A [5, ...»), 9] отсортировано "). Я, вероятно, не понял, что семантика этогоКод должен быть.

Спасибо

Ответы [ 2 ]

1 голос
/ 03 июня 2019

Вы забыли добавить оператор return в ветки "else": 

def quick_select(A, k, s, d):
    r = random.choice(range(s, d))
    pivot = partition(A, r, s, d)
    if pivot == k:
        return A[pivot]
    elif k < pivot:
        return quick_select(A, k, s, pivot-1)
    else:
        return quick_select(A, k, pivot + 1, d)
0 голосов
/ 03 июня 2019

Я думаю, что единственная ошибка, которую я допустил, это не рассмотрение случая, когда массив имеет длину 1. Поэтому правильный код функции "quick_select" должен быть 

def quick_select(A, k, s, d):
    if s == d:
        return A[k]
    r = random.choice(range(s, d))
    pivot = partition(A, r, s, d)
    if pivot == k:
        return A[pivot]
    elif k < pivot:
        return quick_select(A, k, s, pivot-1)
    else:
        return quick_select(A, k, pivot + 1, d)
...