CODEWITHSUNDEEP
python-3.x
Won Kim
Won Kim

Reputation: 109

How to count in recursive function?

The code below is quicksort in Python. How do I count how many times comparison operates in the algorithm?

Although I assign count = 0 at first, it is reset to 0 because of recursion.

def QuickSort(lst):
    if len(lst) > 1:
        pivot_idx = len(lst) // 2
        smaller_nums, larger_nums = [], []

        for idx, num in enumerate(lst):
            if idx != pivot_idx:
                if num < lst[pivot_idx]:
                    smaller_nums.append(num)

                else:
                    larger_nums.append(num)

        QuickSort(smaller_nums)
        QuickSort(larger_nums)
        lst[:] = smaller_nums + [lst[pivot_idx]] + larger_nums

    return lst

Upvotes: 1

Views: 385

Answers (3)

developer_hatch
developer_hatch

Reputation: 16224

Edit, I was erased this answer because I thought it was incorrect, but I think it was correct after all

as suggested, I think also is better if the function is stateless: You can return the lst and the number of calls:

def QuickSort(lst, ncalls=0):
  ncalls += 1

  if len(lst) > 1:
    pivot_idx = len(lst) // 2
    smaller_nums, larger_nums = [], []

    for idx, num in enumerate(lst):
        if idx != pivot_idx:
            if num < lst[pivot_idx]:
                smaller_nums.append(num)

            else:
                larger_nums.append(num)
    lst1, ncalls = QuickSort(smaller_nums, ncalls)
    lst1, ncalls = QuickSort(larger_nums, ncalls)
    lst[:] = smaller_nums + [lst[pivot_idx]] + larger_nums



  return lst,ncalls


QuickSort([1,3,52,4,6,5])
=> [1, 3, 4, 5, 6, 52],7

Upvotes: 3

Jay S.
Jay S.

Reputation: 1327

Pass it recursively as parameter:

def QuickSort(lst, count=0):
    if len(lst) > 1:
        pivot_idx = len(lst) // 2
        smaller_nums, larger_nums = [], []

        for idx, num in enumerate(lst):
            if idx != pivot_idx:
                if num < lst[pivot_idx]:
                    smaller_nums.append(num)

                else:
                    larger_nums.append(num)

        count = QuickSort(smaller_nums, count+1)[1]
        count = QuickSort(larger_nums, count+1)[1]
        lst[:] = smaller_nums + [lst[pivot_idx]] + larger_nums


    return (lst,count)

Upvotes: 1

Ananda
Ananda

Reputation: 3272

Assign count as a global variable and set it to zero. That is, set count=0 outside the definition of the function and increment it every time you compare.

Upvotes: -2

Related Questions