This course will introduce you to SQL Server Core 2016, as well as teach you about SSMS, data tools, installation, server configuration, using Management Studio, and writing and executing queries.

I'm interested in tracking the number of comparisons in some sort algorithms to compare them.

Im not exactly sure where this counter need to be incremented. If anyone has any help, thanks.

Some of the sorts I am using include the following.

INSERTION

-------------------------------------------------------------------------------------

template <class T>

void InsertionSort(T A[], int size)

{

for(int j=1; j<size; j++)

{

T key = A[j];

int i = j - 1;

while ((i >= 0) && (A[i] > key))

{

A[i+1] = A[i];

i -= 1;

}

A[i+1] = key;

}

}

HEAPSORT

------------------------------------------------------------------------------

template <class T>

void Heapsort(T A[], int size)

{

BuildHeap(A, size);

for(i=size; i>1; i--)

{

int tmp = A[0];

A[0] = A[i-1];

A[i-1] = tmp;

size--;

Heapify(A, 1, size);

}

}

template <class T>

void BuildHeap(T A[], int size)

{

for(i=size/2; i>0; i--)

Heapify(A, i, size);

}

template <class T>

void Heapify(T A[], int i, int size)

{

int l = 2 * i;

int r = 2 * i + 1;

int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])

largest = l;

else

largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])

largest = r;

if(largest != i)

{

int tmp = A[i-1];

A[i-1] = A[largest-1];

A[largest-1] = tmp;

Heapify(A, largest, heapsize);

}

}

Im not exactly sure where this counter need to be incremented. If anyone has any help, thanks.

Some of the sorts I am using include the following.

INSERTION

--------------------------

template <class T>

void InsertionSort(T A[], int size)

{

for(int j=1; j<size; j++)

{

T key = A[j];

int i = j - 1;

while ((i >= 0) && (A[i] > key))

{

A[i+1] = A[i];

i -= 1;

}

A[i+1] = key;

}

}

HEAPSORT

--------------------------

template <class T>

void Heapsort(T A[], int size)

{

BuildHeap(A, size);

for(i=size; i>1; i--)

{

int tmp = A[0];

A[0] = A[i-1];

A[i-1] = tmp;

size--;

Heapify(A, 1, size);

}

}

template <class T>

void BuildHeap(T A[], int size)

{

for(i=size/2; i>0; i--)

Heapify(A, i, size);

}

template <class T>

void Heapify(T A[], int i, int size)

{

int l = 2 * i;

int r = 2 * i + 1;

int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])

largest = l;

else

largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])

largest = r;

if(largest != i)

{

int tmp = A[i-1];

A[i-1] = A[largest-1];

A[largest-1] = tmp;

Heapify(A, largest, heapsize);

}

}

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Does this run into making the variable global? If so how is this done?

1. Use a global variable to count the number of comparisons

2. Create a property for the class and use that to store the count

3. Return the count from the Heapify function

Decide what you're after and have a go. Im not inclined to do too much until I can see you're trying to figure it out.

HEAPSORT

--------------------------

template <class T>

void Heapsort(T A[], int size)

{

BuildHeap(A, size);

for(i=size; i>1; i--)

{

int tmp = A[0];

A[0] = A[i-1];

A[i-1] = tmp;

size--;

Heapify(A, 1, size);

}

}

template <class T>

void BuildHeap(T A[], int size)

{

for(i=size/2; i>0; i--)

Heapify(A, i, size);

}

template <class T>

void Heapify(T A[], int i, int size)

{

int compares;

comapres +=2;

int l = 2 * i;

int r = 2 * i + 1;

int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])

largest = l;

else

largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])

largest = r;

if(largest != i)

{

int tmp = A[i-1];

A[i-1] = A[largest-1];

A[largest-1] = tmp;

Heapify(A, largest, heapsize);

}

return compares;

}

Since you call the Heapify function recursively, you should capture the return value of the Heapify (A, largest, heapsize) call and add that to you compares counter before returning it.

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialIf I capture it only from Heapify(A, largest, heapsize) won't that make the count on compares inaccurate?

Well sorry for the additional questions, i'm just very confused on how this is done. If I didnt mention im a beginning programmer so some things that are basically obvious to advanced programmers, are kinda new to me.

Thanks for your continued help.

Ben

template <class T>

void Heapsort(T A[], int size)

{

int count;

count = BuildHeap(A, size);

for(i=size; i>1; i--)

{

int tmp = A[0];

A[0] = A[i-1];

A[i-1] = tmp;

size--;

count += Heapify(A, 1, size);

}

printf("count = %d\n",count);

}

template <class T>

int BuildHeap(T A[], int size)

{

int count=0;

for(i=size/2; i>0; i--)

count += Heapify(A, i, size);

return count;

}

template <class T>

int Heapify(T A[], int i, int size)

{

int count;

count +=2;

int l = 2 * i;

int r = 2 * i + 1;

int largest = 0;

if(l <= heapsize && A[l-1] > A[i-1])

largest = l;

else

largest = i;

if(r <= heapsize && A[r-1] > A[largest-1])

largest = r;

if(largest != i)

{

int tmp = A[i-1];

A[i-1] = A[largest-1];

A[largest-1] = tmp;

count += Heapify(A, largest, heapsize);

}

return count;

}

C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get every solution instantly with premium.
Start your 7-day free trial.

INSERTION - Inside the while loop

HEAPSORT - Twice for each call of Heapify()

I dont think you really want comparisons of non-array elements.