Dictionary of Algorithms and Data Structures és una col·lecció d'algorismes, tècniques algorísmiques, estructures de dades i definicions relacionades. En alguns casos, es complementa amb problemes i la seva solució.

Un exemple és l'explicació del quicksort

quicksort

(algorithm)

Definition: Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.

Generalization (I am a kind of …)
in-place sort.

Specialization (… is a kind of me.)
balanced quicksort, multikey Quicksort, introspective sort.

Aggregate child (… is a part of or used in me.)
partition, divide and conquer, recursion, Select, sublinear time algorithm.

See also external quicksort.

Note: Quicksort has running time Θ(n²) in the worst case, but it is typically O(n log n). In practical situations, a finely tuned implementation of quicksort beats most sort algorithms, including sort algorithms whose theoretical complexity is O(n log n) in the worst case.

Select can be used to always pick good pivots, thus giving a variant with O(n log n) worst-case running time.

Author: CM

Implementation

Robert Sedgewick's talk showing that with Bentley-McIlroy 3-way partitioning Quicksort Is Optimal © (pdf format) for random files possibly with duplicate keys; includes discussion and proof. Wikipedia entry with extended discussion and alternatives (C, Python, Haskell, pseudocode). Demos and code for enhanced, fast, quicksort, and quicksort with bubble sort (Java). (Java). (Scheme). In-line compare (Rexx), compare function (Rexx).

More information

Java applet animation (Java). Comparison of quicksort, heapsort, and merge sort on modern processors.

M'ha emocionat trobar exemples escrits en REXX

Un excel·lent recurs per estudiants i professors de programació.