Подсчет количества сравнений элементов при сортировке

Question

Я делаю алгоритм быстрой сортировки. И мой вопрос, как я могу посчитать количество сравнений при сортировке. А также второй вопрос. Как я могу выбрать элемент "pivot"? Например, я хочу, чтобы моим первым элементом был элемент разворота.

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]),

Answer 1

Для первого вопроса Вы можете определить глобальную переменную и увеличивать ее в любое время.

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 ) 

Вы можете получить доступ к ее правильному значению после выполнения сортировки.

По второму вопросу , выбор точки разворота на ваш выбор.Вы на самом деле делаете это сейчас:

pivot = arr[high] # pivot

Вы используете последний элемент подмассива для поворота.Вы можете использовать arr[low] для выбора первого элемента.

Примечание: Добро пожаловать в сообщество StackOverflow.Есть много вопросов, которые, кажется, являются предметом, который многие другие пользователи, возможно, захотят задать, или задавали раньше!Ответы других на подобные вопросы могут решить вашу проблему.Вы также можете посмотреть на этих SO ответов, чтобы получить больше информации о подсчете количества сравнений и выбора пивота: Для первого вопроса Для второго вопроса

Answer 2

Прежде всего, Вы можете посчитать количество сравнений по этой строке:

        if   arr[j] <= pivot: 

Потому что это всего лишь сравнения (для элемента) во всем алгоритме быстрой сортировки. Вы можете посчитать, сколько раз эта строка выполнялась одной переменной.

Во-вторых, Вам не нужно было выбирать элемент поворота. Потому что элемент pivot автоматически устанавливается этой строкой

    pivot = arr[high] 

Это оригинальный алгоритм. Вы можете выбрать вручную, а также необходимо изменить алгоритм.