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 :)
→ Обратите внимание
До соревнования
Codeforces Round (Div. 1, Based on Zhili Cup 2026)
5 дней
Зарегистрироваться »
Codeforces Round (Div. 1, Based on Zhili Cup 2026)
5 дней
Зарегистрироваться »
*есть доп. регистрация
До соревнования
Codeforces Round (Div. 2, Based on Zhili Cup 2026)
5 дней
Зарегистрироваться »
Codeforces Round (Div. 2, Based on Zhili Cup 2026)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Proof_by_QED | 146 |
| 3 | Um_nik | 146 |
| 5 | Dominater069 | 144 |
| 6 | errorgorn | 141 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 01.05.2026 19:26:36 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
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 .
but randomized Quicksort too has a worst case running time of O(n^2) and what abt sort(a,a+n) in C++ STL??
sortisn't just a quicksort. It's merge of quicksort, heapsort andifs (when n ≤ 3). If quicksort goes very deep, heapsort starts. So its worst case running time isif 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
I don't know what exactly
qsortdoes, but even if it has the same asymptotic assortit may work faster. Hidden constant in O() can vary a lot.okay thanks for the information on sort(a,a+n)
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 ??
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).
Choose one of "expected" and "worst". The expected (average) running time is
, the worst-case running time is still O(n2) for randomized QuickSort.
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
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 
.
Are you sure because i got AC using sort(a,a+n) and scanf printf
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