CreativeAss's blog

Quick Sort
By CreativeAss, history, 8 years ago, In English

Average time of quick sort is O(nlogn). So in many contest n is like 5*10^5 at that time nlogn would be ~10^7 operations. Considering not worst but some bad case the sorting can take around ~(4*10^8 — 5*10^8) operations and give a Time Limit Exceeded.

Now I wanted to know that can this type of case happen during a submission in Codeforces or It can never happen.

Sorry for silly question.

Thanks in advance.

  • Vote: I like it
  • +6
  • Vote: I do not like it

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

There are times when problems have anti-qsort cases, which is mostly just a big problem for java. One of these is the div3c problem Less or Equal: https://codeforces.me/contest/977/problem/C

→ Reply
»
8 years ago, hide # |
← Rev. 12  
Vote: I like it +7 Vote: I do not like it

std::sort in C++ is very smart:

  • in worst case it is heap sort, O(n log(n)), large constant
  • in another case it is quick sort, O(n log(n)), small constant

For speedup use std::random_shuffle before std::sort

Also, you can use std::stable_sort, O(nlog(n)) time and O(n) additional memory (it's a merge sort), if you write code in C++, of course.

I can give a link on problem where std::stable_sort works in 4 times faster then std::sort. Solution with std::sort gets TLE, solution with std::stable_sort — accepted, it's in russian, but you can use google translate. In this problem, you need to sort all the cyclic shifts of the string length 10^5 in lexicographical order. It can be solved with sorting (compare substrings with hashes) in O(nlog(n)^2) (easy) or suffix structures (hard) in O(nlog(n)).

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

    Thanks :) Btw dmkozyrev can you explain that how std::sort in c++ is smart. Like how does it know when to use heap sort and when to use quick sort.

    → Reply
    • »
      »
      »
      8 years ago, hide # ^ |
       
      Vote: I like it +9 Vote: I do not like it

      I'm pretty sure its quicksort until recursion gets too deep it switches to heapsort.

      And why it's "smart" is because it's been constant optimized and combines two algorithms in an effective way. It's hard to get faster than stl sorting. This hybrid of heap and quick sort is called "introsort" you can find it on wikipedia

      And stable_sort does "timsort" which is constant optimized mergesort by combining insertion sort with mergesort.

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

      in addition, merge sort uses the minimal number of comparisons in the worst case among all sorting algorithms based on comparison. If compare two elements very difficult operation, always use merge sort.

      → Reply