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.

Quote:

---

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?

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)

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

Quote:

---

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.

Quote:

---

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.

Quote:

---

"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();
    do_some_more(); //added later

---

------------------
Edit:
Sorry, I seem to be wrong about operator precedence, but the rest of the points should be relevant.

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;
}

---

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

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.

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.

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;

---

Thanks for the help!

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;
}

---

Try changing bubble_sort to return an unsigned int.

Or better yet, a long.

Quote:

---

Originally Posted by King Mir

Or better yet, a long.

---

A long int would provide exactly the same result on a 32-bit machine. Of course, if it's a 64-bit machine, then using long on Linux would make it a 64-bit number, so sufficient for the count.

Changing it to unsigned will help until the number wraps multiple times.

--
Mats

In each function that takes an array size as argument, the size type should be std::size_t, not int.

Quote:

---

Originally Posted by robatino

In each function that takes an array size as argument, the size type should be std::size_t, not int.

---

Whilst this is correct, the OP's complaint was that numbers turn negative all of a sudden in the counting of number of operations.

--
Mats

In general, there may not be a type big enough to hold the result, since std::size_t may be the biggest unsigned type on the platform, and the number of swaps is generally bigger than the array, by at least a log N factor. But with an O(N log N) sort algorithm, the extra log N factor only requires a few extra bits, so the best bet may be to use std::size_t as the output type, and limit the size of the input array (if the algorithm is O(N^2) the limit is a lot smaller).

Edit: For the foreseeable future, a 64-bit type is more than big enough, considering how long it would take to count that high, so if long long is available as a nonstandard extension (as in GCC, I think) then that would do.

Thanks for the fix. This also helped me find out where this large number was coming from. For the randomly generated array, i was averaging thirty of them. So, when my program tried to add them together, the number was apparently too big.

Code:

---

cout<<"Randomly Generated:"<<endl;
        for (int i = 0; i < 21; i++)
        {
                unsigned 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;
        }

---

Thanks again.