CODEWITHSUNDEEP
quicksortshallow-copy
maolmedilla
maolmedilla

Reputation: 19

Confusion with quicksort algorithm and shallow copies of list

def quicksort(numbers:list):
    if len(numbers) > 1:
    
        pivot_element = numbers[-1]

        i = 0
        j = len(numbers)-2

        done = False

        while not done:

            if i>j:
                done = True

            elif numbers[i] <= pivot_element:
                i+=1
            

            elif numbers[j] >= pivot_element:
                j-= 1
        

            else:
                numbers[i],numbers[j] = numbers[j],numbers[i]



        numbers[i],numbers[-1] =  numbers[-1],numbers[i]
    
        
    
        quicksort(numbers[:i])
        quicksort(numbers[i+1:])
    
    return numbers

Hello everyone,

I'm trying to write a quicksort algorithm,but I'm failing to understand why the recursive part of it is not transforming the rest of my list. From what I understood, It's something related with the fact that the shallow copy is not 'saving' the original list, and I should use a deep copy. Is there any possible way I can do that without importing other libraries?

Thank you for your time.

Upvotes: 0

Views: 32

Answers (1)

rcgldr
rcgldr

Reputation: 28921

numbers[:i] and numbers[i+1:] are copies of numbers[]. Changing those copies will not change numbers[].

Use a helper function that passes numbers[] and indexes to the actual function:

    def quicksort(numbers):
        quicksortr(numbers, 0, len(numbers-1)
        ...

    def quicksortr(numbers, lo, hi):
        ...
        quicksort(numbers, lo, i)
        quicksort(numbers, i+1, hi)
        ...

Upvotes: 0

Related Questions