Как подсчитать сравнения, сделанные в Quick Sort

Question

Итак, у меня есть полностью написанный и рабочий код для быстрой сортировки, но вместо того, чтобы возвращать отсортированный список, я пытаюсь вернуть количество сравнений. Я не уверен, где мне поставить счетчик для подсчета количества сделанных сравнений. Любая помощь приветствуется!

def quickSort(alist):
   quickSortHelper(alist,0,len(alist)-1)

def quickSortHelper(alist,first,last):
   if first<last:

       splitpoint = partition(alist,first,last)

       quickSortHelper(alist,first,splitpoint-1)
       quickSortHelper(alist,splitpoint+1,last)


def partition(alist,first,last):
   pivotvalue = alist[first]

   leftmark = first+1
   rightmark = last

   done = False
   while not done:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

       if rightmark < leftmark:
           done = True
       else:
           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

   temp = alist[first]
   alist[first] = alist[rightmark]
   alist[rightmark] = temp


   return rightmark   #returns the sorted list

Answer 1

Эти два цикла - единственные места, где вы фактически сравниваете значения из массива:

       while leftmark <= rightmark and alist[leftmark] <= pivotvalue:
           leftmark = leftmark + 1

       while alist[rightmark] >= pivotvalue and rightmark >= leftmark:
           rightmark = rightmark -1

, поэтому вы должны добавить counter += 1 внутри обоих циклов. Не забудьте инициализировать счетчик на 0 и объявить его глобальным.

Кстати, leftmark = leftmark + 1 можно записать как leftmark += 1, и эта часть:

           temp = alist[leftmark]
           alist[leftmark] = alist[rightmark]
           alist[rightmark] = temp

не требует временная переменная:

           alist[rightmark],alist[leftmark] = alist[leftmark],alist[rightmark]