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 4.0 beta 2 "William Riker" on Tue Nov 15 07:38:39 2022 GMT+0.

Table of Contents


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:

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

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:

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.


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

2.1 zsort

zsort is a collection of portable sorting algorithms.

Author

Jorge Tavares <jorge.tavares@ieee.org>

License

MIT

Version

0.1

Dependency

alexandria (system).

Source

zsort.asd.

Child Components

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   [Contents][Index]

3.1.1 zsort/zsort.asd

Source

zsort.asd.

Parent Component

zsort (system).

ASDF Systems

zsort.


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

3.1.2 zsort/packages.lisp

Source

zsort.asd.

Parent Component

zsort (system).

Packages

zsort.


3.1.3 zsort/base.lisp

Dependency

packages.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).

Internals

sort-dispatch (macro).


3.1.4 zsort/insertion-sort.lisp

Dependency

base.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).

Public Interface

insertion-sort (function).

Internals

insertion-sort-body (macro).


3.1.5 zsort/quicksort.lisp

Dependency

insertion-sort.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).

Public Interface
Internals

3.1.6 zsort/merge-sort.lisp

Dependency

quicksort.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).

Public Interface

merge-sort (function).

Internals

3.1.7 zsort/heapsort.lisp

Dependency

merge-sort.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).

Public Interface

heapsort (function).

Internals

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

3.1.8 zsort/counting-sort.lisp

Dependency

heapsort.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).

Public Interface

counting-sort (function).

Internals

counting-sort-body (macro).


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

3.2 Static


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

3.2.1 zsort/README

Dependency

counting-sort.lisp (file).

Source

zsort.asd.

Parent Component

zsort (system).


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

3.2.2 zsort/LICENSE

Dependency

readme (file).

Source

zsort.asd.

Parent Component

zsort (system).


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.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

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


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

5.1 Public Interface


5.1.1 Ordinary functions

Function: counting-sort (sequence &key ascend min max)
Package

zsort.

Source

counting-sort.lisp.

Function: heapsort (sequence predicate &key key)
Package

zsort.

Source

heapsort.lisp.

Function: insertion-sort (sequence predicate &key key)
Package

zsort.

Source

insertion-sort.lisp.

Function: merge-sort (sequence predicate &key key)
Package

zsort.

Source

merge-sort.lisp.

Function: quicksort (sequence predicate &key key)
Package

zsort.

Source

quicksort.lisp.

Function: randomized-quicksort (sequence predicate &key key)
Package

zsort.

Source

quicksort.lisp.


5.2 Internals


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

5.2.1 Macros

Macro: build-heap (seq type len-1 pred &optional key)
Package

zsort.

Source

heapsort.lisp.

Macro: counting-sort-body (type ref ascend sequence end min max)
Package

zsort.

Source

counting-sort.lisp.

Macro: heapify (seq vector-ref root max pred &optional key)
Package

zsort.

Source

heapsort.lisp.

Macro: heapsort-body (type ref predicate sequence key end)
Package

zsort.

Source

heapsort.lisp.

Macro: insertion-sort-body (type ref predicate sequence key start end)
Package

zsort.

Source

insertion-sort.lisp.

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.

Macro: merge-sort-body (type ref mpredicate msequence mkey mstart mend)
Package

zsort.

Source

merge-sort.lisp.

Macro: quicksort-body (type ref mpredicate msequence mkey mstart mend pick-pivot)
Package

zsort.

Source

quicksort.lisp.

Macro: sort-dispatch (sort-body predicate sequence &rest args)
Package

zsort.

Source

base.lisp.


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

5.2.2 Ordinary functions

Function: bounded-random (min max)
Package

zsort.

Source

quicksort.lisp.

Function: median-of-3-pivot (start end)
Package

zsort.

Source

quicksort.lisp.

Function: median-pivot (start end)
Package

zsort.

Source

quicksort.lisp.


Appendix A Indexes


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

A.1 Concepts


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

A.2 Functions

Jump to:   B   C   F   H   I   M   Q   R   S  
Index Entry  Section

B
bounded-random: Private ordinary functions
build-heap: Private macros

C
counting-sort: Public ordinary functions
counting-sort-body: Private macros

F
Function, bounded-random: Private ordinary functions
Function, counting-sort: Public ordinary functions
Function, heapsort: Public ordinary functions
Function, insertion-sort: Public ordinary functions
Function, median-of-3-pivot: Private ordinary functions
Function, median-pivot: Private ordinary functions
Function, merge-sort: Public ordinary functions
Function, quicksort: Public ordinary functions
Function, randomized-quicksort: Public ordinary functions

H
heapify: Private macros
heapsort: Public ordinary functions
heapsort-body: Private macros

I
insertion-sort: Public ordinary functions
insertion-sort-body: Private macros

M
Macro, build-heap: Private macros
Macro, counting-sort-body: Private macros
Macro, heapify: Private macros
Macro, heapsort-body: Private macros
Macro, insertion-sort-body: Private macros
Macro, merge-sequences-body: Private macros
Macro, merge-sort-body: Private macros
Macro, quicksort-body: Private macros
Macro, sort-dispatch: Private macros
median-of-3-pivot: Private ordinary functions
median-pivot: Private ordinary functions
merge-sequences-body: Private macros
merge-sort: Public ordinary functions
merge-sort-body: Private macros

Q
quicksort: Public ordinary functions
quicksort-body: Private macros

R
randomized-quicksort: Public ordinary functions

S
sort-dispatch: Private macros

Jump to:   B   C   F   H   I   M   Q   R   S  

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

A.3 Variables