Thread: Counting sorting operations

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

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.