moiz_hussain's blog

qsort() implementation
By moiz_hussain, history, 10 years ago, In English

I was attempting ques. 580B. My AC solution(http://mirror.codeforces.com/submissions/moiz_hussain#AC) using qsort() and 2D array gives time of 265ms on case 26 where as WA solution(http://mirror.codeforces.com/submissions/moiz_hussain#WA) uses a quicksort function and two arrays gives time of 2000ms.Can someone explain why this is happening?

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

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

Quicksort has worst case performance O(n2). For simple implementations it happens when array is already sorted. The problem can be partially avoided by using more complex methods of choosing pivot.

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

Search google for randomised quicksort. qsort seems to use "randomised" quicksort, that is, it selects pivot randomly.

→ Reply