1 | [[tags: manual]] |
---|

2 | [[toc:]] |
---|

3 | |
---|

4 | == Module (chicken sort) |
---|

5 | |
---|

6 | This 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 | |
---|

14 | Joins two lists in sorted order. {{merge!}} is the destructive |
---|

15 | version of merge. {{LESS? }} should be a procedure of two arguments, |
---|

16 | that returns true if the first argument is to be ordered before the |
---|

17 | second argument. |
---|

18 | |
---|

19 | |
---|

20 | === sort |
---|

21 | |
---|

22 | <procedure>(sort SEQUENCE LESS?)</procedure><br> |
---|

23 | <procedure>(sort! SEQUENCE LESS?)</procedure> |
---|

24 | |
---|

25 | Sort {{SEQUENCE}}, which should be a list or a vector. {{sort!}} |
---|

26 | is the destructive version of sort. |
---|

27 | |
---|

28 | |
---|

29 | === sorted? |
---|

30 | |
---|

31 | <procedure>(sorted? SEQUENCE LESS?)</procedure> |
---|

32 | |
---|

33 | Returns true if the list or vector {{SEQUENCE}} is already sorted. |
---|

34 | |
---|

35 | === topological-sort |
---|

36 | |
---|

37 | <procedure>(topological-sort DAG PRED)</procedure> |
---|

38 | |
---|

39 | Sorts the directed acyclic graph dag {{DAG}} so that for every edge from vertex |
---|

40 | u 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 |
---|

43 | vertex. The cdr is the adjacency list of that vertex, i.e. a list of |
---|

44 | all vertices to which there exists an edge from the car vertex. |
---|

45 | {{pred}} is procedure of two arguments that should compare vertices |
---|

46 | for equality. |
---|

47 | |
---|

48 | Time 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 | |
---|

66 | If a cycle is detected during the sorting process, an exception of the |
---|

67 | condition kinds {{(exn runtime cycle)}} is thrown. |
---|

68 | |
---|

69 | --- |
---|

70 | Previous: [[Module (chicken repl)]] |
---|

71 | |
---|

72 | Next: [[Module (chicken string)]] |
---|