I have to implement a quicksort algorithm on a "slice" object for a school project, the slice object is a tuple with :
The partition function code goes as follows :
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
The doctests for this function do not fail, however when calling the quicksort recursive function, the partition function does not behave as expected.The code for the quicksort function is as follows :
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)
This is the output produced by the doctests for this function:
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]
I have tried to insert debug print statements to observe the recursive calls to the partition function and it seems it doesn't swap values properly but I don't know how to fix this. Any help would be much appreciated.
Edit : As pointed out by one of the comments below, I simply forgot to update the value of piv, which is not always 0 after the first call to the function. I also replaced :
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)
Tried to close this thread before and just realised that I needed an answer to do this. The solution was provided by jasonharper. As pointed out by jasonharper I was "always using the element at index 0 as your pivot - even if 0 isn't within the slice".