Блог пользователя codeDREAMER

DIFFERENCE BETWEEN THE STANDARD LIBRARY FUNCTION "qsort" AND OTHER SORTING TECHNIQUES
Автор codeDREAMER, 12 лет назад, По-английски

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 :)

  • Проголосовать: нравится
  • -16
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 .

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      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 .

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 ??

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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).

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится
        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.

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

          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

          → Ответить
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится

            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 .

            → Ответить
»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить