Fast-Radix-Sort

KO | EN

gitlite — search

#javascript #python #hacktoberfest #go #golang #android #docker #macos #windows #awesome #cli #kubernetes #pytorch #ios

Fast-Radix-Sort

(★ 20)

An optimized implementation of the Radix LSD sorting algorithm for integers, written in C.

Fast-Radix-Sort Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Fast-Radix-Sort

An optimized implementation of the Radix LSD sorting algorithm for integers, written in C.

🚨 This is an older implementation 🚨

Please check out [Multitype-Radix-Sort](https://github.com/AwardOfSky/Multitype-Radix-Sort) for an improved, more general implementation without compromising speed.

Also, check out [CUDA-Fast-Sort](https://github.com/AwardOfSky/CUDA-Fast-Sort) for a thoroughly optimized GPU implementation in CUDA!

<h2>Algorithm:</h2>
Radix Sort is a non-comparative sorting algorithm able to sort a list of N integers in O(kn) time complexity.
 The presented program showcases an implementation of said algorithm written in ANSI C and optimized for speed.
The function sorts 32-bit integers (signed or unsigned), one byte at a time (a bit like the American Flag sorting,
 but starting with the Least Significant Digit/Byte).
Radix sort is a stable sorting, meaning every two numbers with the same value appear in the same order in the
 sorted output as they appear in the input.
This implementation follows an out-of-place approach, meaning it uses an helper array in order to sort
 the original array.
The program supports all main C compilers (GCC, Clang, MCVS, ...) and architectures.
For more information about the algorithm itself, check the
<a target="_blank" href="https://en.wikipedia.org/wiki/Radix_sort">Wikipedia Page</a>.

<h2>Optimizations:</h2>

The sorting function was made without the help of compiler optimizations in mind.
 Therefore, it uses some microtimizations like macros and registers to speed some things up.
 Be mindful that compilers like GCC don't provide full-fledged optimizations unless told so.
 The ideia is to just include the function in your program and get the performance right out
of the box.

<ul>
 
 <li> Taking advantage of cache locaity by sorting bytes in different orders when the input
 array is bif enought to do so. This means applying the "normal" radix algorithm in subarrays.</li>
 
 <li>Use of powers of 2 for the expoents and bucket size in order to use
 shift and bitwise operations (expoent = 8 in order to sort 1 byet per iteration).
 This works a lot like the American Flag algorithm used to sort strings.</li>
 
 <li>Small preliminary check of the initial unsorted array to determine
 number of bytes to sort. Special useful in randomly shuffled arrays.</li>
 
 <li>The indexes of the buckets express the amount of elements of that respective
 index in the original array. There is also a array of pointers so that
 each pointer has the adress in the helper array where the given offset
 should start.</li>
 
 <li>As there are only 4 iterations at max (for a 32 bit integer at least),
 instead of copying the whole helper array to the original at the end of 
 each iteration, the algorithm switches the purpose of these two arrays
 in order to reduce copying overhead (eventually correcting this at the
 end if it stops in a even number of bytes).</li>
 
 <li>Neglecting the shift operation when sorting the first byte (equals >> 0).</li>
 
 <li>Filling the array of buckets with a blocksize of 4 elements at a time.</li>
 
 <li>The algorithms is the same even if the original array contains integers
 of different signs. The only thing we have to do at the end is starting
 from the negative numbers instead (in case of different signs). This task
 has a relatively small overhead as it is done with the help of memcpy and
 memmove.This only applies if we're not sorting all the bytes (see last point)!</li>
 
 <li>If, when sorting a certain byte, one of the buckets has all the elements, it means
 sorting that byte won't do anything at all in the final result, so skip ahead this byte.</li>
 
 <li>If we have to sort all bytes either way, we can deal with negative numbers by 
 splitting the for loop that assign the pointers to the helper array in half.
 This works because the last bit is the sign bit, thus in the last byte the negative
 numbers will correspond to the buckets with an index higher that 127.
 Although a small improvement this allows for sorting negative and positive integers
 in the same time complexity (if sorting all bytes), bringing down the time for the worst
 case scenario in a random shuffled array.</li>
</ul>

Mind that as the algorithm works byte per byte, having 1 bit or 8 bits maximun is the same timewise.

<h2>Use and compilation:</h2>
Provided you are in a Linux based OS, enter the following commands in your terminal:
Compile with: <code>gcc -Wall radix.c -o radix</code>
 Execute with: <code>./radix</code>

<h4>The code looks ugly!</h4>
I couldn't agree more...
 This is mainly because of the excessive use of microptimizations, macros and other
 small improvements that damages the code readability.
 Keep in mind the main objective is performance.

<h4>Further improvement:</h4>
This algorithm still has space for improving and if you want to optimize it further
 I can provide a cleaner version for clarity.
 If you are kind enough, let me know what optimizations you were able to do.

Fast-Radix-Sort

Fast-Radix-Sort Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Fast-Radix-Sort

Fast-Radix-Sort Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README