chickadee » chicken » sort

Module (chicken sort)

This module contains several procedures which deal with sorting of sequences (i.e., lists and vectors).

merge

merge LIST1 LIST2 LESS?procedure

merge! LIST1 LIST2 LESS?procedure

Joins two lists in sorted order. merge! is the destructive version of merge. LESS? should be a procedure of two arguments, that returns true if the first argument is to be ordered before the second argument.

sort

sort SEQUENCE LESS?procedure

sort! SEQUENCE LESS?procedure

Sort SEQUENCE, which should be a list or a vector. sort! is the destructive version of sort.

sorted?

sorted? SEQUENCE LESS?procedure

Returns true if the list or vector SEQUENCE is already sorted.

topological-sort

topological-sort DAG PREDprocedure

Sorts the directed acyclic graph dag DAG so that for every edge from vertex u to v, u will come before v in the resulting list of vertices.

DAG is a list of sublists. The car of each sublist is a vertex. The cdr is the adjacency list of that vertex, i.e. a list of all vertices to which there exists an edge from the car vertex. pred is procedure of two arguments that should compare vertices for equality.

Time complexity: O (|V| + |E|)

(topological-sort
       '((shirt tie belt)
         (tie jacket)
         (belt jacket)
         (watch)
         (pants shoes belt)
         (undershorts pants shoes)
         (socks shoes))
       eq?)

=>

(socks undershorts pants shoes watch shirt belt tie jacket)

If a cycle is detected during the sorting process, an exception of the condition kinds (exn runtime cycle) is thrown.

---

Previous: Module (chicken repl)

Next: Module (chicken string)