Алгоритм быстрого выбора в стиле быстрой сортировки

Question

Я пытаюсь закодировать оптимальный алгоритм для выбора i-го элемента, большего из списка.Например, если array = [4,3,5,7] и я ищу 2-й, функция вернет 4.

Я предполагаю, что в списке только отдельные номера

Вот проблема:

Функция иногда возвращает None.

А вот мой код (я думаю, что первая функция работает хорошо).

from random import shuffle

def partition(array, leftend, rightend, pivot):
    """ I tested this one and it should work fine """
    i = leftend
    pivotindex = array.index(pivot)  # only works if all values in array unique
    array[pivotindex] = array[leftend]
    array[leftend] = pivot
    for j in range(leftend+1, rightend):
        if array[j] < pivot:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
            i += 1
    pivotindex = array.index(pivot)  # only works if all values in array unique
    leftendval = array[pivotindex]   # Take the value of the pivot
    array[pivotindex] = array[i]
    array[i] = leftendval
    return array

def RSelect(array, n, statistic_order):
    """ list * int * int
        statistic_order = the i th element i'm searching for """
    new_array = []                  # is used at the end of the function
    if n == 1:
        return array[0]
    array_temp = array              # Allows to have a shuffled list and
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    partition(array,0,n,pivot)
    j = array.index(pivot)


    if j == statistic_order:
        return pivot


    elif j > statistic_order:
        for k in range(0,j):
            new_array.append(array[k])
        RSelect(new_array,j,statistic_order)


    elif j < statistic_order:
        for k in range(j+1,n):
            new_array.append(array[k])
        RSelect(new_array,(n-j)-1,statistic_order-j)

Answer 1

код работает нормально, но все равно результат начинается с 0. Например, если arr = [2,3,5,6] и я спрашиваю RSelect (arr, 4,2), ответ будет 5 ине 3. Я не знаю почему.

Вот обновленный код:

from random import shuffle

def partition(array, leftend, rightend, pivot):
    i = leftend
    pivotindex = array.index(pivot)  # only works if all values in array unique
    array[pivotindex] = array[leftend]
    array[leftend] = pivot
    for j in range(leftend+1, rightend):
        if array[j] < pivot:
            temp = array[j]
            array[j] = array[i]
            array[i] = temp
            i += 1
    pivotindex = array.index(pivot)  # only works if all values in array unique
    leftendval = array[pivotindex]   # Take the value of the pivot
    array[pivotindex] = array[i]
    array[i] = leftendval


def RSelect(array, n, statistic_order):
    """ list * int * int
        statistic_order = the i th element i'm searching for """
    if n == 1:
        return array[0]

    array_temp = array              # Allows to have a shuffled list
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    partition(array,0,n,pivot)
    j = array.index(pivot)


    if j == statistic_order:
        return pivot


    elif j > statistic_order:
        return RSelect(array[0:j],j,statistic_order)


    elif j < statistic_order:
        return RSelect(array[j+1:n],(n-j)-1,statistic_order-j-1)

Answer 2

Ну, некоторые вещи были неправильными:

• Вы должны возвращать результаты рекурсивным методом в каждом случае!
• Когда j

Я также изменил несколько вещей, таких как бесполезные параметры или для циклов, которые можно записать с помощью слайсов.

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

RSelect:

def RSelect(array, statistic_order):
    """ list * int * int
    statistic_order = the i th element i'm searching for """
    n = len(array)
    if n == 1:
        return array[0]
    array_temp = array              # Allows to have a shuffled list and
    shuffle(array_temp)
    pivot = array_temp[0]           # Allows to have a random pivot
    array = partition(array,0,n,pivot)  # Changes here, does not impact the result, but for readability
    j = array.index(pivot)

    # print(array, j, statistic_order, end = '\t')
    if j == statistic_order:
        return pivot

    elif j > statistic_order:
        assert j > 0
        # print((array[0:j]), pivot)
        return RSelect(array[0:j],statistic_order)  # Changes here : return

    elif j < statistic_order:
        assert j+1 < n
        # print(pivot, (array[j+1:n]))
        return RSelect(array[j+1:n],statistic_order-j-1)  # Changes here : return, -j-1

main:

if __name__ == "__main__":
    from sys import argv
    if len(argv) > 1:
       n = int(argv[1])
    arr = [2, 1, 3, 5, 4]
    print(RSelect(arr[:], n))

Существует другой алгоритм, также в O (n) для этой цели: см. this

EDIT: исправлены опечатки и исправлены сложности