source: project/wiki/man/5/Module (chicken sort) @ 35527

Last change on this file since 35527 was 34317, checked in by sjamaan, 2 years ago

man/5: Create chapter Module (chicken string)

File size: 1.8 KB
Line 
1[[tags: manual]]
2[[toc:]]
3
4== Module (chicken sort)
5
6This module contains several procedures which deal with sorting of
7''sequences'' (i.e., lists and vectors).
8
9=== merge
10
11<procedure>(merge LIST1 LIST2 LESS?)</procedure><br>
12<procedure>(merge! LIST1 LIST2 LESS?)</procedure>
13
14Joins two lists in sorted order. {{merge!}} is the destructive
15version of merge. {{LESS?  }} should be a procedure of two arguments,
16that returns true if the first argument is to be ordered before the
17second argument.
18
19
20=== sort
21
22<procedure>(sort SEQUENCE LESS?)</procedure><br>
23<procedure>(sort! SEQUENCE LESS?)</procedure>
24
25Sort {{SEQUENCE}}, which should be a list or a vector. {{sort!}}
26is the destructive version of sort.
27
28
29=== sorted?
30
31<procedure>(sorted? SEQUENCE LESS?)</procedure>
32
33Returns true if the list or vector {{SEQUENCE}} is already sorted.
34
35=== topological-sort
36
37<procedure>(topological-sort DAG PRED)</procedure>
38
39Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex
40u to v, u will come before v in the resulting list of vertices.
41
42{{DAG}} is a list of sublists. The car of each sublist is a
43vertex. The cdr is the adjacency list of that vertex, i.e. a list of
44all vertices to which there exists an edge from the car vertex.
45{{pred}} is procedure of two arguments that should compare vertices
46for equality.
47
48Time complexity: O (|V| + |E|)
49
50<enscript highlight=scheme>
51(topological-sort
52       '((shirt tie belt)
53         (tie jacket)
54         (belt jacket)
55         (watch)
56         (pants shoes belt)
57         (undershorts pants shoes)
58         (socks shoes))
59       eq?)
60
61=>
62
63(socks undershorts pants shoes watch shirt belt tie jacket)
64</enscript>
65
66If a cycle is detected during the sorting process, an exception of the
67condition kinds {{(exn runtime cycle)}} is thrown.
68
69---
70Previous: [[Module (chicken repl)]]
71
72Next: [[Module (chicken string)]]
Note: See TracBrowser for help on using the repository browser.