Counting sorting operations

This is a discussion on Counting sorting operations within the C++ Programming forums, part of the General Programming Boards category; Hi, I'm trying to count the number of operations it takes a certain sorting algorighm (in this case a shell ...

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    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. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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?
    Last edited by iMalc; 01-22-2008 at 12:11 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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)
    Last edited by iMalc; 01-22-2008 at 12:13 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  4. #4
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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
    Last edited by Cpro; 01-22-2008 at 12:48 AM.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by Cpro View Post
    "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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    The larch
    Join Date
    May 2006
    Posts
    3,573
    "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.
    Last edited by anon; 01-22-2008 at 01:53 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  7. #7
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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;
    }
    Last edited by Cpro; 01-22-2008 at 04:38 AM.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,767
    cpro, what sort of indentation is that?
    I mean, why are all the count++ essentially invisibly indented all the way to the right?
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,767
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    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;
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    Thanks for the help!

  13. #13
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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;
    }
    Last edited by Cpro; 01-25-2008 at 04:55 AM.
    IDE - Visual Studio 2005
    Windows XP Pro

  14. #14
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Try changing bubble_sort to return an unsigned int.

  15. #15
    Registered User
    Join Date
    Apr 2006
    Posts
    2,053
    Or better yet, a long.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Sorting algorithms, worst-case input
    By Leftos in forum C++ Programming
    Replies: 17
    Last Post: 06-15-2009, 02:33 PM
  2. Need help with linked list sorting function
    By Jaggid1x in forum C Programming
    Replies: 6
    Last Post: 06-02-2009, 03:14 AM
  3. doing floating operations using integer operations
    By ammalik in forum C Programming
    Replies: 10
    Last Post: 08-15-2006, 05:30 AM
  4. Reading a file, sorting and counting contents, help?
    By mmmm_strawberri in forum C Programming
    Replies: 14
    Last Post: 04-04-2005, 02:21 AM
  5. Matrix and vector operations on computers
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 05-11-2004, 07:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21