在 python 中实施快速 select。函数不稳定并且 returns 个不同的值

Question

我尝试实现快速 select 以找到列表中第 m 个最小的数字。当我运行程序时，它有时在同一数组上 return 提供正确的值，而在其他时候提供不正确的值。我做错了什么她是代码

def select_mth_smallest(A, m):
    pivot = np.random.choice(A)
    # split into 3 partitions
    A1 = [] 
    A2 = []
    A3 = []
    for item in A:
        if item < pivot:
            A1.append(item)
        if item > pivot:
            A3.append(item)
        else:
            A2.append(item)
    #find where m'th largest element is and recurse accordingly
    if len(A1) >= m:
        return select_mth_smallest(A1, m)
    elif (len(A1) + len(A2)) >= m:
        return pivot
    else:
        return select_mth_smallest(A3,m - (len(A1)+len(A2)))

这是算法失败的输入。

A = [1,2,3,4,5]

select_mth_smallest(A,5)

当我重复执行上述语句时，我交替得到 5（正确）和 4（不正确）。

让我特别困惑的一件事（我是 python 的新手）是为什么当使用相同的输入重复时我得到不同的函数 return 值。看起来很零星..顺便说一句，我正在使用 Jupyter

Answer 1

您正在向多个分区添加一些项目。

    if item < pivot:
        A1.append(item)
    if item > pivot:
        A3.append(item)
    else:
        A2.append(item)

A1 是小于主元的项集。 A3 是大于主元的项目集。然而，A2 是 小于或等于 的项集，因为第二条 if 语句针对 all 项，一个或另一个分支将执行。

您需要一个带有 elif 和 else 子句的单个 if 语句。

    if item < pivot:
        A1.append(item)
    elif item > pivot:
        A3.append(item)
    else:
        A2.append(item)

在 python 中实施快速 select。函数不稳定并且 returns 个不同的值

Implementation of quick select in python. function is unstable and returns different values

python

algorithm

quicksort

quickselect