<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>bisect – Maintain lists in sorted order — Python Module of the Week</title>
<link rel="stylesheet" href="../_static/sphinxdoc.css" type="text/css" />
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../',
VERSION: '1.132',
COLLAPSE_INDEX: false,
FILE_SUFFIX: '.html',
HAS_SOURCE: true
};
</script>
<script type="text/javascript" src="../_static/jquery.js"></script>
<script type="text/javascript" src="../_static/underscore.js"></script>
<script type="text/javascript" src="../_static/doctools.js"></script>
<link rel="author" title="About these documents" href="../about.html" />
<link rel="top" title="Python Module of the Week" href="../index.html" />
<link rel="up" title="Data Types" href="../data_types.html" />
<link rel="next" title="sched – Generic event scheduler." href="../sched/index.html" />
<link rel="prev" title="heapq – In-place heap sort algorithm" href="../heapq/index.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
accesskey="I">index</a></li>
<li class="right" >
<a href="../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="../sched/index.html" title="sched – Generic event scheduler."
accesskey="N">next</a> |</li>
<li class="right" >
<a href="../heapq/index.html" title="heapq – In-place heap sort algorithm"
accesskey="P">previous</a> |</li>
<li><a href="../contents.html">PyMOTW</a> »</li>
<li><a href="../data_types.html" accesskey="U">Data Types</a> »</li>
</ul>
</div>
<div class="sphinxsidebar">
<div class="sphinxsidebarwrapper">
<h3><a href="../contents.html">Table Of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">bisect – Maintain lists in sorted order</a><ul>
<li><a class="reference internal" href="#example">Example</a></li>
</ul>
</li>
</ul>
<h4>Previous topic</h4>
<p class="topless"><a href="../heapq/index.html"
title="previous chapter">heapq – In-place heap sort algorithm</a></p>
<h4>Next topic</h4>
<p class="topless"><a href="../sched/index.html"
title="next chapter">sched – Generic event scheduler.</a></p>
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="../_sources/bisect/index.txt"
rel="nofollow">Show Source</a></li>
</ul>
<div id="searchbox" style="display: none">
<h3>Quick search</h3>
<form class="search" action="../search.html" method="get">
<input type="text" name="q" size="18" />
<input type="submit" value="Go" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
<p class="searchtip" style="font-size: 90%">
Enter search terms or a module, class or function name.
</p>
</div>
<script type="text/javascript">$('#searchbox').show(0);</script>
</div>
</div>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body">
<div class="section" id="module-bisect">
<span id="bisect-maintain-lists-in-sorted-order"></span><h1>bisect – Maintain lists in sorted order<a class="headerlink" href="#module-bisect" title="Permalink to this headline">¶</a></h1>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Purpose:</th><td class="field-body">Maintains a list in sorted order without having to call sort each time an item is added to the list.</td>
</tr>
<tr class="field"><th class="field-name">Python Version:</th><td class="field-body">1.4</td>
</tr>
</tbody>
</table>
<p>The bisect module implements an algorithm for inserting elements into a list
while maintaining the list in sorted order. This can be much more efficient
than repeatedly sorting a list, or explicitly sorting a large list after it is
constructed.</p>
<div class="section" id="example">
<h2>Example<a class="headerlink" href="#example" title="Permalink to this headline">¶</a></h2>
<p>Let’s look at a simple example using bisect.insort(), which inserts items into
a list in sorted order.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">bisect</span>
<span class="kn">import</span> <span class="nn">random</span>
<span class="c"># Use a constant see to ensure that we see</span>
<span class="c"># the same pseudo-random numbers each time</span>
<span class="c"># we run the loop.</span>
<span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="c"># Generate 20 random numbers and</span>
<span class="c"># insert them into a list in sorted</span>
<span class="c"># order.</span>
<span class="n">l</span> <span class="o">=</span> <span class="p">[]</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">):</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">100</span><span class="p">)</span>
<span class="n">position</span> <span class="o">=</span> <span class="n">bisect</span><span class="o">.</span><span class="n">bisect</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span>
<span class="n">bisect</span><span class="o">.</span><span class="n">insort</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'</span><span class="si">%2d</span><span class="s"> </span><span class="si">%2d</span><span class="s">'</span> <span class="o">%</span> <span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">position</span><span class="p">),</span> <span class="n">l</span>
</pre></div>
</div>
<p>The output for that script is:</p>
<div class="highlight-python"><pre>$ python bisect_example.py
14 0 [14]
85 1 [14, 85]
77 1 [14, 77, 85]
26 1 [14, 26, 77, 85]
50 2 [14, 26, 50, 77, 85]
45 2 [14, 26, 45, 50, 77, 85]
66 4 [14, 26, 45, 50, 66, 77, 85]
79 6 [14, 26, 45, 50, 66, 77, 79, 85]
10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
77 9 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
45 7 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23 4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]</pre>
</div>
<p>The first column shows the new random number. The second column shows the
position where the number will be inserted into the list. The remainder of
each line is the current sorted list.</p>
<p>This is a simple example, and for the amount of data we are manipulating it
might be faster to simply build the list and then sort it once. But for long
lists, significant time and memory savings can be achieved using an insertion
sort algorithm such as this.</p>
<p>You probably noticed that the result set above includes a few repeated values
(45 and 77). The bisect module provides 2 ways to handle repeats. New values
can be inserted to the left of existing values, or to the right. The insort()
function is actually an alias for insort_right(), which inserts after the
existing value. The corresponding function insort_left() inserts before the
existing value.</p>
<p>If we manipulate the same data using bisect_left() and insort_left(), we end
up with the same sorted list but notice that the insert positions are
different for the duplicate values.</p>
<div class="highlight-python"><div class="highlight"><pre><span class="kn">import</span> <span class="nn">bisect</span>
<span class="kn">import</span> <span class="nn">random</span>
<span class="c"># Reset the seed</span>
<span class="n">random</span><span class="o">.</span><span class="n">seed</span><span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="c"># Use bisect_left and insort_left.</span>
<span class="n">l</span> <span class="o">=</span> <span class="p">[]</span>
<span class="k">for</span> <span class="n">i</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">20</span><span class="p">):</span>
<span class="n">r</span> <span class="o">=</span> <span class="n">random</span><span class="o">.</span><span class="n">randint</span><span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">100</span><span class="p">)</span>
<span class="n">position</span> <span class="o">=</span> <span class="n">bisect</span><span class="o">.</span><span class="n">bisect_left</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span>
<span class="n">bisect</span><span class="o">.</span><span class="n">insort_left</span><span class="p">(</span><span class="n">l</span><span class="p">,</span> <span class="n">r</span><span class="p">)</span>
<span class="k">print</span> <span class="s">'</span><span class="si">%2d</span><span class="s"> </span><span class="si">%2d</span><span class="s">'</span> <span class="o">%</span> <span class="p">(</span><span class="n">r</span><span class="p">,</span> <span class="n">position</span><span class="p">),</span> <span class="n">l</span>
</pre></div>
</div>
<div class="highlight-python"><pre>$ python bisect_example2.py
14 0 [14]
85 1 [14, 85]
77 1 [14, 77, 85]
26 1 [14, 26, 77, 85]
50 2 [14, 26, 50, 77, 85]
45 2 [14, 26, 45, 50, 77, 85]
66 4 [14, 26, 45, 50, 66, 77, 85]
79 6 [14, 26, 45, 50, 66, 77, 79, 85]
10 0 [10, 14, 26, 45, 50, 66, 77, 79, 85]
3 0 [3, 10, 14, 26, 45, 50, 66, 77, 79, 85]
84 9 [3, 10, 14, 26, 45, 50, 66, 77, 79, 84, 85]
44 4 [3, 10, 14, 26, 44, 45, 50, 66, 77, 79, 84, 85]
77 8 [3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
1 0 [1, 3, 10, 14, 26, 44, 45, 50, 66, 77, 77, 79, 84, 85]
45 6 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 77, 77, 79, 84, 85]
73 10 [1, 3, 10, 14, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
23 4 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85]
95 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 95]
91 17 [1, 3, 10, 14, 23, 26, 44, 45, 45, 50, 66, 73, 77, 77, 79, 84, 85, 91, 95]</pre>
</div>
<p>In addition to the Python implementation, there is a faster C implementation
available. If the C version is present, that implementation overrides the pure
Python implementation automatically when you import the bisect module.</p>
<div class="admonition-see-also admonition seealso">
<p class="first admonition-title">See also</p>
<dl class="docutils">
<dt><a class="reference external" href="http://docs.python.org/library/bisect.html">bisect</a></dt>
<dd>The standard library documentation for this module.</dd>
<dt><a class="reference external" href="http://en.wikipedia.org/wiki/Insertion_sort">WikiPedia: Insertion Sort</a></dt>
<dd>A description of the insertion sort algorithm.</dd>
</dl>
<p class="last"><a class="reference internal" href="../articles/data_structures.html#article-data-structures"><em>In-Memory Data Structures</em></a></p>
</div>
</div>
</div>
</div>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li class="right" style="margin-right: 10px">
<a href="../genindex.html" title="General Index"
>index</a></li>
<li class="right" >
<a href="../py-modindex.html" title="Python Module Index"
>modules</a> |</li>
<li class="right" >
<a href="../sched/index.html" title="sched – Generic event scheduler."
>next</a> |</li>
<li class="right" >
<a href="../heapq/index.html" title="heapq – In-place heap sort algorithm"
>previous</a> |</li>
<li><a href="../contents.html">PyMOTW</a> »</li>
<li><a href="../data_types.html" >Data Types</a> »</li>
</ul>
</div>
<div class="footer">
© Copyright Doug Hellmann.
Last updated on Oct 24, 2010.
Created using <a href="http://sphinx.pocoo.org/">Sphinx</a>.
<br/><a href="http://creativecommons.org/licenses/by-nc-sa/3.0/us/" rel="license"><img alt="Creative Commons License" style="border-width:0" src="http://i.creativecommons.org/l/by-nc-sa/3.0/us/88x31.png"/></a>
</div>
</body>
</html>