Solved

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

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

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Introduction: Finishing the grid – keyboard support for arrow keys to manoeuvre, entering the numbers.  The PreTranslateMessage function is to be used to intercept and respond to keyboard events. Continuing from the fourth article about sudoku. …
Introduction: Ownerdraw of the grid button.  A singleton class implentation and usage. Continuing from the fifth article about sudoku.   Open the project in visual studio. Go to the class view – CGridButton should be visible as a class.  R…
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 video shows how to remove a single email address from the Outlook 2010 Auto Suggestion memory. NOTE: For Outlook 2016 and 2013 perform the exact same steps. Open a new email: Click the New email button in Outlook. Start typing the address: …

747 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

11 Experts available now in Live!

Get 1:1 Help Now