快速排序算法中配分函数的改进

Question

下面是我对作业的快速排序的实现。分区函数将一个列表分成三部分。一个元素小于枢轴，一个元素等于枢轴，一个元素大于枢轴。然后，它应该返回列表中包含与pivot相等的元素的部分的开始索引和结束索引。我已经编写了以下代码，但每次执行相同的代码时，都会得到不同的数组作为最终输出。请帮忙。你知道吗

import random
def random_sort(A,p,r):
  if p<r:
    i =random.randint(p,r)
    temp=A[r]
    A[r]=A[i]
    A[i]=temp
    q,t=partition(A,p,r)
    print(q,t)
    random_sort(A,p,q-1)
    random_sort(A,t+1,r)
  return A
def partition(A,p,r):
  x=A[r]
  i=p-1
  k=p-1
  for j in range(p,r):
    if A[j]<=x:
      i+=1
      temp = A[i]
      A[i]=A[j]
      A[j]=temp
  for j in range(p,i):
    if A[j]<x:
      k+=1
      temp=A[k]
      A[k]=A[j]
      A[j]=temp
    temp=A[i+1]
    A[i+1]=A[r]
    A[r]=temp
  return k+1,i+1
A=[1,2,9,5,2]
p=0
r=len(A)-1 
a=random_sort(A,p,r)
print(a)

失败输出示例：

(3, 4)
(0, 0)
(1, 2)
[2, 1, 2, 5, 9]

输出示例：

(1, 2)
(3, 3)
[1, 2, 2, 9, 5]