1

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
Improve this question
11
  • 1
    Where do you assign count? Commented Jul 14, 2017 at 4:27
  • right after def QuickSort(lst): Commented Jul 14, 2017 at 4:29
  • Except it's nowhere to be seen in the code that you've posted here... Commented Jul 14, 2017 at 4:30
  • At any rate, you can keep track of the count by adding a second parameter to your QuickSort function, although I'm not sure why you couldn't simply use len(lst) instead of count. Commented Jul 14, 2017 at 4:32
  • 1
    @SwifthsNamesake Oh, I'm sorry to have made confusion. I also assumed that there is a part of code to count. Just give me a second to make it clear. Commented Jul 14, 2017 at 4:49

3 Answers 3

Reset to default
3

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
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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)
Improve this answer

4 Comments

I think you understood what I asked. It helps me a lot!! Thank you Jay!
@WonKim No problem! Please accept and upvote if this helped :)
Is upvote the upward arrow besides your code? I'm a newbie. How can I accept your help?
@WonKim This counts the number of recursive iterations, not the number of comparisons. But maybe that's what the OP wanted?
-2

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.

Improve this answer

5 Comments

That's a really bad idea.
Actually I've been trying not to use global variable.
@SwiftsNamesake why is this a bad idea?
Global variable could occur confusions.
Using global variables is a great way of ending up with entangled and unreusable code. For instance, you'd have to reset the global variable manually every time you wanted to use the sorting function.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.