Lomuto算法验证测试用例

Question

我想在Python中创建一个测试函数，如果我传递列表和索引位置，如果该位置的数字按照Lomuto algorithm正确放置，它应该返回TRUE或FALSE。

例如

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

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])