快速排序函数不会产生预期的输出，但分区函数会产生 (python)

Question

我必须在学校项目的 "slice" 对象上实施快速排序算法，切片对象是一个元组：

一个'data'字段（要排序的整个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

这个函数的doctests没有失败，但是当调用快速排序递归函数时，分区函数并不像expected.The快速排序函数的代码如下：

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]

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

编辑： 正如下面的一条评论所指出的，我只是忘记更新 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

和

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 所指出的，我是 "always using the element at index 0 as your pivot - even if 0 isn't within the slice"。

快速排序函数不会产生预期的输出，但分区函数会产生 (python)

Quicksort function does not produce the expected output, though partition function does (python)

python

quicksort