By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,590 Members | 663 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 428,590 IT Pros & Developers. It's quick & easy.

Microsoft Quick+insertion

P: n/a
Am
hi
i came to know that microsoft improved the efficiency of quick sort
by using a cutoff
of 8 elements and continuing with insertion sort then, do anybody have
the details about it
please contant me.

Apr 15 '06 #1
Share this Question
Share on Google+
11 Replies


P: n/a
Am wrote:
hi
i came to know that microsoft improved the efficiency of quick sort
by using a cutoff
of 8 elements and continuing with insertion sort then, do anybody have
the details about it
please contant me.


This question is more topical in one of the microsoft.public.*
newsgroups.

Apr 15 '06 #2

P: n/a
Am said:
hi
i came to know that microsoft improved the efficiency of quick sort
by using a cutoff
of 8 elements and continuing with insertion sort then, do anybody have
the details about it


I doubt very much whether it was Microsoft which came up with this
improvement. It is true that they use it, but if you think it's their idea,
or if you want to know the details, I suggest you check "The Art of
Computer Programming Vol 3 - Sorting and Searching", by Donald E Knuth.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Apr 15 '06 #3

P: n/a
Am wrote:
i came to know that microsoft improved the efficiency of quick sort
by using a cutoff
of 8 elements and continuing with insertion sort then, do anybody have
the details about it
please contant me.


I doubt this is a Microsoft invention. Check out Bentley McIlroy's
classic paper "Engineering a Sort Function". Software---Practice and
Experience 23(11):1249--1269, November 1993. I located an online copy
at
http://www.enseignement.polytechniqu...ngineering.pdf

Also, the 1992-dated BSD Unix qsort implementation starts with the qsort
with an insertion sort if the numebr of elements is less than 7:

void
qsort(void *a, size_t n, size_t es,
int (*cmp)(const void *, const void*))
{
char *pa, *pb, *pc, *pd, *pl, *pm, *pn;

if (n < 7) {
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
pl -= es)
swap(pl, pl - es);
return;
}
/* Recursive qsort implementation continues here */

--
Diomidis Spinellis
Code Quality: The Open Source Perspective (Addison-Wesley 2006)
http://www.spinellis.gr/codequality
Apr 15 '06 #4

P: n/a
Am
thank you very much Diomidis ,please keep in touch i may need u r help

Apr 15 '06 #5

P: n/a
Am
great u write books!,I am using fedora core 2 can you suggest me an RPM
package to know the amount of time a program spends in a
particular part of the program.

Apr 15 '06 #6

P: n/a
Am wrote:
great u write books!,I am using fedora core 2 can you suggest me an RPM
package to know the amount of time a program spends in a
particular part of the program.


gprof

Susan L. Graham, Peter B. Kessler, and Marshall K. McKusick. An
execution profiler for modular programs. Software: Practice &
Experience, 13:671685, 1983.
Apr 15 '06 #7

P: n/a
Am
gprof, but can you post the link if possible

Apr 16 '06 #8

P: n/a
"Am" <ma*********@gmail.com> writes:
gprof, but can you post the link if possible


www.google.com

And please read <http://cfaj.freeshell.org/google/>.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Apr 16 '06 #9

P: n/a
On 15 Apr 2006 23:12:00 -0700, in comp.lang.c , "Am"
<ma*********@gmail.com> wrote:
gprof, but can you post the link if possible


FCOL, STFW.
Mark McIntyre
--
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan
Apr 16 '06 #10

P: n/a
Am wrote:

gprof, but can you post the link if possible


Meaningless. Include adequate context. See below for how on the
broken google interface to usenet.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
Apr 16 '06 #11

P: n/a
Diomidis Spinellis wrote:
Check out Bentley McIlroy's
classic paper "Engineering a Sort Function". Software---Practice and
Experience 23(11):1249--1269, November 1993. I located an online copy
at
http://www.enseignement.polytechniqu...ngineering.pdf


It has at least one mistake concerning the c programming language.

This footnote is wrong in what it says
about the pointer to void type, compeling casting:

We have used simple parameter declarations for readability.
The official prototype in the ANSI standard header file,
<stdlib.h>, is6
void qsort(void *, size_t, size_t, int (*)(const void *, const void *));
This declaration can be used no more honestly than ours.
The first argument compels casting in the source of qsort;
the last compels casting in programs that call it.

--
pete
Apr 20 '06 #12

This discussion thread is closed

Replies have been disabled for this discussion.