It depends on how qsort is implemented by the C
stdlib library with which perl was compiled. My guess is no,
but it really depends on how your C stdlib was implemented.
It is easy to add a "quicksort worst-case avoider"
by not using a "use the first element as the pivot" and instead
doing something like:
- adding a "sorted list detector"
- Picking the pivot randomly (instead of as the first element)
- Shuffling the list before sorting
- Using another pivot picking technique
Since not everyone knows the internals of quicksort, there
is a worst case performance of O(n^2) with quicksort if the
worst pivot is picked for each iteration (if you don't know what a
pivot is don;t worry.... if you want to know I can explain it. This
worst-case performance can happen if the list is already in
is in sorted order and the pivot is picked by choosing the first
element of the list as the pivot. However, there are
techniques for easily avoiding this pitfall.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] |