[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [glob2-devel] okay to release!

From: Kai Antweiler
Subject: Re: [glob2-devel] okay to release!
Date: Wed, 04 Apr 2007 22:11:21 +0200
User-agent: Gnus/5.1007 (Gnus v5.10.7) XEmacs/21.4.20 (linux)

>> Please use std::stable_sort!
>> std::sort might use random choices when two entries have the same key.
> Its the idea that counts, and std::sort doesn't use random choices,

I don't know whether std::sort uses random choices now.
It uses introsort which is based on quicksort.
But even if it is not random now, it might be in the future.

Random choices are common in sorting algorithms.
e.g: a simple quicksort implementation without random choices
performs very poor some data.
Choosing the pivot elements randomly guarantees mostly good
performance for every input.

> its merely that it is unpredictable. Certain algorithms will move
> elements in a manner that makes them unstable, where as others will
> compare like keys and maintain relative order.

Sometimes, yes.  But sometimes randomness is used.
Take std::stable_sort and you're on the safe side.

Kai Antweiler

reply via email to

[Prev in Thread] Current Thread [Next in Thread]