CODEWITHSUNDEEP
pythonpython-3.x
Henry Krinkle
Henry Krinkle

Reputation: 9

Python variable confusion

I new to Python and I am reading about Quickselect algorithm and found some helpful code. I do not understand how pivotIndex is declared twice and not over written. I would like some clarification on how Python is not over writing pivotIndex.

I removed the second declaration of pivotIndex and I receive random output.

def qselect(k, array):
    n = k-1

    def partition(left, right, pivotIndex):
        pivotValue = array[pivotIndex]

        array[pivotIndex], array[right] = array[right], array[pivotIndex]
        storeIndex = left
        for i in range(left, right):
            if array[i] < pivotValue:
                array[storeIndex], array[i] = array[i], array[storeIndex]
                storeIndex += 1

        array[right], array[storeIndex] = array[storeIndex], array[right]
        return storeIndex

    def select(left, right):
        if left == right:
            return array[left]
        pivotIndex = random.randint(left, right)
        pivotIndex = partition(left, right, pivotIndex)

        if n == pivotIndex:
            return array[n]
        elif n < pivotIndex:
            return select(left, pivotIndex-1)
        else:
            return select(pivotIndex+1, right)

    return select(0, len(array)-1)

Upvotes: 0

Views: 54

Answers (1)

Nisan Abeywickrama
Nisan Abeywickrama

Reputation: 184

It is overwritten.

pivotIndex = random.randint(left, right)
pivotIndex = partition(left, right, pivotIndex)

Here what happens is that we find a random value for pivotIndex within the range of the values of left and right. we use that value as a parameter to the function partition and assign the returned value to pivotIndex.

Upvotes: 2

Related Questions