15,042,336 members
Articles / General Programming / Algorithms
Article
Posted 11 Mar 2012

20.3K views
11 bookmarked

# Simo Sort: A Sorting Algorithm for Elements with Low Variance

Rate me:
4.63/5 (8 votes)
12 Mar 2012CPOL2 min read
Simo Sort a New Sorting algorithm C++ Binary Value Numbers Sort Elements with Low Variance

## Introduction

I was writing an article on determining the fastest algorithm for sorting and while I was writing I got influenced by the many sorting algorithms and I devised an algorithm for sorting. It's called Simo because that's the name of someone who is very special to my heart :)

## How it works

It is a recursive sorting algorithm that repeats the following steps:

1. Get the average value of numbers in the array
2. Divide the array into two arrays (array 1 and array 2) and the average value will be chosen as the pivot.
3. Any value smaller than the pivot will be in first array and any value larger than the pivot will be in the second array.
4. Repeat the same algorithm on array 1 and array 2 till you reach the ending condition

For optimization purposes:

1. The ending condition is not a normal ending for a recursive function but it uses some conditions that I devised through try and error, these conditions raise the performance alot.
2. If the array size is less than 15 an Insertion Sort is used to decrease overhead, 15 has been found empirically as the optimal cutoff value in 1996.

## The algorithm

This is how the algorithm works:

low is the index of the first element and high is the index of last element.

C++
```template <class T>
void simoSort(T a[],int low,int high)
{
//Optimization Condition
if(high-low>15)
{
double average=0;
int n = (high - low + 1);

for (int i = low; i <= high; i++)
average+=a[i];

average/=n;
int k=low;

for(int i = low;i<=high; i++)
if(a[i]<average)
{
int tempValue = a[i];
a[i] = a[k];
a[k] = tempValue;

k++;
}

//Optimized Stop Condition
if(low<k-1 && k-1!=high)
simoSort(a,low,k-1);

if(high>k && low!=k)
simoSort(a,k,high);
}
else
{
//Insertion Sort to reduce Overhead when recursion is not deep enough
for (int i = low + 1; i <= high; i++) {
int value = a[i];
int j;
for (j = i - 1; j >= low && a[j] > value; j--) {
a[j + 1] = a[j];
}
a[j + 1] = value;
}
}
}```

## Example

"Example 1" shows how the algorithm works in a normal case.

"Example 2" shows how the algorithm works in its best case scenario where elements of the array have little variance between them. In the case where there where only 2 numbers "1" and "0" the algorithm had a complexity of O(n)

Note: When the algorithm stops in the shown figures it means a leaf has reached an ending condition.

## Complexity

The Search is Stable and has an upper bound space Complexity of O(1)

After doing the time complexity analysis calculations.

• The Average and Worst case scenarios are of (5/6)*nlogn complexity which maps to O(nlogn)
• The Best Case is O(n) as shown in Example 2.

If any one can prove these values wrong please tell me and I will modify them, thanks.

The algorithm is currently faster than quick sort and bucket sort when the variance of the elements is low(not more than 5 different elements) according to the I benchmark that I made, and I'm currently writing an article that will compare all sorting algorithms including this one.

## Limitations

The current version of the algorithm only works on integers. it does not work on chars or double values.

## History

#### 1.0 (10 March 2012)

• Initial release.

I hope that this article would at least slightly help those who are interested in this issue. Feel free to tell me any comments on the algorithm :)

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Software Developer (Senior) Free Lancer Egypt
BSc Computer Engineering, Cairo University, Egypt.

I love teaching and learning and I'm constantly changing
Feel free to discuss anything with me.

A Freelance UX designer, Code is my tool brush, I design for experience !

My Website

## Comments and Discussions

 First Prev Next
 Iterators instead of T[] Werner Salomon17-Mar-12 5:32 Werner Salomon 17-Mar-12 5:32
 What do You think about using iterators instead of an C-array. I rewrite simoSort in this way, and think there is no disadvantage. Copy Code ```namespace detail { // -- putting the calculation of the pivot element in an extra function // gives us the possibility for later improvement & flexibility template< typename V, typename Ri > V pivot( Ri first, Ri last, V* ) { return std::accumulate( first, last, V() )/(last - first); } } template< typename Ri > // Ri means random access iterator void simoSort( Ri first, Ri last ) { typedef typename std::iterator_traits< Ri >::value_type value_type; typename std::iterator_traits< Ri >::difference_type const n = last - first; if( n > 16 ) { const value_type pivot = detail::pivot( first, last, (value_type*)(0) ); Ri k = first; for( Ri i = first; i != last; ++i ) { if( *i < pivot ) std::iter_swap( i, k++ ); } simoSort( first, k ); simoSort( k, last ); } else if( n > 1 ) { for( Ri i = first; ++i != last; ) { const value_type value = *i; Ri j = i; for( Ri k = j; k != first && value < *--k; j = k ) *j = *k; *j = value; } } } ``` The advantage is the higher flexibility. Thanks for writing this article Werner
 Impact of calculating the mean mounte@sandvik11-Mar-12 22:40 mounte@sandvik 11-Mar-12 22:40
 Re: Impact of calculating the mean Mahmoud Hesham El-Magdoub11-Mar-12 22:53 Mahmoud Hesham El-Magdoub 11-Mar-12 22:53
 Difference to Quicksort? nv311-Mar-12 12:38 nv3 11-Mar-12 12:38
 Re: Difference to Quicksort? Mahmoud Hesham El-Magdoub11-Mar-12 22:30 Mahmoud Hesham El-Magdoub 11-Mar-12 22:30
 Re: Difference to Quicksort? melimani12-Mar-12 0:37 melimani 12-Mar-12 0:37
 Re: Difference to Quicksort? Mahmoud Hesham El-Magdoub12-Mar-12 0:53 Mahmoud Hesham El-Magdoub 12-Mar-12 0:53
 Re: Difference to Quicksort? melimani12-Mar-12 2:02 melimani 12-Mar-12 2:02
 Re: Difference to Quicksort? Mahmoud Hesham El-Magdoub12-Mar-12 2:09 Mahmoud Hesham El-Magdoub 12-Mar-12 2:09
 Re: Difference to Quicksort? nv312-Mar-12 8:48 nv3 12-Mar-12 8:48
 Re: Difference to Quicksort? Mahmoud Hesham El-Magdoub12-Mar-12 8:57 Mahmoud Hesham El-Magdoub 12-Mar-12 8:57
 Re: Difference to Quicksort? Member 851795515-Mar-12 0:10 Member 8517955 15-Mar-12 0:10
 Re: Difference to Quicksort? Mahmoud Hesham El-Magdoub15-Mar-12 10:27 Mahmoud Hesham El-Magdoub 15-Mar-12 10:27
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Sep-21 4:15 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Praise    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.