www.neubert.net - Dr. Neubert's Website
The Entropy Reduction Laboratory

A Collection of animated FlashSort Demonstrations


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 with L(k(A(i))) >= i. Evidently, in addition to the array A of length n which holds the n elements to be sorted, the only auxiliary vector is the L(k)-vector. The size of this vector is equal to the number m of classes which is small compared to n, e.g. m typically may be set to m=0.1 n in case of floating point numbers.
Finally,a small number of partially distinguishable elements are sorted locally within their classes either by recursion or by a simple conventional sort algorithm.
Collection
of
demonstrations
related to
to the FlashSort
algorithm

Collection of animated demos related to the FlashSort algorithm

  • For an animated demonstration of performance and runtime of the algorithm under DOS, select
    download FLADEMO1.ZIP (DOS-Version1: a simple demonstration)
  • For an animated demonstration of performance and runtime of the algorithm under DOS, select
    download FLADEMO2.ZIP (DOS-Version2: a more detailed demonstration)
  • Both these files are .zip files. If you do'nt have an unzip facility available, download unzip.exe into the same directory as flademo1.zip. Then type 'unzip flademo1.zip' to unzip and just 'flademo1' to run the demo. Proceed accordingly with flademo2.
    Note: These demos run only, if activated from DOS level, not if activated out of Windows.
    --------------------------------------------------
  • For an animated demonstration of the performance of the algorithm as a Java applet, select
    FlashSort animation Applet
    to be implemented !
  • For an animated presentation of the sort-process and run time performance compared to other sort algorithms, select
    FlashSort runtime Applet
    to be implemented !
FlashSort
introduction 		To go back to FlashSort introduction click here.
Back to
Welcome 		To go back to the Welcome page click here.

This page and each part of it Copyright © 1998-2002 Karl-Dietrich Neubert.
All Rights Reserved
Design by Vladimir Marek.
Last update of the page: April 20, 2003