Подсчитайте количество компонентных сравнений в алгоритме быстрой сортировки.

Я пытаюсь подсчитать количество сравнений, которые мой алгоритм быстрой сортировки выполняет для размера массива 500. Я знаю, что лучший вариант быстрой сортировки с разделением — это nlogn-n + 1. Таким образом, для размера массива 500 наилучшее число сравнений компонентов будет примерно 3983. Однако, когда я запускаю свой код, я получаю 2400 сравнений или около того, в зависимости от массива, который генерирует случайная функция. Я неправильно подсчитываю количество компонентных сравнений? Пожалуйста помоги.

#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;int count_500 = 0;

int partition(int *S,int l, int u);
void swap(int &val1, int &val2);
void Quicksort(int S[],int low, int hi);
void exchange(int list[], int p, int q);
int median_of_3(int list[], int p, int r);
void Quicksort_M3(int S[], int low, int hi);
int main()
{
int S1_500[500];
int S2_500[500];
int S3_500[500];

int S1_200[200];
int S2_200[200];
int S3_200[200];

int S1_8[8];
int S2_8[8];
int S3_8[8];

srand ( time(NULL) );for(int i=0; i<500; i++)
{
S1_500[i] = rand()%1000;
S2_500[i] = rand()%1000;
S3_500[i] = rand()%1000;
}

for(int i=0; i<200; i++)
{
S1_200[i] = rand()%500;
S2_200[i] = rand()%500;
S3_200[i] = rand()%500;
}

for(int i=0; i<8; i++)
{
S1_8[i] = rand()%100;
S2_8[i] = rand()%100;
S3_8[i] = rand()%100;
}

Quicksort(S1_500,0,499);
for(int i=0; i<500; i++)
{
cout << S1_500[i] << endl;
}

cout << "Number of component wise comparisons is: " << count_500 << endl;
}int partition(int *S,int l, int u)
{
int x = S[l];
int j = l;
for(int i=l+1; i<=u; i++)
{
if(S[i] < x)
{
count_500++; // Count the component wise comparison
j++;
swap(S[i],S[j]);
}
}
int p = j;
swap(S[l],S[p]);
return p;
}

void swap(int &val1, int &val2)
{
int temp = val1;
val1 = val2;
val2 = temp;
}

void Quicksort(int S[],int low, int hi)
{
if (low < hi)
{
int p = partition(S,low,hi);
Quicksort(S,low,p-1);
Quicksort(S,p+1,hi);
}
}