I've been trying to debug my code for some hours and haven't had a headway with it. I love if anyone could help me, I just started learning algorithms
def quicksort(arr):
start = 0
end = len(arr) - 1
quick_sort(arr, start, end)
def quick_sort(arr, start, end):
if start < end:
pindex = partition(arr, start, end)
quick_sort(arr, start, pindex)
quick_sort(arr, pindex+1, end)
def partition(arr, start, end):
pivot = arr[end]
i = start
for j in range(start, end):
if arr[j]<= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[end] = pivot, arr[i]
return i;
when i run it with quicksort([6,4,5,4,2,43,1,4,532,515,243,3,34,5,12,24,234,45,6,457,5])
I get
RecursionError: maximum recursion depth exceeded in comparison
and I'm quite sure I used a base case at the beginning of the quick_sort function
Your quicksort
and quick_sort
routine use, as parameters, the index of the first and of the last item in the sub-array to be sorted. After you partition the sub-array, you sort two parts. However, you include the pivot element of the partition in the first part in your call quick_sort(arr, start, pindex)
. You should leave the pivot element out, so use quick_sort(arr, start, pindex-1)
.
Give that a try. You have no comments so it is difficult to debug your program. Your example input is also far too large and difficult to debug easily. Try an empty array, then an array with one element, then some arrays with two elements, and so on, to catch your errors.
With that one change, your program now passes all my tests.