I have written an assignment for a data structures class and am having trouble figuring out how to "Implement the main quicksort function that recursively sorts the subarrays formed by partitioning" which implies the recursion happens in the main quicksort function, while also " [having] a method signature of: quicksort(arr) — Sorts the list arr in-place and returns nothing"

I am struggling to see how I can implement it to the word of the assignment without doing silly things. The TA is a really really tough marker and needs everything to be to the letter of the assignment (even things not explicitly stated anywhere in the assignment or slides). All I am requesting is if what I am being asked is even technically possible.

Right now, I have the following:

def partition(arr, low, high):
    pivot = arr[high]
    pivIndex = high
    while True:
        while arr[low] <= pivot and low != high:
            low += 1
        while arr[high] >= pivot and low != high:
            high -= 1
        if low == high:
            arr[low], arr[pivIndex] = arr[pivIndex], arr[low]
            return low
        else:
            arr[low], arr[high] = arr[high], arr[low]
            
def quicksort(arr, low, high):
    #the subarray has strictly less than two elements
    if high <= low:
        return

    pivot = round(random.random() * (high - low) + low)

    arr[pivot], arr[high] = arr[high], arr[pivot]

    pivot = partition(arr, low, high)

    quicksort(arr, pivot + 1, high)
    quicksort(arr, low, pivot - 1)

    return arr

I have written an assignment for a data structures class and am having trouble figuring out how to "Implement the main quicksort function that recursively sorts the subarrays formed by partitioning" which implies the recursion happens in the main quicksort function, while also " [having] a method signature of: quicksort(arr) — Sorts the list arr in-place and returns nothing"

I am struggling to see how I can implement it to the word of the assignment without doing silly things. The TA is a really really tough marker and needs everything to be to the letter of the assignment (even things not explicitly stated anywhere in the assignment or slides). All I am requesting is if what I am being asked is even technically possible.

Right now, I have the following:

def partition(arr, low, high):
    pivot = arr[high]
    pivIndex = high
    while True:
        while arr[low] <= pivot and low != high:
            low += 1
        while arr[high] >= pivot and low != high:
            high -= 1
        if low == high:
            arr[low], arr[pivIndex] = arr[pivIndex], arr[low]
            return low
        else:
            arr[low], arr[high] = arr[high], arr[low]
            
def quicksort(arr, low, high):
    #the subarray has strictly less than two elements
    if high <= low:
        return

    pivot = round(random.random() * (high - low) + low)

    arr[pivot], arr[high] = arr[high], arr[pivot]

    pivot = partition(arr, low, high)

    quicksort(arr, pivot + 1, high)
    quicksort(arr, low, pivot - 1)

    return arr

• python
• algorithm
• quicksort

Share Improve this question Follow edited Nov 18, 2024 at 17:52 Gabriel Denney-Martell asked Nov 18, 2024 at 17:49 Gabriel Denney-MartellGabriel Denney-Martell 111 bronze badge 5

• 3 Think about the built-in list.sort() method which sorts the list in place and returns None. That is what your quicksort algorithm should do. Modify the array in place, but it doesn't need to return any values. – Frank Yellin Commented Nov 18, 2024 at 17:54
• In Python, generally functions either return a new object (like sorted()) or they modify the existing object in place (like list.sort()). In the latter case they don't return the object that was updated. – Barmar Commented Nov 18, 2024 at 18:02
• First, what you are trying to achieve is technically feasible. As a hint: In python splitting and merging lists is very natural, so it might be easier to mentally work out the algorithm not working on the whole array all the time. Another hint: There is no need for returns in your recursion if the method works in place. – André Commented Nov 18, 2024 at 18:04
• You might have to show us the full "letter of the assignment", and exactly how they defined "in-place". – no comment Commented Nov 18, 2024 at 18:13
• Does the assignment really say that the main quicksort function is the function that is called recursively, or does it say that it performs the algorithm using recursion? I only see the second requirement: you should use recursion, and the main function should have a specific signature. I see no problem with that. – trincot Commented Nov 18, 2024 at 19:09

Add a comment  | 

1 Answer 1

Sorted by: Reset to default 1

Try to implement helper function and call it recursively within your main quicksort(arr) function

Something like this:

def quicksort(arr):

    def partition(low, high):
        ...

    def quicksort_recursive(low, high):

        if high <= low:
            return

        pivot = round(random.random() * (high - low) + low)
        arr[pivot], arr[high] = arr[high], arr[pivot]
        
        pivot = partition(low, high)
        
        quicksort_recursive(low, pivot - 1)
        quicksort_recursive(pivot + 1, high)


    quicksort_recursive(0, len(arr) - 1)

Lists in Python are mutable, so there is no need to return arr from your function if you change it in-place