• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 272
  • Last Modified:

Is Ms vc6 qsort known to be 'smart' about already sorted array?

Is Ms vc6 qsort known to be 'smart' about already sorted array?

I'm getting ready to do some sorting of a small'ish array. (300 to 1000 elements). In general, it will already be sorted, or almost sorted.  My understanding is that some implementations of qsort become quadratic with an array that is already sorted.  Does anyone know specifically if this applies to MicroSoft's implementation in visual c++ 6, sp5?  Preferrably, this would include a link to something authoritative with, ideally, a test program.

I could write a quick 'proof-of-concept' program, but would rather ask this forum.

A related question ... my impression is that a variant of a quadratic sort algorithm turns out to be 'good enough' for almost sorted arrays.  Is this the 'shell' sort?  Can some 'smart' implementations of qsort detect an already (or almost) sorted list and use another algorithm for this partition?  Or use a simple quadratic sort variant when the partition get small?

TIA
0
ee-user
Asked:
ee-user
  • 2
1 Solution
 
snoeglerCommented:
You can take a look at qsort.c (installed with the MSVC RTL source code) in VC98\CRT\SRC\QSORT.c

Basically, it decides whether the array is short (8 elements) and does an insertion sort if that is the case.

Otherwise, it takes the middle element as median. Original comment from the source code:

        /* First we pick a partititioning element.  The efficiency of the
           algorithm demands that we find one that is approximately the
           median of the values, but also that we select one fast.  Using
           the first one produces bad performace if the array is already
           sorted, so we use the middle one, which would require a very
           wierdly arranged array for worst case performance.  Testing shows
           that a median-of-three algorithm does not, in general, increase
           performance. */
0
 
ee-userAuthor Commented:
Snoegler,

Thanks for the reply.  I didn't choose the option to install source code during VisStudio installation .. perhaps I should have :-(

Based on the comment you provide, MicroSoft's implementation of qsort looks at least adequately 'smart'.
0
 
snoeglerCommented:
Thanks
0

Featured Post

Upgrade your Question Security!

Add Premium security features to your question to ensure its privacy or anonymity. Learn more about your ability to control Question Security today.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now