The zsort Reference Manual

Table of Contents

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.3 "Robert April" on Tue Jan 09 16:05:11 2018 GMT+0.


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

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.


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>

License

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

zsort


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]

3.2.1 zsort/README

Dependency

counting-sort.lisp (file)

Parent

zsort (system)

Location

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


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

3.2.2 zsort/LICENSE

Dependency

readme (file)

Parent

zsort (system)

Location

LICENSE


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

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)


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

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)


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

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)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   L   O   Z  
Index Entry  Section

F
File, Lisp, zsort.asd: The zsort<dot>asd file
File, Lisp, zsort/base.lisp: The zsort/base<dot>lisp file
File, Lisp, zsort/counting-sort.lisp: The zsort/counting-sort<dot>lisp file
File, Lisp, zsort/heapsort.lisp: The zsort/heapsort<dot>lisp file
File, Lisp, zsort/insertion-sort.lisp: The zsort/insertion-sort<dot>lisp file
File, Lisp, zsort/merge-sort.lisp: The zsort/merge-sort<dot>lisp file
File, Lisp, zsort/packages.lisp: The zsort/packages<dot>lisp file
File, Lisp, zsort/quicksort.lisp: The zsort/quicksort<dot>lisp file
File, other, zsort/LICENSE: The zsort/license file
File, other, zsort/README: The zsort/readme file

L
Lisp File, zsort.asd: The zsort<dot>asd file
Lisp File, zsort/base.lisp: The zsort/base<dot>lisp file
Lisp File, zsort/counting-sort.lisp: The zsort/counting-sort<dot>lisp file
Lisp File, zsort/heapsort.lisp: The zsort/heapsort<dot>lisp file
Lisp File, zsort/insertion-sort.lisp: The zsort/insertion-sort<dot>lisp file
Lisp File, zsort/merge-sort.lisp: The zsort/merge-sort<dot>lisp file
Lisp File, zsort/packages.lisp: The zsort/packages<dot>lisp file
Lisp File, zsort/quicksort.lisp: The zsort/quicksort<dot>lisp file

O
Other File, zsort/LICENSE: The zsort/license file
Other File, zsort/README: The zsort/readme file

Z
zsort.asd: The zsort<dot>asd file
zsort/base.lisp: The zsort/base<dot>lisp file
zsort/counting-sort.lisp: The zsort/counting-sort<dot>lisp file
zsort/heapsort.lisp: The zsort/heapsort<dot>lisp file
zsort/insertion-sort.lisp: The zsort/insertion-sort<dot>lisp file
zsort/LICENSE: The zsort/license file
zsort/merge-sort.lisp: The zsort/merge-sort<dot>lisp file
zsort/packages.lisp: The zsort/packages<dot>lisp file
zsort/quicksort.lisp: The zsort/quicksort<dot>lisp file
zsort/README: The zsort/readme file

Jump to:   F   L   O   Z  

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: Internal functions
build-heap: Internal macros

C
counting-sort: Exported functions
counting-sort-body: Internal macros

F
Function, bounded-random: Internal functions
Function, counting-sort: Exported functions
Function, heapsort: Exported functions
Function, insertion-sort: Exported functions
Function, median-of-3-pivot: Internal functions
Function, median-pivot: Internal functions
Function, merge-sort: Exported functions
Function, quicksort: Exported functions
Function, randomized-quicksort: Exported functions

H
heapify: Internal macros
heapsort: Exported functions
heapsort-body: Internal macros

I
insertion-sort: Exported functions
insertion-sort-body: Internal macros

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

Q
quicksort: Exported functions
quicksort-body: Internal macros

R
randomized-quicksort: Exported functions

S
sort-dispatch: Internal macros

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

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

A.3 Variables


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

A.4 Data types

Jump to:   P   S   Z  
Index Entry  Section

P
Package, zsort: The zsort package

S
System, zsort: The zsort system

Z
zsort: The zsort system
zsort: The zsort package

Jump to:   P   S   Z