python - Lomuto 算法验证测试用例

Question

我想在 Python 中创建一个测试函数，如果我通过列表和索引位置，它应该返回TRUE，或者FALSE该位置的数字是否按照Lomuto algorithm.

例如

verify_partition([-2, 5, 2, 3, 4, 8, 9, 14, 10, 23], 5). 在这种情况下，它应该在排序后判断位置 5 的元素是否正确定位。

标签： pythonlist

Answer 1

对不起，我无法抗拒。

如果只有不同的元素：

def isplaced(a, i):
    return sum(1 for e in a if e < a[i]) == i

对于非唯一元素，您还需要计算重复次数a[i]：

def isplaced(a, i):
    key = a[i]
    lt_count = le_count = 0
    for e in a:
        if e < key:
            lt_count += 1
        elif e <= key:
            le_count += 1
    return lt_count <= i < le_count

更简洁：

def isplaced(a, i):
    return sum(1 for e in a if e < a[i]) <= i < sum(1 for e in a if e <= a[i])