what sort is this?

Discussion in 'C Programming' started by Kapteyn's Star, Aug 3, 2008.

  1. Hi all,
    Can anyone identify this sort code? why is it very slow compard to
    qsort()? and it can be improved?
    Thanks.

    int *next_ascending(int *arr, size_t narr, int val)
    {
    size_t ctr;
    int *next= arr;
    for(ctr= 0; ctr < narr; ++ctr)
    if (arr[ctr] >= val && arr[ctr] < *next) next= &arr[ctr];
    return next;
    }

    int *next_descending(int *arr, size_t narr, int val)
    {
    size_t ctr;
    int *next= arr;
    for(ctr= 0; ctr < narr; ++ctr)
    if (arr[ctr] <= val && arr[ctr] > *next) next= &arr[ctr];
    return next;
    }

    void sort(int *arr, size_t narr, char direction)
    {
    size_t ctr= 0;
    int preva= INT_MIN, prevd= INT_MAX, *next, tmp;
    switch (direction) {
    case ASCENDING:
    while (ctr < narr) {
    next= next_ascending(&arr[ctr], narr-ctr, preva);
    tmp= arr[ctr];
    arr[ctr]= preva= *next;
    *next= tmp;
    ctr++;
    }
    break;
    case DESCENDING:
    while (ctr < narr) {
    next= next_descending(&arr[ctr], narr-ctr, prevd);
    tmp= arr[ctr];
    arr[ctr]= prevd= *next;
    *next= tmp;
    ctr++;
    }
    }
    }


    --
    Kapteyn's Star
     
    Kapteyn's Star, Aug 3, 2008
    #1
    1. Advertising

  2. Kapteyn's Star

    jacob navia Guest

    DO YOUR OWN HOMEWORK!
     
    jacob navia, Aug 3, 2008
    #2
    1. Advertising

  3. jacob navia wrote:

    > DO YOUR OWN HOMEWORK!


    It's not homework. Im not a student at all...just interested in
    programming.

    I came up with the algorithm but im certain it's already known. but im
    just not able to find it on the web...only psudocode is given on
    wikipaedia and i don't know which one is this method.

    --
    Kapteyn's Star
     
    Kapteyn's Star, Aug 3, 2008
    #3
  4. Kapteyn's Star

    arj Guest

    > Can anyone identify this sort code?
    Looks like some kind of selection sort.
     
    arj, Aug 3, 2008
    #4
  5. Kapteyn's Star

    regis Guest

    arj wrote:
    >> Can anyone identify this sort code?

    > Looks like some kind of selection sort.


    it s a selection sort where the (arr[ctr] >= val) condition
    in next_ascending() seems useless because val is the minimum
    selected in the previous step by sort() in descending direction.
    So the condition is always true by inviariant of the algorithm.

    Same thing for (arr[ctr] <= val) condition in next_desscending()
    because val is maximum selected in the previous step by sort()
    in ascending direction.

    so the parameter val seems useless as is the updating of
    variable preva in sort()...

    But i may be wrong...
     
    regis, Aug 4, 2008
    #5
  6. Kapteyn's Star

    Ron Ford Guest

    On Sun, 03 Aug 2008 16:06:45 +0530, Kapteyn's Star posted:

    > jacob navia wrote:
    >
    >> DO YOUR OWN HOMEWORK!

    >
    > It's not homework. Im not a student at all...just interested in
    > programming.
    >
    > I came up with the algorithm but im certain it's already known. but im
    > just not able to find it on the web...only psudocode is given on
    > wikipaedia and i don't know which one is this method.


    Jacob's a Texas ex-pat in Paris. He also shouted "you're queer if you
    don't like penthouse," and "you poisoned me on the chanz a lyzee."

    I can provide a selection sort from a syntax with C bindings, if that would
    help.

    Britain's Heide has the final word on this sort, probably coarse.
    --
    What men value in this world is not rights but privileges. 7
    H. L. Mencken
     
    Ron Ford, Aug 8, 2008
    #6
    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. nobody
    Replies:
    0
    Views:
    566
    nobody
    Jun 1, 2004
  2. JerryJ
    Replies:
    11
    Views:
    1,430
    Dave Moore
    Apr 28, 2004
  3. John Black
    Replies:
    6
    Views:
    2,110
    John Harrison
    May 28, 2004
  4. Angus Comber
    Replies:
    7
    Views:
    1,199
    Richard Heathfield
    Feb 5, 2004
  5. Navin
    Replies:
    1
    Views:
    762
    Ken Schaefer
    Sep 9, 2003
Loading...

Share This Page