Bucketsort?

Discussion in 'C++' started by desktop, Sep 17, 2007.

  1. desktop

    desktop Guest

    Is the bucket sort container/algorithm built in somewhere in the C++ std
    or do I have to implement it myself?
    desktop, Sep 17, 2007
    #1
    1. Advertising

  2. desktop wrote:
    > Is the bucket sort container/algorithm built in somewhere in the C++
    > std or do I have to implement it myself?


    There is no bubble sort either. And no Shell sort. And no merge sort.
    Actually, come to think of it, only Quick sort is identified, and it's
    in the C++ library because it's in the C library. The C++ Standard
    does not specify what kind of sort algorithm is used for std::sort,
    std::stable_sort, and std::partial_sort[_copy].

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 17, 2007
    #2
    1. Advertising

  3. desktop

    desktop Guest

    Victor Bazarov wrote:
    > desktop wrote:
    >> Is the bucket sort container/algorithm built in somewhere in the C++
    >> std or do I have to implement it myself?

    >
    > There is no bubble sort either. And no Shell sort. And no merge sort.
    > Actually, come to think of it, only Quick sort is identified, and it's
    > in the C++ library because it's in the C library. The C++ Standard
    > does not specify what kind of sort algorithm is used for std::sort,
    > std::stable_sort, and std::partial_sort[_copy].
    >
    > V


    Ok I have found it here:

    http://www.codecogs.com/cog-1

    but I am not sure of the quality of the code from this place and it
    seems that its not downloadable like boost or other quality expansions.

    Any experience with codecogs?
    desktop, Sep 17, 2007
    #3
  4. desktop wrote:
    > Victor Bazarov wrote:
    >> desktop wrote:
    >>> Is the bucket sort container/algorithm built in somewhere in the C++
    >>> std or do I have to implement it myself?

    >>
    >> There is no bubble sort either. And no Shell sort. And no merge
    >> sort. Actually, come to think of it, only Quick sort is identified,
    >> and it's in the C++ library because it's in the C library. The C++
    >> Standard does not specify what kind of sort algorithm is used for
    >> std::sort, std::stable_sort, and std::partial_sort[_copy].
    >>
    >> V

    >
    > Ok I have found it here:
    >
    > http://www.codecogs.com/cog-1
    >
    > but I am not sure of the quality of the code from this place and it
    > seems that its not downloadable like boost or other quality
    > expansions.
    > Any experience with codecogs?


    Nope. I am a programmer, not a downloader/integrator. I use books
    and other publications to learn the algorithms which I then implement
    [and often modify] to suit our team's needs.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 17, 2007
    #4
  5. desktop

    desktop Guest

    Victor Bazarov wrote:
    > desktop wrote:
    >> Victor Bazarov wrote:
    >>> desktop wrote:
    >>>> Is the bucket sort container/algorithm built in somewhere in the C++
    >>>> std or do I have to implement it myself?
    >>> There is no bubble sort either. And no Shell sort. And no merge
    >>> sort. Actually, come to think of it, only Quick sort is identified,
    >>> and it's in the C++ library because it's in the C library. The C++
    >>> Standard does not specify what kind of sort algorithm is used for
    >>> std::sort, std::stable_sort, and std::partial_sort[_copy].
    >>>
    >>> V

    >> Ok I have found it here:
    >>
    >> http://www.codecogs.com/cog-1
    >>
    >> but I am not sure of the quality of the code from this place and it
    >> seems that its not downloadable like boost or other quality
    >> expansions.
    >> Any experience with codecogs?

    >
    > Nope. I am a programmer, not a downloader/integrator. I use books
    > and other publications to learn the algorithms which I then implement
    > [and often modify] to suit our team's needs.
    >
    > V


    In that case can you recommend a good book on data structures/algorithms
    for C++?

    I already have Sedegewicks 2 books for C and Thomas H Cormens
    Introduction to Algorithms but would like to find something specific for
    C++ with code samples.
    desktop, Sep 17, 2007
    #5
  6. desktop

    Guest

    On Sep 17, 4:00 pm, desktop <> wrote:
    > Victor Bazarov wrote:
    > > desktop wrote:
    > >> Victor Bazarov wrote:
    > >>> desktop wrote:
    > >>>> Is the bucket sort container/algorithm built in somewhere in the C++
    > >>>> std or do I have to implement it myself?
    > >>> There is no bubble sort either. And no Shell sort. And no merge
    > >>> sort. Actually, come to think of it, only Quick sort is identified,
    > >>> and it's in the C++ library because it's in the C library. The C++
    > >>> Standard does not specify what kind of sort algorithm is used for
    > >>> std::sort, std::stable_sort, and std::partial_sort[_copy].

    >
    > >>> V
    > >> Ok I have found it here:

    >
    > >>http://www.codecogs.com/cog-1

    >
    > >> but I am not sure of the quality of the code from this place and it
    > >> seems that its not downloadable like boost or other quality
    > >> expansions.
    > >> Any experience with codecogs?

    >
    > > Nope. I am a programmer, not a downloader/integrator. I use books
    > > and other publications to learn the algorithms which I then implement
    > > [and often modify] to suit our team's needs.

    >
    > > V

    >
    > In that case can you recommend a good book on data structures/algorithms
    > for C++?
    >
    > I already have Sedegewicks 2 books for C and Thomas H Cormens
    > Introduction to Algorithms but would like to find something specific for
    > C++ with code samples.- Hide quoted text -
    >
    > - Show quoted text -

    A quick google search indicates that the NIST website has a bucket
    sort
    algorithm. It looks to be in C but you can use that as a starting
    point.

    BTW, the NIST library is mentioned in this NG's FAQ.
    , Sep 17, 2007
    #6
  7. desktop

    Default User Guest

    Victor Bazarov wrote:

    > desktop wrote:
    > > Is the bucket sort container/algorithm built in somewhere in the C++
    > > std or do I have to implement it myself?

    >
    > There is no bubble sort either. And no Shell sort. And no merge
    > sort. Actually, come to think of it, only Quick sort is identified,
    > and it's in the C++ library because it's in the C library.


    Nope. The qsort() function doesn't specify a sorting algorithm.




    Brian
    Default User, Sep 17, 2007
    #7
  8. desktop wrote:
    > Victor Bazarov wrote:
    >> [..] I am a programmer, not a downloader/integrator. I use books
    >> and other publications to learn the algorithms which I then implement
    >> [and often modify] to suit our team's needs.
    >>
    >> V

    >
    > In that case can you recommend a good book on data
    > structures/algorithms for C++?


    Don't be ridiculous. There is no single book that contains all
    algorithms one can ever need. Not to mention with code samples.

    > I already have Sedegewicks 2 books for C and Thomas H Cormens
    > Introduction to Algorithms but would like to find something specific
    > for C++ with code samples.


    If you want to develop/grow as a programmer, you don't need code
    samples. If you, however, just need to get from point A to point B
    in your development tasks, and move on to other tasks, think of some
    third-party library. Books can be outdated, and often full of typos.

    Here are some useful books where some algorithms can be found:

    "Scientific and Engineering C++"
    "Numeric Recipes for C++"
    "Graphics Gems" series
    "The Art of Computer Programming"

    .... and plenty of field-specific ones, of course. But don't rely
    on any book alone.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 17, 2007
    #8
  9. desktop

    red floyd Guest

    Default User wrote:
    > Victor Bazarov wrote:
    >
    >> desktop wrote:
    >>> Is the bucket sort container/algorithm built in somewhere in the C++
    >>> std or do I have to implement it myself?

    >> There is no bubble sort either. And no Shell sort. And no merge
    >> sort. Actually, come to think of it, only Quick sort is identified,
    >> and it's in the C++ library because it's in the C library.

    >
    > Nope. The qsort() function doesn't specify a sorting algorithm.
    >


    Not only that, but [in C99] it doesn't even specify a time complexity
    (see ISO/IEC 9899:1999 7.20.5.2)
    red floyd, Sep 17, 2007
    #9
  10. desktop

    James Kanze Guest

    On Sep 17, 9:34 pm, "Victor Bazarov" <> wrote:
    > desktop wrote:
    > > Is the bucket sort container/algorithm built in somewhere in the C++
    > > std or do I have to implement it myself?


    > There is no bubble sort either. And no Shell sort. And no merge sort.
    > Actually, come to think of it, only Quick sort is identified, and it's
    > in the C++ library because it's in the C library. The C++ Standard
    > does not specify what kind of sort algorithm is used for std::sort,
    > std::stable_sort, and std::partial_sort[_copy].


    Even quick sort isn't identified. The name of the C function,
    qsort, is suggestive, but as far as the C standard is concerned,
    an implementation is free the use bubble sort, if that's what it
    wants (and a linear search for bsearch). The C standard makes
    no statements concerning the algorithm, NOR any concerning the
    complexity.

    The C++ standard specifies the complexity of std::sort as being
    "Approximately N log(N) (where N == last - first ) comparisons
    on the average." Putting aside for a moment the question as to
    what "approximately" means in normative text, the intent is
    obviously that quick sort, or something better, be used. Heap
    sort, however, would definitely be legal, and I believe that
    many implementations today use some sort of mixed algorithm,
    starting with quick sort, but switching to heap sort if it
    detects a degenerate case (which would result in quick sort
    taking O(n^2) time). (Historically, of course, many quick sort
    algorithms switch to something simpler, like insertion sort,
    when the partition size falls below a certain threashold.)

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Sep 18, 2007
    #10
  11. desktop

    Ole Nielsby Guest

    Ole Nielsby, Sep 18, 2007
    #11
  12. Ole Nielsby wrote:
    > Victor Bazarov <> wrote:
    >
    >> If you want to develop/grow as a programmer, you don't need code
    >> samples.

    >
    > Are you serious?
    >
    > We got from http://www.biopix.dk/Photo.asp?Language=da&PhotoId=10118
    > to
    > http://content.techrepublic.com.com/2347-10877_11-32968-32969.html?seq=1
    >
    > by learning from the doings of others.
    >
    > But who cares - it's just the same old silicon.


    You're apparently misreading (or misinterpreting) what I wrote. The
    OP asked for code to be downloaded and used. Reading the code to
    learn to program is a necessity, but sometimes (I find it more often
    than some, perhaps) one needs to cast some code away to overcome
    a common misconception or to avoid making the same mistake as the
    author of the code snippet.

    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Sep 18, 2007
    #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. aminer
    Replies:
    3
    Views:
    334
    aminer
    Sep 7, 2012
  2. aminer
    Replies:
    0
    Views:
    354
    aminer
    Sep 7, 2012
  3. aminer
    Replies:
    0
    Views:
    292
    aminer
    Sep 7, 2012
Loading...

Share This Page