Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #7860

Re: Best way to insert sorted in a list

Path csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!feeder.news-service.com!newsfeed.xs4all.nl!newsfeed6.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <ian.g.kelly@gmail.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.011
X-Spam-Evidence '*H*': 0.98; '*S*': 0.00; 'singh': 0.07; 'python': 0.08; 'pm,': 0.10; 'binary': 0.14; 'wrote:': 0.14; 'inserting': 0.16; 'n),': 0.16; 'somewhere': 0.17; 'subject:list': 0.19; 'insert': 0.19; 'header:In-Reply-To:1': 0.21; 'memory': 0.22; 'fri,': 0.23; 'received:209.85.161.46': 0.23; 'received:mail- fx0-f46.google.com': 0.23; 'received:209.85.161': 0.26; 'correct': 0.28; 'message-id:@mail.gmail.com': 0.28; 'lists': 0.29; 'second': 0.30; 'arrays': 0.30; 'value.': 0.32; 'to:addr:python-list': 0.33; 'list': 0.33; "isn't": 0.33; '17,': 0.35; 'actual': 0.36; 'received:google.com': 0.37; 'received:209.85': 0.37; 'but': 0.38; 'implemented': 0.38; 'subject:: ': 0.38; 'received:209': 0.39; 'finding': 0.39; 'to:addr:python.org': 0.39; 'here': 0.66; 'subject:Best': 0.91
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:content-type; bh=gNnXa2CIN+ndZK9laXzNDikTMflUbzB3hgX2cCRVYOQ=; b=xmnRrbj2zIxdTFcQcv4Z4ZyIE6QIZDELB/0wTbFwJb8CvUxWSoKOhb/6rYaka5GVru IAFKpJZxmbVOZsZP/2KvspgDt+1CIimOvJHdReXPuncOW2Ixa43lqtnGP62x3MdUX6xN 6ymUpGI5nPZkkoBJUiNdIG+/Ot+rCYFWYvUuY=
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 :content-type; b=RLu4XDgR4/7/LlgtjeWFK44VGxorlGZwDqSoDjlCA2cBQjSDt+sIMLLGG1GtW9Md8I 5N66hjaflbBdLZ6Mo46KQmQ3q4fmK5FZ/Cjcmg4Y+YF+8eFYuwa3LhfbViBit7mHT7J5 /23PpydACTDlZTMTPCjiw51s61RHluM/xJh9E=
MIME-Version 1.0
In-Reply-To <BANLkTin-76BecXqwnHCaegYQyQ24gsp9BQ@mail.gmail.com>
References <c63e771c-8968-4d7a-9c69-b7fa6ff34e09@35g2000prp.googlegroups.com> <BANLkTin-76BecXqwnHCaegYQyQ24gsp9BQ@mail.gmail.com>
From Ian Kelly <ian.g.kelly@gmail.com>
Date Fri, 17 Jun 2011 15:23:54 -0600
Subject Re: Best way to insert sorted in a list
To Python <python-list@python.org>
Content-Type text/plain; charset=ISO-8859-1
X-BeenThere python-list@python.org
X-Mailman-Version 2.1.12
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.93.1308345873.1164.python-list@python.org> (permalink)
Lines 11
NNTP-Posting-Host 82.94.164.166
X-Trace 1308345873 news.xs4all.nl 49044 [::ffff:82.94.164.166]:56340
X-Complaints-To abuse@xs4all.nl
Xref x330-a1.tempe.blueboxinc.net comp.lang.python:7860

Show key headers only | View raw

On Fri, Jun 17, 2011 at 3:02 PM, Shashank Singh
<shashank.sunny.singh@gmail.com> wrote:
> 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.

Finding the position to insert is O(log n), but the actual insert is
O(n).  This is because Python lists are implemented with arrays and
everything after the inserted item has to be moved in memory to make
space for the insert.

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Best way to insert sorted in a list SherjilOzair <sherjilozair@gmail.com> - 2011-06-17 13:53 -0700
  Re: Best way to insert sorted in a list Shashank Singh <shashank.sunny.singh@gmail.com> - 2011-06-18 02:32 +0530
  Re: Best way to insert sorted in a list Ethan Furman <ethan@stoneleaf.us> - 2011-06-17 14:31 -0700
  Re: Best way to insert sorted in a list Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 15:23 -0600
  Re: Best way to insert sorted in a list Chris Torek <nospam@torek.net> - 2011-06-17 21:48 +0000
    Re: Best way to insert sorted in a list Ethan Furman <ethan@stoneleaf.us> - 2011-06-17 15:24 -0700
    Re: Best way to insert sorted in a list Ian Kelly <ian.g.kelly@gmail.com> - 2011-06-17 17:33 -0600
      Re: Best way to insert sorted in a list Chris Torek <nospam@torek.net> - 2011-06-18 00:46 +0000
  Re: Best way to insert sorted in a list Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-06-18 02:27 +0000
  Re: Best way to insert sorted in a list Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2011-06-17 21:21 -0700
  Re: Best way to insert sorted in a list Vito De Tullio <vito.detullio@gmail.com> - 2011-06-19 16:21 +0200

csiph-web