[2.5.1.1/dictionary] Change sorting order?

[Neil Cerutti]

On 2010-01-22, Steven D'Aprano <steve at REMOVE-THIS-cybersource.com.au> wrote:
> On Fri, 22 Jan 2010 13:35:26 +0000, Neil Cerutti wrote:
>> On 2010-01-22, Gilles Ganault <nospam at nospam.com> wrote:
>>> Hello
>>>
>>> I use a dictionary to keep a list of users connected to a web site.
>>>
>>> To avoid users from creating login names that start with digits in
>>> order to be listed at the top, I'd like to sort the list differently
>>> every minute so that it'll start with the next letter, eg. display the
>>> list from A...Zdigits the first time, then B...ZAdigits, etc.
>> 
>> Resorting is more work than is needed. Just choose a different starting
>> index each time you display the names, and set up your lister to
>> wrap-around to your arbitrary starting index.
>
> The original poster's requirement is to start at a new *letter*
> each time, not whatever name happens to be at index N.
>
> Unless you can predict what index to use for (say) names
> starting with "B", then your scheme doesn't work. In order to
> find that index, you have to do a linear search of the list
> after every sort, turning sorting into O(N**2) instead of
> O(N*log N).

O(N*Log N) + O(N) == O(N**2)?

Besides, the idea was to avoid sorting altogether.

-- 
Neil Cerutti