I am using the quicksort algorithm in Python whereby it swaps the values in place. My question is how does Python know I am using the same list in the Partition and quicksort function?
As you can see below in my code for quicksort, the swap for the position of the values only happens in the partition function. Yet, without needing to do a return of the list to the quicksort function, it knows that I swapped the position of the values for the list in partition, thus printing the sorted list.
def quicksort(lst, start = 0, end = None):
if end is None:
end = len(lst) - 1
if start >= end:
return
p = partition(lst, start, end)
quicksort(lst, start, p-1)
quicksort(lst, p+1, end)
def partition(lst, start, end):
pivot = lst[start]
low = start + 1
high = end
while low <= high:
while lst[low] <= pivot:
low += 1
while lst[high] >= pivot:
high -= 1
if low <= high:
lst[low], lst[high] = lst[high], lst[low]
low += 1
high -= 1
lst[start], lst[high] = lst[high], lst[start]
return high
numbers = [7, 6, 2, 4, 9, 1000]
quicksort(numbers)
print(numbers)
Please accept my humble apologies if I have asked something redundant as I could not find anything regarding this. I am currently learning about algorithms through team treehouse, but they don't seem to have anything about it besides the video about quicksort which doesn't explain much. If you know of somewhere that has more information on this, your help will be greatly appreciated if you could share it with me! Thank you.
This is because values are passed by reference in python. When you pass your lst to your partition function, you are actually passing a reference to your list in your quicksort function, and not a copy of the list.