pythonpython-3.xpyscripterquickselect

Python based quickselect Implementation resulting in error


I have small python code that implements the quickselect discussed here.

import random
def Quickselect(A, k):
    if not A:
        return
    pivot = random.choice(A)

    i = 0
    A1 = []
    A2 = [] # Two new arrays A1, A2 to store the split lists
    for i in range(len(A)):
        if A[i] < pivot :
            A1.append(A[i])
        else:
            A2.append(A[i])

    if k < len(A1):
        return Quickselect(A1, k)
    if k > len(A) - len(A2):
        return Quickselect(A2, k-(len(A) - len(A2)))
    else:
        return pivot
pass
def main():
    A = [45,1,27,56,12,56,88]
    print(Quickselect(A,2))
pass

I seem to be getting an randrange error. Is something amiss?

Edit: Implemented random.choice instead of random.randint. The above code seems to work fine. Thanks to User Blender.


Solution

  • Your error occurs because randrange breaks when the range is empty (i.e. randrange(1, 1)).

    Use random.choice instead and change k <= len(A1) to k < len(A1):

    def quick_select(A, k):
        pivot = random.choice(A)
    
        A1 = []
        A2 = []
    
        for i in A:
            if i < pivot:
                A1.append(i)
            elif i > pivot:
                A2.append(i)
            else:
                pass  # Do nothing
    
        if k <= len(A1):
            return Quickselect(A1, k)
        elif k > len(A) - len(A2):
            return Quickselect(A2, k - (len(A) - len(A2)))
        else:
            return pivot