CODEWITHSUNDEEP
pythonrecursionquickselect
Fionnuala
Fionnuala

Reputation: 19

Calls value not incrementing as intended

I am writing a program meant to find the average number of recursive calls it takes to run quickselect, and I have added a counter "calls" to keep track of the number of recursive calls. I have it incrementing every time quickselect is called again, but when I use a larger number for main the number of calls quickly goes into exponential territory. I would like for main to return the average number of calls, and I know the number I am getting is wrong but I cannot tell why. Any suggestions would be welcomed.


import numpy
import numpy as np
import random

def main(trials,k):
    i = 0;
    hold = []
    calls = -1;
    while i < trials:
        generate(hold, 75)
        calls = calls + quickselect(hold, k, calls)
        i = i + 1
    print(calls/trials)


def generate(l,n):
    for i in range(n):
        r=random.randint(0,n)
        if r not in l:
            l.append(r)


def quickselect(l, k, calls) :
    #l is the list of the numbers
    #we are finding the kth largest element
    calls = calls + 1
    length = len(l)
    pivotselect = numpy.random.randint(0,length,1)

    l = numpy.array(l)
 
    #print(pivotselect)
    #print(l[pivotselect])
    pivot = l[pivotselect]
    #print("this is the pivot", pivot)
    
    # Pick a random pivot element from the list, each
    # equally likely
    l_small = []
    l_big = []

    smalltrack = 0
    bigtrack = 0
    i = 0
    ispivot = 0
    while i < length:
        #print(i)
        compare = l[i]
        if compare < pivot:
            l_small.append(compare)
            smalltrack = smalltrack + 1
            #print(l_small)
        elif l[i] > pivot:
            l_big.append(compare)
            bigtrack = bigtrack + 1
        else:
            ispivot = ispivot + 1
            #print(compare, "ispivot is now", ispivot)
        i = i + 1
    #print("ispivot is", ispivot)
    #print(len(l_small), "small then big", len(l_big))
    checker = len(l_small) + len(l_big)
    #print(checker)
    checker = checker + ispivot
    #print(checker)
    assert(length == checker)
    l_big = numpy.array(l_big)
    l_small = numpy.array(l_small)
    #print("check 1")


    if k <= len(l_big):
        
    # kth largest must be in l_big
    
        res = quickselect(l_big, k, calls)
        #print("check 2")
        #calls = calls + 1
        return res
    elif k > len(l_big) + 1:
        
    # kth largest must be in l_small
    
        res = quickselect(l_small, k - len(l_big) - 1, calls)
        #print("check 3")
        #calls = calls + 1
        return res
    else:
        #print("check 4")
        #print("calls", calls)
        print(calls)
        return calls

Upvotes: 0

Views: 18

Answers (1)

Frank Yellin
Frank Yellin

Reputation: 11283

As your code is written, you are more than doubling calls each time you call quickselect. You're passing it the current value, incrementing it by however many times quickselect is called, and then adding that new value of calls to your old value.

You need to get rid of either one addition or the other. You can either:

  • Call quickselect in main with the calls argument being 0. Continue to add the return result to calls.

  • You can just call quickselect(hold, k, calls) and not add the return value to calls.

Upvotes: 0

Related Questions