Count number of element comparisons when sorting

Question

I'm doing a quick sort algorithm. And my question is how can i count number of comparisons when sorting. And also the second question. How can i choose the "pivot" element? Foe example i want to my first element to be pivot element.

import random 
def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 

    for j in range(low , high): 

        # If current element is smaller than or 
        # equal to pivot 
        if   arr[j] <= pivot: 

            # increment index of smaller element 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 

# The main function that implements QuickSort 
# arr[] --> Array to be sorted, 
# low  --> Starting index, 
# high  --> Ending index 

# Function to do Quick sort 
def quickSort(arr,low,high): 
    if low < high: 

        # pi is partitioning index, arr[p] is now 
        # at right place 
        pi = partition(arr,low,high) 

        # Separately sort elements before 
        # partition and after partition 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high) 

# Driver code to test above 
arr = random.sample(range(0, 9999), 1000)
n = len(arr) 
quickSort(arr,0,n-1) 
print ("Sorted array is:") 
for i in range(n): 
    print ("%d" %arr[i]),

Do note that the way of selecting pivot changes the number of comparisons. So if this is a challenge problem, stick to whatever definition of the pivot given. — Master Chief, Apr 20 '19 at 05:48

score 1 · Answer 1 · answered Apr 19 '19 at 15:35

First of all, You can count the number of comparisons by this line:

        if   arr[j] <= pivot:

Because it is only comparisons(for element) in whole quick sort algorithm. You can count how many time this line executed by a single variable.

Secondly, You didn't need to choose the pivot element. Because pivot element is automatically set by this line

    pivot = arr[high]

It is the original algorithm. You can choose manually and also need to redesign the algorithm.

score 0 · Answer 2 · answered Apr 19 '19 at 15:36

For the first question, You can define a global variable and increment it whenever you want.

count = 0  # define it in global scope

def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 

    for j in range(low , high): 

        # If current element is smaller than or 
        # equal to pivot 

        count += 1  # increment wherever you want

        if   arr[j] <= pivot: 

            # increment index of smaller element 
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 

    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 )

You can access its correct value after doing the sort.

For the second question, the selection of pivot is of your choice. You are actually doing this now:

pivot = arr[high] # pivot

You are using last element of sub-array to be pivot. You can use arr[low] to choose the first element.

Note: Welcome to StackOverflow community. There are lots of questions that seem to be a subject that lots of other users may want to ask, or have asked before! The answers of the others to similar questions might solve your problem. You can also look at these SO answers, to get more info about counting number of comparisons and selecting pivot: For first question, For second question

Count number of element comparisons when sorting

2 Answers2