Counting sorting operations

This is a discussion on Counting sorting operations within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by King Mir Or better yet, a long. A long int would provide exactly the same result on ...

  1. #16
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by King Mir View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  2. #17
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    In each function that takes an array size as argument, the size type should be std::size_t, not int.

  3. #18
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by robatino View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  4. #19
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    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.
    Last edited by robatino; 01-25-2008 at 09:21 AM.

  5. #20
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    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.
    IDE - Visual Studio 2005
    Windows XP Pro

Page 2 of 2 FirstFirst 12
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