Microsoft Quick+insertion

Discussion in 'C Programming' started by Am, Apr 15, 2006.

  1. Am

    Am Guest

    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.
    Am, Apr 15, 2006
    #1
    1. Advertising

  2. Am

    santosh Guest

    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.
    santosh, Apr 15, 2006
    #2
    1. Advertising

  3. 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)
    Richard Heathfield, Apr 15, 2006
    #3
  4. 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.polytechniq.../Luc.Maranget/421/09/bentley93engineering.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
    Diomidis Spinellis, Apr 15, 2006
    #4
  5. Am

    Am Guest

    thank you very much Diomidis ,please keep in touch i may need u r help
    Am, Apr 15, 2006
    #5
  6. Am

    Am Guest

    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.
    Am, Apr 15, 2006
    #6
  7. 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:671–685, 1983.
    Diomidis Spinellis, Apr 15, 2006
    #7
  8. Am

    Am Guest

    gprof, but can you post the link if possible
    Am, Apr 16, 2006
    #8
  9. "Am" <> 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) <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.
    Keith Thompson, Apr 16, 2006
    #9
  10. On 15 Apr 2006 23:12:00 -0700, in comp.lang.c , "Am"
    <> 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
    Mark McIntyre, Apr 16, 2006
    #10
  11. Am

    CBFalconer Guest

    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/>
    CBFalconer, Apr 16, 2006
    #11
  12. Am

    pete Guest

    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.polytechniq.../Luc.Maranget/421/09/bentley93engineering.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
    pete, Apr 20, 2006
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Charles A. Lackman
    Replies:
    1
    Views:
    1,323
    smith
    Dec 8, 2004
  2. SpamProof
    Replies:
    0
    Views:
    528
    SpamProof
    Oct 21, 2003
  3. JKop
    Replies:
    11
    Views:
    852
  4. Am
    Replies:
    5
    Views:
    341
  5. harshu010
    Replies:
    0
    Views:
    282
    harshu010
    May 29, 2008
Loading...

Share This Page