codeDREAMER's blog

DIFFERENCE BETWEEN THE STANDARD LIBRARY FUNCTION "qsort" AND OTHER SORTING TECHNIQUES
By codeDREAMER, 12 years ago, In English

Hello everyone..!! Yesterday i was trying to check the time taken by sorting techniques in this simple ques : http://www.codechef.com/problems/TSORT here the time limit is 5 sec and the no. of elements <=10^6 and the elements are <=10^6..as the optimal solution for this is hashing (or linear sorting) in O(n) i was trying to test for other sorting techniques too... and i observed following : 1. Heapsort : time limit exceeded 2. Mergesort : same 3. quicksort as expected same due to O(n^2) worst case 4.sort(a,a+n) in <algorithm.h> :same but the standard library function qsort passed now i can't understand that why qsort which is also qucicksort passed and mine other sorting techniques failed?? Is it that qsort works in different way or something else ... plzz help .. thanx :)

  • Vote: I like it
  • -16
  • Vote: I do not like it

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

Remember that quick sort is a randomized algorithm .Here the pivot point which you choose has a very big hand to play . For eg . you can check for a few sample cases that the end element, the start element and the middle element choosen as pivot point have different run times. I dont know exactly how is the qsort implemented in C++ STL , but you can just shuffle your array once to make your own version pass I suppose .

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

    but randomized Quicksort too has a worst case running time of O(n^2) and what abt sort(a,a+n) in C++ STL??

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      sort isn't just a quicksort. It's merge of quicksort, heapsort and ifs (when n ≤ 3). If quicksort goes very deep, heapsort starts. So its worst case running time is .

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

        if sort(a,a+n) is always O(nlogn) then it should have also passed because qosrt passed which cant be better than O(nlogn) please have a look into the problem

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

          I don't know what exactly qsort does, but even if it has the same asymptotic as sort it may work faster. Hidden constant in O() can vary a lot.

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

            okay thanks for the information on sort(a,a+n)

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

    one more thing even if QuickSort don't go to its Worst case then its running time is O(nlogn) and Heapsort and Mergesort too with asymtotical same complexity so if Qucik Sort can pass why not others ??

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Yes, expected running time for randomized quicksort is O(nlogn). For non-randomized quicksort, the worst case running time is O(n^2)

      Quicksort has a very small constant factor compared to other sorting algorithms. Compared to mergesort, quicksort performs better because it sorts the array in place; mergesort creates an array each time when merging. Heapsort also sorts in place, but apparently quicksort is faster than it because it uses the CPU cache in a better way & also other factors (according to wikipedia).

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +9 Vote: I do not like it
        expected worst case running time

        Choose one of "expected" and "worst". The expected (average) running time is , the worst-case running time is still O(n2) for randomized QuickSort.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it +1 Vote: I do not like it

          Thanks got confused about that, but isn't it very improbable to obtain the worst case, because of the randomization? So that we can actually expect the worst case to be equal to the average case?

          Thanks

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            For any particular input, the expected running time is for randomized QuickSort. However, there is still non-zero probability that it will run in O(n2) time on this input. Thus you can't say that the algorithm never performs worse than .

            → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Are you sure because i got AC using sort(a,a+n) and scanf printf

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

    after seeing ur cmmnt i resubmitted the sol but sort(a,a+n) is still Time limit Exceeding with scanf,printf or cin,cout but i got AC with fast input method

    → Reply