Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!news2.euro.net!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail Return-Path: 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; 'value,': 0.04; 'singh': 0.07; 'append': 0.09; 'received:mail-bw0-f46.google.com': 0.09; 'traverse': 0.09; 'am,': 0.14; 'binary': 0.14; 'wrote:': 0.14; 'inserting': 0.16; 'programmer,': 0.16; 'received:209.85.214.46': 0.16; 'cc:addr:python-list': 0.17; 'somewhere': 0.17; 'subject:list': 0.19; 'insert': 0.19; 'header:In-Reply-To:1': 0.21; 'appropriate': 0.21; 'right.': 0.22; 'cc:2**0': 0.22; 'cc:no real name:2**0': 0.23; 'code': 0.24; 'url:mailman': 0.26; 'correct': 0.28; 'message-id:@mail.gmail.com': 0.28; 'received:209.85.214': 0.28; 'position.': 0.29; 'sat,': 0.29; 'url:ac': 0.29; 'instead': 0.29; 'cc:addr:python.org': 0.30; 'second': 0.30; 'url:listinfo': 0.30; "one's": 0.30; 'sort': 0.31; 'this.': 0.31; 'community': 0.32; 'value.': 0.32; 'does': 0.33; 'list': 0.33; "isn't": 0.33; 'url:in': 0.33; 'list.': 0.33; 'there': 0.35; 'using': 0.35; 'log': 0.36; 'received:google.com': 0.37; 'received:209.85': 0.37; 'ways': 0.37; 'case': 0.37; 'another': 0.37; 'two': 0.37; 'url:python': 0.38; 'url:org': 0.38; 'but': 0.38; 'subject:: ': 0.38; 'received:209': 0.39; 'list,': 0.39; 'best': 0.60; 'here': 0.66; 'yourself': 0.68; 'subject:Best': 0.91; 'complexity': 0.93 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=J/gxXDEfTz9y1pfMktr5VWjX65WQoCieKTNpbyn2y4U=; b=iE4i4ET0y+6ra7kKwA6BuXswfyEwDpLwEuVo+2h3ALxO3k4r3+f1BFjIhx4KO/ywwG av336LVK6ibMpBlgcUMfCJMuQjYcazvhWu2dqW2iZ4u6LgCUG93eb1A75JUJq7lB7Vvl Ow53ap4xyXqQmS4resixJzrnnYBTXBwJDsZ+o= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=dTfbjE9XABLgeZFsl/BxjfS7gNha9vkCeGvkviUDi8ybqITPMBqHTo9tPA6QPsvdox Qic2N0VvgscUtO1H8vWXAgo5S2GwQZ2xMkGh+8t0I99RzI5TyaRyV5WksVrcPcK2qyA4 7HnfL25AKGADMtB+XCNUUOchTU7FJ1X//OzX4= MIME-Version: 1.0 In-Reply-To: References: From: Shashank Singh Date: Sat, 18 Jun 2011 02:32:14 +0530 Subject: Re: Best way to insert sorted in a list To: SherjilOzair Content-Type: text/plain; charset=ISO-8859-1 Cc: python-list@python.org X-BeenThere: python-list@python.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: General discussion list for the Python programming language List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Newsgroups: comp.lang.python Message-ID: Lines: 34 NNTP-Posting-Host: 82.94.164.166 X-Trace: 1308344556 news.xs4all.nl 49046 [::ffff:82.94.164.166]:49403 X-Complaints-To: abuse@xs4all.nl Xref: x330-a1.tempe.blueboxinc.net comp.lang.python:7858 On Sat, Jun 18, 2011 at 2:23 AM, SherjilOzair wrote: > There are basically two ways to go about this. > One is, to append the new value, and then sort the list. > Another is to traverse the list, and insert the new value at the > appropriate position. > > The second one's complexity is O(N), while the first one's is O(N * > log N). Correct me if I am wrong here but isn't the second one is O(log N)? Binary search? That is when you have an already sorted list from somewhere and you are inserting just one new value. In case you are building the whole list yourself it's the same (N * log N) > > Still, the second one works much better, because C code is being used > instead of pythons. > > Still, being a programmer, using the first way (a.insert(x); > a.sort()), does not feel right. > > What has the community to say about this ? What is the best (fastest) > way to insert sorted in a list ? > -- > http://mail.python.org/mailman/listinfo/python-list > -- Regards Shashank Singh http://www.cse.iitb.ac.in/~shashanksingh