The Problem
of in-situ sorting with
minimal auxiliary space
in minimal time.
Introduction
In "Mathematical Analysis of Algorithms", (Information Processing '71, North Holland Publ.'72) Donald Knuth remarked "... that research on computional complexity is an interesting way to sharpen our tools for more routine problems we face from day to day."With respect to the sorting problem, Knuth points out, that time effective in-situ permutation is inherently connected with the problem of finding the cycle leaders, and in-situ permutations could easily be performed in O(n) time if we would be allowed to manipulate n extra "tag" bits specifying how much of the permutation has been carried out at any time. Without such tag bits, he concludes "it seems reasonable to conjecture that every algorithm will require for in-situ permutation at least n log n steps on the average".
Now this conjecture is shown not to be valid. A new efficient way to find cycle leaders is presented and in-situ permutations can be performed in optimal time. The algorithm FlashSort sorts in O(n) time without the manipulation of n extra "tag" bits. Here an auxiliary vector of only length m is required, where m is a small fraction of the number of elements n.
Classification
Accumulation
run the loops:
- find cycle leader
- in situ permutation
short range sorting
The FlashSort Algorithm
FlashSort sorts n elements in O(n) time. Flash-Sort uses a vector L(k) of length m in a first step for the classification of the elements of array A. Then, in a second step, the resulting counts are accumulated and the L(k) point to the class boundaries. Then the elements are sorted by in situ permutation. During the permutation, the L(k) are decremented by a unit step at each new placement of an element of class k in the array A. A crucial aspect of FlashSort is that for identifying new cycle leaders. A cycle ends, if the the vector L(k) points to the position of an element below the classboundary of class k. The new cycle leader is the element situated in the lowest position complying to the complimentary condition, i.e. for which L(k) points to a position withFinally,a small number of partially distinguishable elements are sorted locally within their classes either by recursion or by a simple conventional sort algorithm.
you find
a more detailed description
of the algorithm.
- Karl-Dietrich Neubert
The FlashSort Algorithm
This is an MS 6.0 Word document as published in the Proceedings of the
euroFORTH'97 -Conference, Oxford, England,Sept.26-28 1997
- Karl-Dietrich Neubert,
FlashSort1 Algorithm in
Dr. Dobb's Journal
Feb.1998,p.123
CLICK HERE TO SUBSCRIBE TO DDJ
A collection of
FlashSort demos-
For animations of the FlashSort principle and runtime, select
Collection of FlashSort demosA collection of
FlashSort codes-
For codes in various languages and various modifications
of the FlashSort algorithm see
Collection of FlashSort codes.
-
To go back to the Welcome page click
here.