Re: An interview question
- From: user923005 <dcorbit@xxxxxxxxx>
- Date: Tue, 25 Sep 2007 12:04:10 -0700
On Sep 21, 9:45 pm, xhli <dante.hay...@xxxxxxxxx> wrote:
Hi, all, I have an interview question I don't know:
The interviewer said that in C++ std lib, sorting algorithm is quick sort
by default, while in Java, the default one is merge sort.
There is no formal definition for the algorithm used in the C++
standard library. The standard library defines the interface for
qsort() as follows:
"4 The function signature:
qsort(void *, size_t, size_t,
int (*)(const void *, const void *));
is replaced by the two declarations:
extern "C" void qsort(void* base, size_t nmemb, size_t size,
int (*compar)(const void*, const void*));
extern "C++" void qsort(void* base, size_t nmemb, size_t size,
int (*compar)(const void*, const void*));
[Note: Because the function argument compar() may throw an exception,
bsearch() and qsort()
are allowed to propagate the exception (17.4.4.8). -end note]"
No doubt, the interviewer was fooled by the *name* of the interface
being qsort. In reality, most C++ standard library sorts will be
either introspective sort or Singleton's sort (ACM algorithm 347). A
few of them may use heapsort (I know of a UNIX library that used to
use heapsort, but I guess that it has been replaced by introspective
sort by now).
He's wrong about Java too. This is from Sun's documentation on
http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html :
"(For example, the algorithm used by sort(Object[]) does not have to
be a mergesort, but it does have to be stable.) "
Why there are scuh
difference?
The difference between the two interfaces is that the C and C++
library does not demand that qsort() be stable while Java demands a
stable sort.
And what is the benefits?
It makes debugging easier for Java sorting because the order will
always be the same. The C and C++ interface will be faster most of
the time.
Does any one have any ideas?
Yes, I have lots of ideas.
.
- Prev by Date: Re: [Q] big function vs many small functions
- Next by Date: Where does programming begin?
- Previous by thread: Re: An interview question
- Next by thread: Re: An interview question
- Index(es):
Relevant Pages
|
