Solved

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

Posted on 2002-04-29
3
242 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
Powershell based monitoring system 2 138
Adapt this command to show who installed 29 106
Pressing cancel button with C# UI Automation 3 51
tripleUp challenge 7 73
In this article, I'll describe -- and show pictures of -- some of the significant additions that have been made available to programmers in the MFC Feature Pack for Visual C++ 2008.  These same feature are in the MFC libraries that come with Visual …
Introduction: The undo support, implementing a stack. Continuing from the eigth article about sudoku.   We need a mechanism to keep track of the digits entered so as to implement an undo mechanism.  This should be a ‘Last In First Out’ collec…
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.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.

932 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now