The zsort Reference Manual

Table of Contents

The zsort Reference Manual

This is the zsort Reference Manual, version 0.1, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Mar 25 19:33:12 2020 GMT+0.

1 Introduction

Overview

zsort is a collection of portable sorting algorithms. Common lisp provides the sort and stable-sort functions but these can have different algorithms implemented according to each implementation. Also, the standard sorting function might not be the best for a certain situation. This library aims to provide developers more options. Although for most situations the standard functions are more than enough, zsort could be a useful complement.

Sorting Algorithms

The following comparison based algorithms are implemented:

• insertion-sort
• quicksort
• randomized-quicksort
• merge-sort
• heapsort

At the moment, only one non-comparison algorithm is implemented:

• counting-sort

Install

zsort is available via Quicklisp and that is the preferable method of installation. To use it, first load Quicklisp in your Common Lisp implementation and then evaluate (ql:quickload "zsort")

How to Use

All comparison sorts have the same syntax (<sort> sequence predicate &key key) and return a sorted sequence. All the functions sort destructively, i.e., keep a copy of the unsorted sequence if you wish to keep it.

Counting sort only accepts sequences without key data and can be sorted in ascending or descending order, according to the value of the :ascend key (t for ascending and nil for descending).

Although zsort accepts list sequences, the algorithms are expected to work on vectors/arrays. A specialized sort for lists will be included in the future.

Examples

CL-USER> (zsort:quicksort #(4 5 7 3 9 2 4 2 0 8 2 4 1 5 9) #'<)
 #(0 1 2 2 2 3 4 4 4 5 5 7 8 9 9)

CL-USER> (zsort:merge-sort #((4 5) (7 3) (9 2) (4 2) (0 8) (2 4) (1 5) (9 1)) #'> :key #'first)
#((9 2) (9 1) (7 3) (4 5) (4 2) (2 4) (1 5) (0 8))

CL-USER> (zsort:counting-sort #(4 5 7 3 9 2 4 2 0 8 2 4 1 5 9) :ascend t)
#(0 1 2 2 2 3 4 4 4 5 5 7 8 9 9)

Todo

The following is planned for zsort:

• More sorting algorithms, e.g., timsort, radix sort and bucket sort
• External sorting to handle large amounts of data
• Parallel implementations of some sorting algorithms

License

zsort is available under an MIT-style license. See the LICENSE file.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 zsort

Author

Jorge Tavares <jorge.tavares@ieee.org>

License

MIT

Description

zsort is a collection of portable sorting algorithms.

Version

0.1

Dependency

alexandria

Source

zsort.asd (file)

Components

• packages.lisp (file)
• base.lisp (file)
• insertion-sort.lisp (file)
• quicksort.lisp (file)
• merge-sort.lisp (file)
• heapsort.lisp (file)
• counting-sort.lisp (file)
• readme (file)
• license (file)

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.

3.1 Lisp

3.1.1 zsort.asd

Location

zsort.asd

Systems

zsort (system)

3.1.2 zsort/packages.lisp

Parent

zsort (system)

Location

packages.lisp

Packages

zsort

3.1.3 zsort/base.lisp

Dependency

packages.lisp (file)

Parent

zsort (system)

Location

base.lisp

Internal Definitions

sort-dispatch (macro)

3.1.4 zsort/insertion-sort.lisp

Dependency

base.lisp (file)

Parent

zsort (system)

Location

insertion-sort.lisp

Exported Definitions

insertion-sort (function)

Internal Definitions

insertion-sort-body (macro)

3.1.5 zsort/quicksort.lisp

Dependency

insertion-sort.lisp (file)

Parent

zsort (system)

Location

quicksort.lisp

Exported Definitions

• quicksort (function)
• randomized-quicksort (function)

Internal Definitions

• bounded-random (function)
• median-of-3-pivot (function)
• median-pivot (function)
• quicksort-body (macro)

3.1.6 zsort/merge-sort.lisp

Dependency

quicksort.lisp (file)

Parent

zsort (system)

Location

merge-sort.lisp

Exported Definitions

merge-sort (function)

Internal Definitions

• merge-sequences-body (macro)
• merge-sort-body (macro)

3.1.7 zsort/heapsort.lisp

Dependency

merge-sort.lisp (file)

Parent

zsort (system)

Location

heapsort.lisp

Exported Definitions

heapsort (function)

Internal Definitions

• build-heap (macro)
• heapify (macro)
• heapsort-body (macro)

3.1.8 zsort/counting-sort.lisp

Dependency

heapsort.lisp (file)

Parent

zsort (system)

Location

counting-sort.lisp

Exported Definitions

counting-sort (function)

Internal Definitions

counting-sort-body (macro)

3.2 Static

3.2.1 zsort/README

Dependency

counting-sort.lisp (file)

Parent

zsort (system)

Location

/home/quickref/quicklisp/dists/quicklisp/software/zsort-20120520-git/README (not found)

3.2.2 zsort/LICENSE

Dependency

readme (file)

Parent

zsort (system)

Location

LICENSE

4 Packages

Packages are listed by definition order.

4.1 zsort

zsort is a collection of portable sorting algorithms.

Source

packages.lisp (file)

Use List

common-lisp

Exported Definitions

• counting-sort (function)
• heapsort (function)
• insertion-sort (function)
• merge-sort (function)
• quicksort (function)
• randomized-quicksort (function)

Internal Definitions

• bounded-random (function)
• build-heap (macro)
• counting-sort-body (macro)
• heapify (macro)
• heapsort-body (macro)
• insertion-sort-body (macro)
• median-of-3-pivot (function)
• median-pivot (function)
• merge-sequences-body (macro)
• merge-sort-body (macro)
• quicksort-body (macro)
• sort-dispatch (macro)

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

5.1 Exported definitions

5.1.1 Functions

Function: counting-sort SEQUENCE &key ASCEND MIN MAX

Package

zsort

Source

counting-sort.lisp (file)

Function: heapsort SEQUENCE PREDICATE &key KEY

Package

zsort

Source

heapsort.lisp (file)

Function: insertion-sort SEQUENCE PREDICATE &key KEY

Package

zsort

Source

insertion-sort.lisp (file)

Function: merge-sort SEQUENCE PREDICATE &key KEY

Package

zsort

Source

merge-sort.lisp (file)

Function: quicksort SEQUENCE PREDICATE &key KEY

Package

zsort

Source

quicksort.lisp (file)

Function: randomized-quicksort SEQUENCE PREDICATE &key KEY

Package

zsort

Source

quicksort.lisp (file)

5.2 Internal definitions

5.2.1 Macros

Macro: build-heap SEQ TYPE LEN-1 PRED &optional KEY

Package

zsort

Source

heapsort.lisp (file)

Macro: counting-sort-body TYPE REF ASCEND SEQUENCE END MIN MAX

Package

zsort

Source

counting-sort.lisp (file)

Macro: heapify SEQ VECTOR-REF ROOT MAX PRED &optional KEY

Package

zsort

Source

heapsort.lisp (file)

Macro: heapsort-body TYPE REF PREDICATE SEQUENCE KEY END

Package

zsort

Source

heapsort.lisp (file)

Macro: insertion-sort-body TYPE REF PREDICATE SEQUENCE KEY START END

Package

zsort

Source

insertion-sort.lisp (file)

Macro: merge-sequences-body TYPE REF A START-A END-A B START-B END-B AUX START-AUX PREDICATE &optional KEY

Package

zsort

Source

merge-sort.lisp (file)

Macro: merge-sort-body TYPE REF MPREDICATE MSEQUENCE MKEY MSTART MEND

Package

zsort

Source

merge-sort.lisp (file)

Macro: quicksort-body TYPE REF MPREDICATE MSEQUENCE MKEY MSTART MEND PICK-PIVOT

Package

zsort

Source

quicksort.lisp (file)

Macro: sort-dispatch SORT-BODY PREDICATE SEQUENCE &rest ARGS

Package

zsort

Source

base.lisp (file)

5.2.2 Functions

Function: bounded-random MIN MAX

Package

zsort

Source

quicksort.lisp (file)

Function: median-of-3-pivot START END

Package

zsort

Source

quicksort.lisp (file)

Function: median-pivot START END

Package

zsort

Source

quicksort.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types