I'm trying to implement a 3 way partition quick sort code in Python.
My code takes in 2 lines:
My code worked for the following inputs:
However, when it is tested with the following input: 10, 10 9 8 7 6 5 4 3 2 1
My code does not sort the array of integers properly?
May I know why my code does not work for the last case?
This is my code:
def partition3(a, l, r):
#write your code here
pivot = a[r]
i = l
j = l - 1
iterable_length = r
while i <= iterable_length:
if a[i] < pivot:
j += 1
a[i], a[j] = a[j], a[i]
elif a[i] > pivot:
a[i], a[iterable_length] = a[iterable_length], a[i]
iterable_length -= 1
i += 1
return j, iterable_length+1
def randomized_quick_sort(a, l, r):
if l >= r:
return
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
#use partition3
# m = partition2(a, l, r)
m1, m2 = partition3(a, l, r)
randomized_quick_sort(a, l, m1);
randomized_quick_sort(a, m2, r);
if __name__ == '__main__':
input = sys.stdin.read()
n, *a = list(map(int, input.split()))
randomized_quick_sort(a, 0, n - 1)
for x in a:
print(x, end=' ')
The problem seems to be here:
k = random.randint(l, r)
a[l], a[k] = a[k], a[l]
You are getting a random index k
and using it to swap two elements a[l]
and a[k]
randomly. Removing the two lines should give the correct output only looks right in certain circumstances.
I'm assuming you're looking to create a random pivot point, in which case you should use the random index as a pivot inside the partition3
function.
Edit: The problem was not processing/skipping the new element at a[i]
after swapping inside a[i] > pivot:
. It should be:
elif a[i] > pivot:
a[i], a[iterable_length] = a[iterable_length], a[i]
iterable_length -= 1
# don't forget to process new element at a[i]
i -= 1