Quicksort函数不会产生预期的输出，尽管分区函数会产生（python）

Question

我必须在学校项目的“切片”对象上实现快速排序算法，该切片对象是具有：的元组：

• 一个“数据”字段（要排序的整个numpy数组）
• 一个'left'和'right'字段（索引表示数组中切片的子部分）

分区功能代码如下：

def partition (s, cmp, piv=0):
"""
Creates two slices from *s* by selecting in the first slice all
elements being less than the pivot and in the second one all other
elements.

:param s: A slice of is a dictionary with 3 fields :
          - data: the array of objects,
          - left: left bound of the slide (a position in the array),
          - right: right bound of the slice.
:type s: dict
:param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
:type cmp: function
:return: A couple of slices, the first slice contains all elements that are
         less than the pivot, the second one contains all elements that are
         greater than the pivot, the pivot does not belong to any slice.
:rtype: tuple

>>> import generate
>>> import element
>>> import numpy
>>> def cmp (x,y):
...    if x == y:
...       return 0
...    elif x < y:
...       return -1
...    else:
...       return 1
>>> t = numpy.array([element.Element(i) for i in [4,2,3,1]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> pivot = 0
>>> p1,p2 = partition(p,cmp,pivot)
>>> print(p1['data'][p1['left']:p1['right']+1])
[1 2 3 4]
>>> print(p2['data'][p2['left']:p2['right']+1])
[]
"""
#convenience variables to make the function easily readable.
left = s['left']
right = s['right']
swap(s['data'],right,piv)

j = left
for i in range(left,right+1):
    if (cmp(s['data'][i] , s['data'][right]) != 1 ):
        swap(s['data'],i,j)
        j += 1
s1 = {'data':s['data'],'left':left,'right':j-1}
s2 = {'data':s['data'],'left':j+1,'right':right}

return s1,s2

此函数的doctest不会失败，但是，在调用quicksort递归函数时，分区函数的行为不符合预期。quicksort函数的代码如下：

def quicksort_slice (s, cmp):
"""
A sorting function implementing the quicksort algorithm

:param s: A slice of an array, that is a dictionary with 3 fields :
          data, left, right representing resp. an array of objects and left
          and right bounds of the slice.
:type s: dict
:param cmp: A comparison function, returning 0 if a == b, -1 is a < b, 1 if a > b
:type cmp: function
:return: Nothing

>>> import generate
>>> import element
>>> import numpy
>>> def cmp (x,y):
...    if x == y:
...       return 0
...    elif x < y:
...       return -1
...    else:
...       return 1
>>> t = numpy.array([element.Element(i) for i in [4,5,1,2,3,8,9,6,7]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> quicksort_slice(p,cmp)
>>> print(p['data'])
[1 2 3 4 5 6 7 8 9]
"""

if s['left'] < s['right'] :
    s1,s2 = partition(s,cmp)
    quicksort_slice(s1,cmp)
    quicksort_slice(s2,cmp)

这是doctests为此功能生成的输出：

File "C:\Users\Marion\Documents\S2\ASD\TP\tp2_asd\src\sorting.py", line 148, in __main__.quicksort_slice
Failed example:
    print(p['data'])
Expected:
    [1 2 3 4 5 6 7 8 9]
Got:
    [8 2 1 3 7 4 9 5 6]

我已经尝试插入调试打印语句来观察对分区函数的递归调用，似乎它无法正确交换值，但是我不知道如何解决此问题。任何帮助将不胜感激。

Edit：正如下面的一条评论所指出的，我只是忘了更新piv的值，该值在第一次调用该函数后并不总是为0。我也替换了：

for i in range(left,right+1):
if (cmp(s['data'][i] , s['data'][right]) != 1 ):
    swap(s['data'],i,j)
    j += 1

with

for i in range(left,right):
    if (cmp(s['data'][i] , s['data'][right]) != 1 ):
        swap(s['data'],i,j)
        j += 1
swap(s['data'],right,j)

Answer 1

试图在此之前关闭该线程，只是意识到我需要一个答案才能做到这一点。解决方案由jasonharper提供。正如jasonharper指出的那样，我“总是将索引0处的元素用作枢轴-即使0不在切片内”。