Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.x-privat.org!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.005
X-Spam-Evidence: '*H*': 0.99; '*S*': 0.00; 'algorithm': 0.03; 'lawrence': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'subject:python': 0.11; 'applies': 0.15; 'algorithm.': 0.16; 'benjamin': 0.16; 'bisect': 0.16; 'n),': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'sorting': 0.16; 'subject:3.3': 0.16; 'worst': 0.16; 'wed,': 0.16; 'wrote:': 0.17; 'certainly': 0.17; '>>>': 0.18; 'suggested': 0.20; 'sort': 0.21; 'example': 0.23; 'elements': 0.23; "python's": 0.23; 'header:In-Reply-To:1': 0.25; 'header:User-Agent:1': 0.26; 'first,': 0.27; 'right.': 0.27; "doesn't": 0.28; 'header:X -Complaints-To:1': 0.28; 'subject:list': 0.28; 'run': 0.28; 'comparison': 0.29; "d'aprano": 0.29; 'faster,': 0.29; 'shoot': 0.29; 'steven': 0.29; 'function': 0.30; 'lists': 0.31; 'from:addr:yahoo.co.uk': 0.32; 'operate': 0.32; 'running': 0.32; 'could': 0.32; 'true.': 0.33; 'zero': 0.33; 'to:addr:python-list': 0.33; 'another': 0.33; 'minimum': 0.34; 'list': 0.35; 'faster': 0.35; 'there': 0.35; 'received:org': 0.36; 'but': 0.36; 'compare': 0.36; 'data.': 0.36; 'two': 0.37; 'being': 0.37; 'far': 0.37; 'subject:: ': 0.38; 'mark': 0.38; 'performance': 0.39; 'to:addr:python.org': 0.39; 'apply': 0.39; 'takes': 0.39; 'where': 0.40; 'header:Received:5': 0.40; 'your': 0.60; 'easy': 0.60; 'kind': 0.61; 'time,': 0.62; 'necessarily': 0.63; 'skip:n 10': 0.63; 'beat': 0.65; '2013': 0.84; 'hanging': 0.84; 'oscar': 0.84; 'subject:Min': 0.84; 'average': 0.93
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Mark Lawrence <breamoreboy@yahoo.co.uk>
Subject: Re: Finding the Min for positive and negative in python 3.3 list
Date: Wed, 13 Mar 2013 14:37:33 +0000
References: <mailman.3239.1363109618.2939.python-list@python.org> <513fdcfc$0$29965$c3e8da3$5496439d@news.astraweb.com> <loom.20130313T111109-885@post.gmane.org> <mailman.3260.1363173832.2939.python-list@python.org> <5140893b$0$29965$c3e8da3$5496439d@news.astraweb.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Gmane-NNTP-Posting-Host: host-92-18-6-95.as13285.net
User-Agent: Mozilla/5.0 (Windows NT 6.0; rv:17.0) Gecko/20130307 Thunderbird/17.0.4
In-Reply-To: <5140893b$0$29965$c3e8da3$5496439d@news.astraweb.com>
X-Antivirus: avast! (VPS 130311-2, 11/03/2013), Outbound message
X-Antivirus-Status: Clean
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <http://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <http://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.3266.1363185380.2939.python-list@python.org>
Lines: 42
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1363185380 news.xs4all.nl 6848 [2001:888:2000:d::a6]:57370
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:41179

On 13/03/2013 14:12, Steven D'Aprano wrote:
> On Wed, 13 Mar 2013 11:23:22 +0000, Oscar Benjamin wrote:
>
>> On 13 March 2013 10:43, Wolfgang Maier
>> <wolfgang.maier@biologie.uni-freiburg.de> wrote:
>>>
>>> thinking again about the question, then the min() solutions suggested
>>> so far certainly do the job and they are easy to understand. However,
>>> if you need to run the function repeatedly on larger lists, using min()
>>> is suboptimal because its performance is an O(n) one. It's faster,
>>> though less intuitive, to sort your list first, then use bisect on it
>>> to find the zero position in it. Two manipulations running at
>>> O(log(n)).
>>
>> Sort cannot be O(log(n)) and it cannot be faster than a standard O(n)
>> minimum finding algorithm. No valid sorting algorithm can have even a
>> best case performance that is better than O(n). This is because it takes
>> O(n) just to verify that a list is sorted.
>
> That's almost true. It applies to comparison sorts, that is, the kind of
> sort algorithm where you have to compare the elements being sorted to
> know where they go. But it doesn't necessarily apply to non-comparison
> sorts. For example, Bead sort could in principle operate in O(sqrt(n))
> time, or even O(1), although in practice it is O(n).
>
> Another example is Bitonic sort, which is O(log(n)**2).
>
> In practical terms though, you are right. There is no practical, general
> purpose sorting algorithm that can beat O(n) for arbitrary lists of data.
>

For the newbies hanging around there's Python's own Timsort which 
apparantly has worst case performance O(n log n), best case O(n) and 
average case O(n log n).  Please don't shoot the messenger :)



-- 
Cheers.

Mark Lawrence