1. ## Counting sorting operations

Hi,

I'm trying to count the number of operations it takes a certain sorting algorighm (in this case a shell sort) to sort arrays of different sizes (numbers in the arrays are randomly generated).
Here is my code:
Code:
```#include <iostream>
#include <string>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <stdlib.h>
#include <time.h>

using namespace std;
void fill_array(int A[], int size);
int shell_sort(int A[], int size);
void print_array(int A[], int size);

int main()
{
const int size = 10000;
int A [size];
int B [21] = {1,2,3,4,5,6,7,8,9,10,20,30,40,70,100,200,300,500,1000,2000,5000};
int new_size = 0;

srand ((unsigned int)time((time_t)0));

for (int i = 0; i < 21; i++)
{
new_size = B[i];

fill_array(A, new_size);
shell_sort(A, new_size);
//int count = shell_sort(A, new_size);
//cout<<count<<endl;
}
return 0;
}
int shell_sort(int A[], int size)
{
int count = 0;
int i, j, increment, temp;
increment = size / 2;

while (increment > 0)
{
for (i = increment; i < size; i++)
{
j = i;											count++;
temp = A[i];									count++;

while ((j >= increment) && (A[j-increment] > temp))
{
A[j] = A[j - increment];					count++;
j = j - increment;							count++;
}
A[j] = temp;									count++;
}

if (increment == 2)
increment = 1 &&								count++;
else
increment = (int) (increment / 2.2) &&			count++;
}
cout.width(4);
cout<<size<<": ";
cout<<count<<endl;
return count;
}
void fill_array(int A[], int size)
{
int first_rand = 0;

while(first_rand < size)
{
A[first_rand] = rand() % 1000;
first_rand++;
}
}```
The problem:
If i print the output of the number of operations (count) in the for loop in main, i get results such as these (The left column is the size of the array, and the right column is how many operations it takes to sort the array):
Code:
```   1:  0
2:  3
3:  6
4:  16
5:  22
6:  25
7:  31
8:  34
9:  40
10:  43
20:  88
30:  133
40:  178
70:  313
100:  448
200:  898
300:  1348
500:  2248
1000:  4498
2000:  8998
5000:  22498```
Now, if i print count and the end of the sorting function, i get results such as these:
Code:
```   1: 0
2: 3
3: 10
4: 18
5: 30
6: 39
7: 43
8: 56
9: 70
10: 61
20: 220
30: 427
40: 692
70: 1735
100: 3730
200: 15362
300: 31148
500: 85822
1000: 338354
2000: 1341068
5000: 8419422```
So, when i print count in the sorting function, the numbers are alot higer than when count is printed in the for loop in main. So, i'm not sure what is going on, and which count is correct.

*Note, when i change where i output count (in main or in the sorting function) i comment out the other count.

2. shell_sort(A, new_size);
//int count = shell_sort(A, new_size);
I imagine you're calling shell_sort twice when you uncoment that line. The second time in main it will be already sorted and so the operation counts will of course be lower as less work needs to be done.

Why doesn't fill_array simply use a for-loop?

3. You have a very odd way of counting operations: "&& count++"
Why would you count the j = i; line but not the expression in the inner while loop which is far more complicated?
I prefer to count operations by creating a class to wrap the key type and provide comparison and assignment operators which do the counting work. This also allows it to be done non-intrusively. This is how I measure the 60+ array sorting algorithms I have mentioned on my website. (link in sig)

4. Thanks for the fix, i didn't realize i was calling it twice.

"You have a very odd way of counting operations: "&& count++"
I did this so i didn't have to put brackets around the material in the if else statements.

"Why would you count the j = i; line but not the expression in the inner while loop which is far more complicated?"
So, i'm trying to see how many operations it takes to sort the array.
I don't see what i'm not counting. Every line seems to be counted, unless i'm not seing something.

Code:
```int shell_sort(int A[], int size)
{
int count = 0;
int i, j, increment, temp;
increment = size / 2;

while (increment > 0)
{
for (i = increment; i < size; i++)
{
j = i;											count++;
temp = A[i];									count++;

while ((j >= increment) && (A[j-increment] > temp))
{
A[j] = A[j - increment];					count++;
j = j - increment;							count++;
}
A[j] = temp;									count++;
}

if (increment == 2)
increment = 1 &&								count++;
else
increment = (int) (increment / 2.2) &&			count++;
}

return count;
}```
Btw, do you by chance know how i could set the cursor position back to the beginning, so that i could output another set of number to the right of the ones above, instead of below.

Thanks

5. Originally Posted by Cpro
"Why would you count the j = i; line but not the expression in the inner while loop which is far more complicated?"
So, i'm trying to see how many operations it takes to sort the array.
I don't see what i'm not counting. Every line seems to be counted, unless i'm not seing something.
This line is doing a lot of work:
Code:
`			while ((j >= increment) && (A[j-increment] > temp))`
Whereas j = i; is a simple copy from one register to another. Even the i < size comparison in the for-loop does more work than that.
What's more, without measuring the operations by wrapping it in a class and providing the operators as I mentioned, you can't easily measure that line because the second part of the && expression is only executed i the first part is true.
In general it isn't worth counting every trivial line of code anyway, but the comparisons are worth counting.
Btw, do you by chance know how i could set the cursor position back to the beginning, so that i could output another set of number to the right of the ones above, instead of below.
There are OS specific ways of doing that, but the better option is to store your results in arrays, and then output the whole lot at once, outputting the first element from each array on each line.

6. "You have a very odd way of counting operations: "&& count++"
I did this so i didn't have to put brackets around the material in the if else statements.
I also think that you have a problem with operator precedence.

Code:
`increment = 1 && count++;`
This does not assign 1 to increment and increase count - it assigns the result of 1 && count++ (can be 1 or 0) to increment.

When testing sorting algorithms I suggest you write a function that tests that the array is indeed in a sorted order after sorting. I wouldn't be surprised if it turned out that the sort algorithm doesn't work correctly.

I also second the idea of using a special class that counts operations done with it, rather than modifying the algorithm itself. (You can use templates to make the function sort different types.)

-----------------
Avoiding brackets around single-line if-else blocks is not a worthy goal anyway. It is often recommended to put the braces there anyway, so they won't be forgotten when some time later someone decides to add another line.
Code:
```if (condition)
do_something();
------------------
Edit:
Sorry, I seem to be wrong about operator precedence, but the rest of the points should be relevant.

7. Ok:
1) I added counts to the for and while loops. So i should be counting every operation now.
*Note: My instructor did an example with a different sort, and i tried to match the placements of the counts in my program with his (ex: counts inside for and while loops).
2) I now have three sets of numbers that are the number of operations it takes to sort: A) A randomly generated array B) An already sorted array C) Reverse Sorted Array.

Output is as follows:
Code:
```size    a       b       c

1	2	2	2
2	12	10	10
3	18	15	15
4	40	33	33
5	54	43	49
6	66	48	57
7	82	58	67
8	99	63	75
9	113	73	85
10	162	121	133
20	371	236	290
30	727	494	623
40	993	644	809
70	2233	1472	1859
100	3466	2082	2673
200	8066	5125	5980
300	14062	9178	11401
500	24682	15263	19127
1000	57107	35476	40663
2000	128925	80899	92179
5000	371277	227157	283188```
Do these values seem correct? The running times of the reverse sorted array are generally less than the randomly sorted array.
This could be possible i guess, depending on the nature of the sort, but it seems odd. I read how this sorting algorithm works, but i didn't fully understand it.
On the examples we did in class, the reverse sort arrays always took more operations.

As for making a class to count the number of operations.
This was how my instructor counted his sorting algorithm (probably for simplicity since he was doing it in class).
So, i tired to follow his example, since i don't have much experience programming.

Thanks for the help.

Here is my code if needed:
*Note: I have a printing function that i used to test if the arrays were sorted correctly.
When i would shrink the number and size of the arrays to say...11 and 40 instead of 21 and 5000, they seemed to be sorted correctly.
When i changed back the number and size of the arrays back to 21 and 5000, i suppose something could have gone wrong.
Code:
```#include <iostream>
#include <time.h>
using namespace std;

void fill_array(int A[], int size);
int shell_sort(int A[], int size);
void print_array(int A[], int size);

int main()
{
const int size = 5000;
int A [size];
int B [21] = {1,2,3,4,5,6,7,8,9,10,20,30,40,70,100,200,300,500,1000,2000,5000};
int C [size];
int new_size = 0;

srand ((unsigned int)time((time_t)0));

cout<<"Randomly Generated:"<<endl;
for (int i = 0; i < 21; i++)
{
int sum = 0;

for(int j = 0; j <= 30; j++)
{
new_size = B[i];

fill_array(A, new_size);
sum+= shell_sort(A, new_size);
}

cout.width(4);
cout<<sum/30<<endl;
//new_size<<":  "<<sum/30<<endl;
}

cout<<endl<<"Sorted:"<<endl;
for (int k = 0; k < 21; k++)
{
new_size = B[k];

cout.width(4);
//cout<<new_size<<":  "
cout<<shell_sort(A, new_size)<<endl;
}

cout<<endl<<"Reverse Sorted:"<<endl;

for( int m = 0; m < 5001; m++)
{
C[m] = A[4999-m];
}
for (int l = 0; l < 21; l++)
{
new_size = B[l];

cout.width(4);
//cout<<new_size<<":  "
cout<<shell_sort(C, new_size)<<endl;
}

//print_array(C, size);

return 0;
}
int shell_sort(int A[], int size)
{
int count = 0 ;
int i, j, increment, temp;
increment = size / 2;									++count;

while (++count && increment > 0)
{
for (i = increment; ++count && i < size; i++)
{
j = i;											++count;
temp = A[i];									++count;

while (++count &&(j >= increment) && (A[j-increment] > temp))
{
A[j] = A[j - increment];					++count;
j = j - increment;							++count;
}
A[j] = temp;									++count;
}

if (increment == 2)
{
increment = 1;									++count;
}
else
{
increment = (int) (increment / 2.2);			++count;
}
}

return count;
}
void fill_array(int A[], int size)
{
int first_rand = 0;

while(first_rand < size)
{
A[first_rand] = rand() &#37; 2100;
first_rand++;
}
}
void print_array(int A[], int size)
{
int first_pos = 0;

cout.width(2);
cout<<size<<":    ";

while(first_pos < size)
{
cout<<A[first_pos]<<" ";
first_pos++;
}
cout<<endl;
}```

8. cpro, what sort of indentation is that?
I mean, why are all the count++ essentially invisibly indented all the way to the right?

9. On my program, they are all lined up. When i copied and pasted it over to the message board, the spacing got messed up.
I have them tabbed over so i can see all the lines that are being counted in my code, so i don't miss any.

10. Mixing spaces and tabs is a disaster for posting code on a forum. Your editors' idea of a tab differs from what the forum uses, which is different from.... (and so on).

Set your editor to use only spaces, 4 spaces seems to be a good choice. A good editor will auto indent for you anyway, and do the right thing when you press tab.
Spaces are universal and unambiguous.

11. Your results at least seem to be consistent with the Comparison counts from my code. For 100 items I get:
771 comparisons for random order
420 comparisons for in order
588 comparisons for reverse order
Note that this is with the Incerpi-Sedgewick gap sequence.
I also avoid doing these two lines if the while loop will not be entered, by doing a comparison first.
Code:
```temp = A[i];
A[j] = temp;```

12. Thanks for the help!

13. I ran into another problem when i applied my code to a bubble sort (i have to do multiple sorts and compare them).
The last value of count for the randomly generated array comes out as a negative number:
Code:
```Randomly Generated:
1:  7
2:  14
3:  26
4:  43
5:  59
6:  98
7:  128
8:  158
9:  210
10:  257
20:  1033
30:  2383
40:  4460
70:  13777
100:  28908
200:  116320
300:  266019
500:  751638
1000:  3014333
2000:  12128173
5000:  -66639026

Sorted:
1:  7
2:  9
3:  11
4:  13
5:  15
6:  17
7:  19
8:  21
9:  23
10:  25
20:  45
30:  65
40:  85
70:  145
100:  205
200:  405
300:  605
500:  1005
1000:  2005
2000:  4005
5000:  10005

Reverse Sorted:
1:  7
2:  9
3:  11
4:  13
5:  75
6:  85
7:  95
8:  105
9:  207
10:  225
20:  1372
30:  2656
40:  4402
70:  15972
100:  29927
200:  139532
300:  279632
500:  818199
1000:  3497816
2000:  13991219
5000:  91954493```
As you can see, everything else seems to be fine. I can't imagine why i'm getting a negative number there. I was thinking that it may be just too large of a number, but the numbers of the reverse sort are similar, and it doesn't return a negative value. The code is similar to the shell sort code (i just replaced the shell sort with a bubble sort), and the shell sort seemed to work fine.
Any ideas?
Thanks.

Here is the code:
Code:
```#include <iostream>
#include <time.h>
using namespace std;

void fill_array(int A[], int size);
int bubble_sort(int Array1[], int size);
void print_array(int A[], int size);

int main()
{
const int size = 5000;
int A [size];
int B [21] = {1,2,3,4,5,6,7,8,9,10,20,30,40,70,100,200,300,500,1000,2000,5000};
int C [size];
int new_size = 0;

srand ((unsigned int)time((time_t)0));

cout<<"Randomly Generated:"<<endl;
for (int i = 0; i < 21; i++)
{
int sum = 0;

for(int j = 0; j <= 30; j++)
{
new_size = B[i];

fill_array(A, new_size);
sum+= bubble_sort(A, new_size);
}
cout.width(4);
cout<<new_size<<":  "<<sum/30<<endl;
}

cout<<endl<<"Sorted:"<<endl;
for (int k = 0; k < 21; k++)
{
new_size = B[k];

cout.width(4);
cout<<new_size<<":  "<<bubble_sort(A, new_size)<<endl;
}

cout<<endl<<"Reverse Sorted:"<<endl;
for( int m = 0; m < 5001; m++)
{
C[m] = A[4999-m];
}
//print_array(C, size);
for (int l = 0; l < 21; l++)
{
new_size = B[l];

cout.width(4);
cout<<new_size<<":  "<<bubble_sort(C, new_size)<<endl;
}
//print_array(A, size);

return 0;
}
int bubble_sort(int Array1[], int size)
{
int count = 0;
int i, j, flag = 1;                                         ++count;
int temp;                                                   ++count;
int Array1Length = size;                                    ++count;

for(i = 1; ++count &&(i <= Array1Length) && flag; i++)
{
flag = 0;                                             ++count;
for (j=0; ++count && j < (Array1Length -1); j++)
{
if (++count && Array1[j+1] < Array1[j])
{
temp = Array1[j];                           ++count;
Array1[j] = Array1[j+1];                    ++count;
Array1[j+1] = temp;                         ++count;
flag = 1;                                   ++count;
}
}
}

return count;
}

void fill_array(int A[], int size)
{
int first_rand = 0;

while(first_rand < size)
{
A[first_rand] = rand() &#37; 2100;
first_rand++;
}
}
void print_array(int A[], int size)
{
int first_pos = 0;

cout.width(2);
cout<<size<<":    ";

while(first_pos < size)
{
cout<<A[first_pos]<<" ";
first_pos++;
}
cout<<endl;
}```

14. Try changing bubble_sort to return an unsigned int.

15. Or better yet, a long.