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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
|
<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!--
Generated from r6rs-lib.tex by tex2page, v 20070803
(running on MzScheme 371, unix),
(c) Dorai Sitaram,
http://www.ccs.neu.edu/~dorai/tex2page/tex2page-doc.html
-->
<head>
<title>
r6rs-lib
</title>
<link rel="stylesheet" type="text/css" href="r6rs-lib-Z-S.css" title=default>
<meta name=robots content="index,follow">
</head>
<body>
<div id=slidecontent>
<div align=right class=navigation>[Go to <span><a href="r6rs-lib.html">first</a>, <a href="r6rs-lib-Z-H-4.html">previous</a></span><span>, <a href="r6rs-lib-Z-H-6.html">next</a></span> page<span>; </span><span><a href="r6rs-lib-Z-H-1.html#node_toc_start">contents</a></span><span><span>; </span><a href="r6rs-lib-Z-H-21.html#node_index_start">index</a></span>]</div>
<p></p>
<a name="node_chap_4"></a>
<h1 class=chapter>
<div class=chapterheading><a href="r6rs-lib-Z-H-1.html#node_toc_node_chap_4">Chapter 4</a></div><br>
<a href="r6rs-lib-Z-H-1.html#node_toc_node_chap_4">Sorting</a></h1>
<p></p>
<p>
This chapter describes the <tt>(rnrs sorting (6))</tt><a name="node_idx_244"></a>library for
sorting lists and vectors.</p>
<p>
</p>
<p></p>
<div align=left><tt>(<a name="node_idx_246"></a>list-sort<i> proc list</i>)</tt> procedure </div>
<div align=left><tt>(<a name="node_idx_248"></a>vector-sort<i> proc vector</i>)</tt> procedure </div>
<p>
<i>Proc</i> should accept any two elements
of <i>list</i> or <i>vector</i>, and should not have any side
effects. <i>Proc</i> should return a true value when its first argument
is strictly less than its second, and <tt>#f</tt> otherwise.</p>
<p>
The <tt>list-sort</tt> and <tt>vector-sort</tt> procedures perform a stable
sort of <i>list</i> or <i>vector</i> in ascending order according to
<i>proc</i>, without changing <i>list</i> or
<i>vector</i> in any way. The <tt>list-sort</tt> procedure returns a
list, and <tt>vector-sort</tt> returns a vector. The results may be <tt>eq?</tt> to the argument when the argument is already sorted, and the
result of <tt>list-sort</tt> may share structure with a tail of the
original list. The sorting algorithm performs <em>O</em>(<em>n</em> lg <em>n</em>) calls to
<i>proc</i> where <em>n</em> is the length of <i>list</i> or <i>vector</i>,
and all arguments passed to <i>proc</i> are elements of the list or
vector being sorted, but the pairing of arguments and the sequencing
of calls to <i>proc</i> are not specified.
If multiple returns occur from <tt>list-sort</tt> or <tt>vector-sort</tt>, the return
values returned by earlier returns are not mutated.</p>
<p>
</p>
<tt>(list-sort < ’(3 5 2 1)) ⇒ (1 2 3 5)<br>
(vector-sort < ’<tt>#</tt>(3 5 2 1)) ⇒ <tt>#</tt>(1 2 3 5)<p></tt></p>
<p>
<em>Implementation responsibilities: </em>The implementation must check the restrictions
on <i>proc</i> to the extent performed by applying it as described.
An
implementation may check whether <i>proc</i> is an appropriate argument
before applying it.
</p>
<p></p>
<p>
</p>
<p></p>
<div align=left><tt>(<a name="node_idx_250"></a>vector-sort!<i> proc vector</i>)</tt> procedure </div>
<p>
<i>Proc</i> should accept any two elements
of the vector, and should not have any side
effects. <i>Proc</i> should return a true value when its first
argument is strictly less than its second, and <tt>#f</tt> otherwise.
The <tt>vector-sort!</tt> procedure destructively sorts <i>vector</i> in
ascending order according to <i>proc</i>. The sorting algorithm
performs <em>O</em>(<em>n</em><sup>2</sup>) calls to <i>proc</i> where <em>n</em> is the length of
<i>vector</i>, and all arguments passed to <i>proc</i> are elements
of the vector being sorted, but the pairing of arguments and the
sequencing of calls to <i>proc</i> are not specified. The sorting
algorithm may be unstable. The procedure returns unspecified values.</p>
<p>
</p>
<tt>(define v (vector 3 5 2 1))<br>
(vector-sort! v) ⇒ <em>unspecified</em><br>
v ⇒ <tt>#</tt>(1 2 3 5)<br>
<p></tt>
<em>Implementation responsibilities: </em>The implementation must check the restrictions
on <i>proc</i> to the extent performed by applying it as described.
An
implementation may check whether <i>proc</i> is an appropriate argument
before applying it.
</p>
<p></p>
<p>
</p>
<p></p>
<div class=smallskip></div>
<p style="margin-top: 0pt; margin-bottom: 0pt">
<div align=right class=navigation>[Go to <span><a href="r6rs-lib.html">first</a>, <a href="r6rs-lib-Z-H-4.html">previous</a></span><span>, <a href="r6rs-lib-Z-H-6.html">next</a></span> page<span>; </span><span><a href="r6rs-lib-Z-H-1.html#node_toc_start">contents</a></span><span><span>; </span><a href="r6rs-lib-Z-H-21.html#node_index_start">index</a></span>]</div>
</p>
<p></p>
</div>
</body>
</html>
|
