Мне нужно реализовать алгоритм быстрой сортировки для объекта «срез» для школьного проекта, объект среза - это кортеж с:
- полем «данных» (весь массив 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
Тесты для этой функции не завершаются неудачно, однако при вызове рекурсивной функции быстрой сортировки функция разделения работает не так, как ожидалось. Код для функции быстрой сортировки выглядит следующим образом:
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)