Several unique sort
From Wikipedia, the free encyclopedia.
- Warning: This article describes a new algorithm – see Wikipedia:No original research.
Several Unique is a sorting algorithm that works by pushing elements to their final place. It was found by the Critticall programming tool, which uses evolutionary programming to optimise existing algorithms. Several Unique operates fastest when the input arrays have a small number of unique elements among a larger number of them.
Several Unique runs in time less than Θ(kn), proportional to the number of unique elements and the total number of elements – which is equivalent to Θ(n2) in the worst case. It makes as many passes as there are unique keys in the list and every next pass is shorter than the previous one.
Conceptually, Several Unique works as an optimised Bubble sort. Upon each pass it performs the following tasks.
- Track the first occurrence of the highest value found so far.
- If a lower value is encountered, swap it with the higher one.
- After a swap, assume that the successor of the first element is the first occurrence of the highest value found so far.
This last task is important, because it allows the algorithm to rapidly move the first element in a sequence of equal values, placing it at the end of that sequence when a lower value follows.
At the end of each pass, the highest value encountered has all of its elements moved to the end of the list. This allows the algorithm to ignore the highest values on each subsequent pass by shortening the length of each scan.
Example code
Here is an example implementation in the C programming language, which works for lists of signed integers only.
#include <limits.h>
/* ... */
int Element[ NUM_ELEMENTS ]; /* Array of signed integers to be sorted. */
int EndIndex; /* Index where current scan should end. */
int Position; /* Current scan position. */
int HighValue; /* Highest value found in current scan. */
int SwapIndex; /* First index of highest value found. */
int NewValue; /* Value of current element. */
/* Scan all elements on the first pass. */
EndIndex = NUM_ELEMENTS - 1;
/* For each distinct element value... */
do
{
/* Start with no highest value (use lowest possible value). */
HighValue = INT_MIN;
/* For each element, scanning from start to end... */
Position = -1;
while ( Position < EndIndex )
{
/* Advance to the next element. */
Position++;
/* Get the current value. */
NewValue = Element[ Position ];
/* If the current value is lower, swap it with highest so far.
* Rather than swapping the lower value again, use the next
* position which is the first occurrence of the highest value. */
if ( NewValue < HighValue )
{
Element[ SwapIndex ] = NewValue;
SwapIndex++;
Element[ Position ] = HighValue;
}
/* If the current value is higher, remember its value/position. */
if ( NewValue > HighValue )
{
SwapIndex = Position;
HighValue = Element[ Position ];
}
}
/* Finish the next scan prior to the highest value found in this pass,
* as its elements are now in their final positions. */
EndIndex = SwapIndex - 1;
}
while ( Position >= SwapIndex );
Note: This example has been rewritten but is functionally equivalent to the original produced by the Critticall tool.
Relationships to other sorting algorithms
Using Several Unique on a random array will result in poor performance, as with a Bubble sort. When the number of different elements is low, Several Unique can outperform general comparison-based sorts such as Quicksort. However a Radix sort is more general-purpose, and in practice would be preferred when its extra memory requirements are not an issue.
External link
- Critticall home page (http://www.critticall.com/)