Really fast sorting algorithm for small arrays.
Take a look at the other sorting algorithms like EcoSelection sort inside the code to better understand this one.
:)
The idea is to open the mind about the options inside loops.
Why use only 1 value of the array at a time? Why not compare more than one?
I hope that this implementation shows that it is worth to think about it.
We all know that O(n^2) sorting algorithms like insertion or selection sort are not the best options for big arrays.
The new algotrithm as implemented is faster than insertion sort.
The Ranking sort uses the core idea of selection sort but uses the min e max each iteration, going from 0 - mid and final - mid inside the same loop. When they meet, stop the iteration and the unsorted array is sorted.
EcoShellSort (I am still working on this one) is a modified implementation of shellSort using the size of the array as a parameter to set the gap (I am still testing to check when and how to make it better). As it uses the same principle of insertion sort to sort the small chunks, I am tweaking the size of the chunk to improve speedy. It seems to be working.
:)
The above code (sorts.c) shows the difference in time - microseconds - (I know that we must NOT use time to measure, but as they will ALL run with the same array and in the same machine - your machine - I think we can try)
Take a look at some speed benchmarks
Array size = 50
BubleSort - Time : 15 us
SelectionSort - Time : 9 us
InsertionSort - Time : 7 us
ShellSort - Time : 6 us
MergeSort - Time : 123 us
// bellow are mine
EcoSelectionSort - Time : 7 us
EcoTurboSelectionSort - Time : 8 us
EcoPowerSelectionSort - Time : 9 us
RankingSort - Time : 6 us
EcoShellSort - Time : 5 us
Array size = 100
BubleSort - Time : 44 us
SelectionSort - Time : 28 us
InsertionSort - Time : 19 us
ShellSort - Time : 14 us
MergeSort - Time : 150 us
// bellow are mine
EcoSelectionSort - Time : 23 us
EcoTurboSelectionSort - Time : 21 us
EcoPowerSelectionSort - Time : 23 us
RankingSort - Time : 15 us
EcoShellSort - Time : 12 us
Array size = 1000
BubleSort - Time : 2839 us
SelectionSort - Time : 1715 us
InsertionSort - Time : 979 us
ShellSort - Time : 156 us
MergeSort - Time : 304 us
// bellow are mine
EcoSelectionSort - Time : 999 us
EcoTurboSelectionSort - Time : 845 us
EcoPowerSelectionSort - Time : 799 us
RankingSort - Time : 642 us
EcoShellSort - Time : 137 us
Array size = 10000
BubleSort - Time : 294167 us
SelectionSort - Time : 136732 us
InsertionSort - Time : 90682 us
ShellSort - Time : 1881 us
MergeSort - Time : 2243 us
// bellow are mine
EcoSelectionSort - Time : 90063 us
EcoTurboSelectionSort - Time : 65995 us
EcoPowerSelectionSort - Time : 68592 us
RankingSort - Time : 59071 us
EcoShellSort - Time : 1832 us
Array size = 100000
BubleSort - Time : 33071597 us
SelectionSort - Time : 14116509 us
InsertionSort - Time : 8419908 us
ShellSort - Time : 30218 us
MergeSort - Time : 28247 us
// bellow are mine
EcoSelectionSort - Time : 8386055 us
EcoTurboSelectionSort - Time : 6415782 us
EcoPowerSelectionSort - Time : 6295024 us
RankingSort - Time : 5709083 us
EcoShellSort - Time : 26694 us
If you use clang to compile just:
clang -o sorts sorts.c
Or use your prefered compiler.