Я работал над этим разделом быстрой сортировки в течение нескольких дней и до сих пор не могу это исправить.Я попытался отладить его с помощью отпечатков, чтобы увидеть, как развиваются разделы при вызове основной быстрой сортировкой, но все еще не могу понять, как это исправить.Показаны документы, подтверждающие контекст, приносим извинения, если это не актуально.
Он работает на некоторых примерах, но не на других и не может понять, почему.Любое понимание и помощь высоко ценится.
def partition (s, cmp):
>>> import generate
>>> import numpy
>>> import element
>>> 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 [3, -8, 2 , -2, 3, 7, 9, 1, -1, 7]])
>>> p = {'left':0,'right':len(t)-1,'data':t}
>>> p1,p2 = partition(p,cmp)
>>> p1['data'][p1['left']:p1['right']+1]
array([-8, 2, -2, 3, -1, 1], dtype=object)
>>> p2['data'][p2['left']:p2['right']+1]
array([9, 7, 7], dtype=object)
"""
a = s["data"] #whole array
lp = s["left"]+1 #left pointer
rp = s["right"] #right pointer
pivot = a[lp-1] #pivot is element of index lp=0 in slice
while lp <= rp:
if cmp(a[lp], pivot) <= 0: #lp is already on the correct side since it's <= to pivot
a[lp-1] = a[lp]
lp += 1 #moving towards center
else:
a[lp], a[rp] = a[rp], a[lp] #taking advantage of python's easy swap
rp -= 1 #moving towards center
a[rp] = pivot #replacing pivot in the end
lslice = {"data" : a, "left" : s["left"], "right" : rp-1} #<pivot
rslice = {"data" : a, "left" : rp+1, "right" : s["right"]} #>pivot
return (lslice,rslice)