Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Bucketsort?

Reply
Thread Tools

Bucketsort?

 
 
desktop
Guest
Posts: n/a
 
      09-17-2007
Is the bucket sort container/algorithm built in somewhere in the C++ std
or do I have to implement it myself?
 
Reply With Quote
 
 
 
 
Victor Bazarov
Guest
Posts: n/a
 
      09-17-2007
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:artial_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


 
Reply With Quote
 
 
 
 
desktop
Guest
Posts: n/a
 
      09-17-2007
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:artial_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?
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      09-17-2007
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:artial_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


 
Reply With Quote
 
desktop
Guest
Posts: n/a
 
      09-17-2007
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:artial_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.
 
Reply With Quote
 
AnonMail2005@gmail.com
Guest
Posts: n/a
 
      09-17-2007
On Sep 17, 4:00 pm, desktop <(E-Mail Removed)> 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:artial_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.

 
Reply With Quote
 
Default User
Guest
Posts: n/a
 
      09-17-2007
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
 
Reply With Quote
 
Victor Bazarov
Guest
Posts: n/a
 
      09-17-2007
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


 
Reply With Quote
 
red floyd
Guest
Posts: n/a
 
      09-17-2007
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)
 
Reply With Quote
 
James Kanze
Guest
Posts: n/a
 
      09-18-2007
On Sep 17, 9:34 pm, "Victor Bazarov" <(E-Mail Removed)> 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:artial_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:(E-Mail Removed)
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

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off




Advertisments