damn_me's blog

Functioning of qsort in c++
By damn_me, 10 years ago, In English

I know how qsort works using the function compare. But I am not getting how many times that compare is called. i.e. how is qsort functioning using compare. I read that it takes the elements pairwise. Does that mean if the array is int a[]={10,9,8,7,6,5};

then it will first take 10,9 and then 8,7 and so on. What exactly is happening. I did this to figure out but could not.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

It's about N to N^2 comparisons, with average about N*log(N) Consider using C++ sort instead of C's, because it usually runs faster (it's easier for compiler to optimize it), has N*log(N) worst-case instead of N^2, and has more type-checks. Also, the "static" keyword in your code is useless (it would have made sense if it had been declared as local variable, but it is global variable and so static keyword makes it local to current module instead). Also, return l-r can give error if it overflows.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    static is not completely useless there. With it the compiler knows the variable will not be accessed from outside, which may help the optimizer.

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There is a way that may help you ,look at this code I've just add one line to your code inside the compare function.

→ Reply