validity of ... reasons for preferring C over C++

Robert Wessel <robertwessel2@yahoo.com> wrote:

(snip, I wrote)
>>>> (Good quicksort doesn't use a fixed array element as the pivot for a
>>>> partition, but maybe the median of three elemennts.  That pretty much
>>>> avoids the O(N**2) worst case.)
 
>>> Not really. It just cuts the number of steps in half: rather than the
>>> worst case consistently choosing the highest/lowest element as the
>>> partition, the worst case consistently chooses the second highest/lowest
>>> element.

(I also wrote)
>>OK, if you don't like it use the random pivot selector.

>>The problem with original quicksort wasn't that the worst case was
>>so bad, but that it was so common. 

(snip about a very unlikely way to die)

>>As someone noted, in some cases a worst case can be supplied
>>by a malicious user. For large N, not likely if you use a random
>>pivot selector and the user can't guess the seed.
 
> OTOH, a good (pseudo) random number generator is likely more work 
> than implementing Introsort, and probably would probably add enough
> overhead to Quicksort that plain Heapsort would only be marginally
> faster, if at all.  

I wondered a little about that. Seems to me that if you do random
pivot selection for enough large partitions, maybe not all that
many, and use median of three for smaller ones, you get most of
the advantage.  For even medium sized N, the permutations get large
darn fast, so your main worry is someone intentionally supplying
worst case.

> And it still doesn't *guarantee* non-quadratic
> behavior, even if it does make it unlikely (which is an issue in some
> environments).

And for some values of N.
 
> IMO, there are four sorts non-specialist programmers should know
> about, and be ready to use.  Insertion (<10 items), Shell (<2000
> items), and Heap, for things with array-like semantics.  For
> linked-list sorts of data structures, merge sort is useful option.
> Quicksort *looks* simple, but has far too many pitfalls for the
> programmer not specifically versed in the subject.  The four have few
> surprises, are simple to implement, and degrade reasonably gracefully
> when their nominal limits are (not-excessively) exceeded.

When I had a CS course (large number) years ago, for one assignment
we wrote insertion sort, selection sort, and bubble sort. For the
next one, quicksort, heapsort, and shell sort.

As was mentioned earlier, cache behavior should be considered.
My first thought is that heap sort and shell sort aren't so good
in cache use, but I haven't thought about it all that much.
I always like the 3N+1 shell sort, should work well with 
interleaved memory, but maybe not with cache.
 
> Of course in most cases, you should try to use a well 
> implemented sort library.

-- glen

Nobody wrote:
> On Wed, 29 Oct 2014 20:15:54 +0000, glen herrmannsfeldt wrote:
>
>> (Good quicksort doesn't use a fixed array element as the pivot for a
>> partition, but maybe the median of three elemennts.  That pretty much
>> avoids the O(N**2) worst case.)
>
> Not really. It just cuts the number of steps in half: rather than the
> worst case consistently choosing the highest/lowest element as the
> partition, the worst case consistently chooses the second highest/lowest
> element.
>

Sounds like a Nash equilibrium.

-- 
Les Cargill