-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathquicksort.html
More file actions
86 lines (73 loc) · 4.8 KB
/
Copy pathquicksort.html
File metadata and controls
86 lines (73 loc) · 4.8 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
<!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><no title> — Python scientifique - ENS Paris</title>
<link rel="stylesheet" href="../_static/nature.css" type="text/css" />
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<script type="text/javascript">
var DOCUMENTATION_OPTIONS = {
URL_ROOT: '../',
VERSION: '2013.4',
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>
<script type="text/javascript" src="../_static/translations.js"></script>
<link rel="top" title="Python scientifique - ENS Paris" href="../index.html" />
</head>
<body>
<div class="related">
<h3>Navigation</h3>
<ul>
<li><a href="../index.html">Python scientifique - ENS Paris</a> »</li>
</ul>
</div>
<div class="document">
<div class="documentwrapper">
<div class="body">
<p id="example-quicksort-py">Quick sort</p>
<p><strong>Python source code:</strong> <a class="reference download internal" href="../_downloads/quicksort.py"><tt class="xref download docutils literal"><span class="pre">quicksort.py</span></tt></a></p>
<div class="highlight-python"><div class="highlight"><pre><span class="k">def</span> <span class="nf">quicksort</span><span class="p">(</span><span class="n">array</span><span class="p">):</span>
<div class="newline"></div> <span class="k">if</span> <span class="nb">len</span><span class="p">(</span><span class="n">array</span><span class="p">)</span> <span class="o"><=</span> <span class="mi">1</span><span class="p">:</span>
<div class="newline"></div> <span class="k">return</span> <span class="n">array</span>
<div class="newline"></div> <span class="n">pivot</span> <span class="o">=</span> <span class="n">array</span><span class="o">.</span><span class="n">pop</span><span class="p">()</span> <span class="c"># this modifies the initial list!!</span>
<div class="newline"></div> <span class="c"># to avoid this, do</span>
<div class="newline"></div> <span class="c"># copy_array = array[:]; pivot = copy_array.pop()</span>
<div class="newline"></div> <span class="n">less_than</span><span class="p">,</span> <span class="n">greater_than</span> <span class="o">=</span> <span class="p">[],</span> <span class="p">[]</span>
<div class="newline"></div> <span class="k">for</span> <span class="n">element</span> <span class="ow">in</span> <span class="n">array</span><span class="p">:</span>
<div class="newline"></div> <span class="k">if</span> <span class="n">element</span> <span class="o"><</span> <span class="n">pivot</span><span class="p">:</span>
<div class="newline"></div> <span class="n">less_than</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">element</span><span class="p">)</span>
<div class="newline"></div> <span class="k">else</span><span class="p">:</span>
<div class="newline"></div> <span class="n">greater_than</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">element</span><span class="p">)</span>
<div class="newline"></div> <span class="k">return</span> <span class="n">quicksort</span><span class="p">(</span><span class="n">less_than</span><span class="p">)</span> <span class="o">+</span> <span class="p">[</span><span class="n">pivot</span><span class="p">]</span> <span class="o">+</span> <span class="n">quicksort</span><span class="p">(</span><span class="n">greater_than</span><span class="p">)</span>
<div class="newline"></div></pre></div>
</div>
<p><div style="clear: both"></div></p>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="related">
<h3>Navigation</h3>
<ul>
<li><a href="../index.html">Python scientifique - ENS Paris</a> »</li>
</ul>
</div>
<!-- your html code here -->
<a href="http://www.ens.fr"><img src="../_static/ENS_Logo.png"
alt="ENS" height="100"></a>
<a href="http://www.inria.fr"><img src="../_static/logo-inria.jpg"
alt="INRIA" height="60"></a>
<a href="http://www.saint-gobain-recherche.fr/fr/"><img
src="../_static/logoSGR.png" alt="Saint-Gobain Recherche" height="60"></a>
<script language="JavaScript"
src="http://freehostedscripts.net/ocount.php?site=ID1953783&name=pages
visitées"></script>
</body>
</html>