Re: questions about the STL sort()
On Jul 8, 10:32 am, feverzsj <fever...@hotmail.com> wrote:
STL sort() as an implementation of introsort, below is the
code snippet from the gnu stl.
template<typename _RandomAccessIterator, typename _Size>
void
__introsort_loop(_RandomAccessIterator __first,
_RandomAccessIterator __last,
_Size __depth_limit)
{
typedef typename iterator_traits<_RandomAccessIterator>::value_ty=
pe
_ValueType;
while (__last - __first > _S_threshold)
{
if (__depth_limit == 0)
{
std::partial_sort(__first, __last, __last);
return;
}
--__depth_limit;
_RandomAccessIterator __cut =
std::__unguarded_partition(__first, __last,
_ValueType(std::__median(*__first,
*(__first
+ (__last
- __first)
/ 2),
*(__last
- 1))));
std::__introsort_loop(__cut, __last, __depth_limit);
__last = __cut;
}
}
my question is : why not use two recursive calls to __introsort_loop,
Probably because the code was originally a quick sort (without
the __depth_limit), and they didn't want it to core dump due to
stack overflow.
it will have a clear view to present a divide-and-conquer
algorithm. Yes, it is a optimization, but tail recursion
elimination is now a common technique of today's cpp compiler.
First, I'm not sure that it's that common. Compilers optimize
for real code, and tail recursion isn't that frequent in C++.
And second, I'm not sure that the compiler can do the
optimization; if _RandomAccessIterator has a non-trivial
destructor, it certainly can't.
another question is about the __final_insertion_sort() placed after
the call to __introsort_loop()
below is the code snippet.
template<typename _RandomAccessIterator>
void
__final_insertion_sort(_RandomAccessIterator __first,
_RandomAccessIterator __last)
{
if (__last - __first > _S_threshold)
{
std::__insertion_sort(__first, __first + _S_threshold);
std::__unguarded_insertion_sort(__first + _S_threshold, _=
_last);
}
else
std::__insertion_sort(__first, __last);
}
why not just call one __insertion_sort in the if-condition?
Probably optimization. Without seeing where this function is
called, and what the differences are between the two insertion
sorts, it's hard to say, but just guessing... this function is
called when the quick sort has partitionned the total range into
blocks of _S_threshold size, and all of the values in one block
are greater than the values in all previous blocks, and less
then the values in all following blocks. The standard insertion
sort will have to check for the bottom of the array in the inner
loop, something like (i and j are iterators):
for ( i = first + 1 ; i != last ; ++ i ) {
T tmp = *i ;
j = i ;
while ( j != first && *(j-1) > tmp ) {
*j = *(j-1) ;
-- j ;
}
*j = tmp ;
}
If you're sorting anything but the first block after the
partitionning, you don't need the j != first test in the inner
loop.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34