Solved

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

Posted on 2002-04-29
3
245 Views
Last Modified: 2013-11-20
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
Comment
Question by:ee-user
  • 2
3 Comments
 
LVL 6

Accepted Solution

by:
snoegler earned 50 total points
ID: 6982108
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
 

Author Comment

by:ee-user
ID: 6982643
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
 
LVL 6

Expert Comment

by:snoegler
ID: 6983109
Thanks
0

Featured Post

Master Your Team's Linux and Cloud Stack!

The average business loses $13.5M per year to ineffective training (per 1,000 employees). Keep ahead of the competition and combine in-person quality with online cost and flexibility by training with Linux Academy.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Here is how to use MFC's automatic Radio Button handling in your dialog boxes and forms.  Beginner programmers usually start with a OnClick handler for each radio button and that's just not the right way to go.  MFC has a very cool system for handli…
Exception Handling is in the core of any application that is able to dignify its name. In this article, I'll guide you through the process of writing a DRY (Don't Repeat Yourself) Exception Handling mechanism, using Aspect Oriented Programming.
This video will show you how to get GIT to work in Eclipse.   It will walk you through how to install the EGit plugin in eclipse and how to checkout an existing repository.
Email security requires an ever evolving service that stays up to date with counter-evolving threats. The Email Laundry perform Research and Development to ensure their email security service evolves faster than cyber criminals. We apply our Threat…

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question