# The zsort Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

# The zsort Reference Manual

This is the zsort Reference Manual, version 0.1, generated automatically by Declt version 2.4 "Will Decker" on Wed Jun 20 12:47:42 2018 GMT+0.

Next: , Previous: , Up: Top   [Contents][Index]

# 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

Next: , Previous: , Up: Top   [Contents][Index]

## 2 Systems

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

Previous: , Up: Systems   [Contents][Index]

### 2.1 zsort

Author

Jorge Tavares <jorge.tavares@ieee.org>

MIT

Description

zsort is a collection of portable sorting algorithms.

Version

0.1

Dependency

alexandria

Source

zsort.asd (file)

Components

Next: , Previous: , Up: Top   [Contents][Index]

## 3 Files

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

Next: , Previous: , Up: Files   [Contents][Index]

### 3.1 Lisp

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.1 zsort.asd

Location

zsort.asd

Systems

zsort (system)

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.2 zsort/packages.lisp

Parent

zsort (system)

Location

packages.lisp

Packages

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.3 zsort/base.lisp

Dependency

packages.lisp (file)

Parent

zsort (system)

Location

base.lisp

Internal Definitions

sort-dispatch (macro)

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 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)

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.5 zsort/quicksort.lisp

Dependency

insertion-sort.lisp (file)

Parent

zsort (system)

Location

quicksort.lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 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

Next: , Previous: , Up: Lisp files   [Contents][Index]

#### 3.1.7 zsort/heapsort.lisp

Dependency

merge-sort.lisp (file)

Parent

zsort (system)

Location

heapsort.lisp

Exported Definitions

heapsort (function)

Internal Definitions

Previous: , Up: Lisp files   [Contents][Index]

#### 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)

Previous: , Up: Files   [Contents][Index]

### 3.2 Other

Next: , Previous: , Up: Other files   [Contents][Index]

Dependency

counting-sort.lisp (file)

Parent

zsort (system)

Location

Previous: , Up: Other files   [Contents][Index]

Dependency

Parent

zsort (system)

Location

Next: , Previous: , Up: Top   [Contents][Index]

## 4 Packages

Packages are listed by definition order.

Previous: , Up: Packages   [Contents][Index]

### 4.1 zsort

zsort is a collection of portable sorting algorithms.

Source

packages.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

Next: , Previous: , Up: Top   [Contents][Index]

## 5 Definitions

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

Next: , Previous: , Up: Definitions   [Contents][Index]

### 5.1 Exported definitions

Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.1 Functions

Function: counting-sort SEQUENCE &key ASCEND MIN MAX
Package
Source

counting-sort.lisp (file)

Function: heapsort SEQUENCE PREDICATE &key KEY
Package
Source

heapsort.lisp (file)

Function: insertion-sort SEQUENCE PREDICATE &key KEY
Package
Source

insertion-sort.lisp (file)

Function: merge-sort SEQUENCE PREDICATE &key KEY
Package
Source

merge-sort.lisp (file)

Function: quicksort SEQUENCE PREDICATE &key KEY
Package
Source

quicksort.lisp (file)

Function: randomized-quicksort SEQUENCE PREDICATE &key KEY
Package
Source

quicksort.lisp (file)

Previous: , Up: Definitions   [Contents][Index]

### 5.2 Internal definitions

Next: , Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.1 Macros

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

heapsort.lisp (file)

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

counting-sort.lisp (file)

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

heapsort.lisp (file)

Macro: heapsort-body TYPE REF PREDICATE SEQUENCE KEY END
Package
Source

heapsort.lisp (file)

Macro: insertion-sort-body TYPE REF PREDICATE SEQUENCE KEY START END
Package
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
Source

merge-sort.lisp (file)

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

merge-sort.lisp (file)

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

quicksort.lisp (file)

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

base.lisp (file)

Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.2 Functions

Function: bounded-random MIN MAX
Package
Source

quicksort.lisp (file)

Function: median-of-3-pivot START END
Package
Source

quicksort.lisp (file)

Function: median-pivot START END
Package
Source

quicksort.lisp (file)

Previous: , Up: Top   [Contents][Index]

## Appendix A Indexes

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.1 Concepts

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.2 Functions

Next: , Previous: , Up: Indexes   [Contents][Index]

### A.3 Variables

Previous: , Up: Indexes   [Contents][Index]

### A.4 Data types

Index Entry Section `Package, zsort`: The zsort package `System, zsort`: The zsort system `zsort`: The zsort system `zsort`: The zsort package