Thread: Why sort( ) is taking longer time than qsort( ) in my program?

  1. #1
    Registered User
    Join Date
    Jul 2014
    Posts
    41

    Why sort( ) is taking longer time than qsort( ) in my program?

    I ran my program using qsort( ) , then again using sort( ).But qsort( ) finished faster than sort( ).why is that?
    Code:
    #include<iostream>
    #include<algorithm>
    #include<cstdlib>
    #include<ctime>
    using namespace std;
    int compare(const void * a, const void * b)
    {
    	return (*(int*)a - *(int*)b);
    }
    void fillRand(int* a, size_t size, int low, int high)
    {
    	srand(time(NULL));
    	int i;
    	for (i = 0; i<size; ++i)
    	{
    		a[i] = rand() % ((high + 1) - low) + low;
    	}
    }
    int main()
    {
    	size_t size; cout << " size : "; cin >> size;
    	int* a = new int[size];
    	int l, h; cout << " low : "; cin >> l; cout << " high : "; cin >> h;
    	fillRand(a, size, l, h);
    	clock_t st, et;
    	double diff;
    	char answer;
    	int option;
    	cout << " Which sorting method would you like to apply : \n"
    		 << " 1.qsort()\n"
    		 << " 2.sort()\n ";
    	cin >> option;
    	if (option == 1)
    	{
    		st = clock();
    		qsort(a, size, sizeof(int), compare);
    		et = clock();
    		diff = et - st;
    		cout << " time taken = " << diff / CLOCKS_PER_SEC << " sec" << endl;
    	}
    	else if (option == 2)
    	{
    		st = clock();
    		sort(a, a + size);
    		et = clock();
    		diff = et - st;
    		cout << " time taken = " << diff / CLOCKS_PER_SEC << " sec" << endl;
    	}
    	else
    	{
    		cout << " Invalid option\n";
    		exit(0);
    	}
    	delete[] a;
    	return 0;
    }

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,981
    >> srand(time(NULL));
    You're getting different data on each run. You don't want that for it to be a fair comparison. You would also want to have optimization enabled for a fair comparison.

    gg

  3. #3
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    How much longer and what kind of sizes are you using?

    If you are using small sizes (below a few million) the time difference is just noise.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    I tried this with VS2005, removing the srand(), so the data would be the same. On an Intel 2600K 3.4gz cpu, with input size of 1,000,000, low of 1, high of 1,000,000 the result was qsort took .109 seconds while sort took .047 seconds, with 10,000,000, the times were 0.984 and 0.578. Note clock is running at 64hz, so the times are to the nearest .015625 seconds, but sort is faster on my system.

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    Quote Originally Posted by rcgldr View Post
    I tried this with VS2005, removing the srand(), so the data would be the same. On an Intel 2600K 3.4gz cpu, with input size of 1,000,000, low of 1, high of 1,000,000 the result was qsort took .109 seconds while sort took .047 seconds, with 10,000,000, the times were 0.984 and 0.578. Note clock is running at 64hz, so the times are to the nearest .015625 seconds, but sort is faster on my system.
    On my server (Amazon EC2 m1.small instance) with GCC 4.8.1, and the same parameters -
    Without optimizations -
    qsort: 0.63s
    sort: 0.72s

    With optimizations (-O3 -march=native) -
    qsort: 0.5s
    sort: 0.22s

  6. #6
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    Lol those optimizations. Holy poop.

  7. #7
    Registered User
    Join Date
    Apr 2013
    Posts
    1,658
    My guess is that qsort() is a pre-compiled library function (and already optimized), so only the compare routine is affected by optimization. Since std::sort() is a template, it's getting compiled, so all of it is affected by optimization.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Plus inlining of the comparison function(s).
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by V8cTor View Post
    I ran my program using qsort( ) , then again using sort( ).But qsort( ) finished faster than sort( ).why is that?
    This is like asking: "I flipped a coin and got heads, why is that?"
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Use qsort() to sort array of pointers to struct
    By VIgnotam in forum C Programming
    Replies: 4
    Last Post: 04-04-2012, 06:42 PM
  2. dxgi.dll is taking all my render time , help please
    By thedodgeruk in forum Game Programming
    Replies: 1
    Last Post: 03-13-2012, 08:12 PM
  3. sleep(1) takes longer each time it is called?
    By lsad in forum C Programming
    Replies: 13
    Last Post: 07-08-2010, 02:28 AM
  4. Using qsort to sort an array of strings
    By MSF1981 in forum C Programming
    Replies: 31
    Last Post: 05-17-2009, 01:31 AM
  5. using qsort to sort an array of strings
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-25-2005, 08:31 AM