This problem was very brilliantly solved by @fxshrat and it showed us how to properly use the Sort() function of AmiBroker.
So, as an exercise, today I decided to spend some time reviewing and porting some standard sorting algos to AFL.
Keep in mind that actually there was no need for it since the native Sort() (and also MxSort() , MxSortRows()) are quite fast because they implement the QuickSort algorithm.
Anyway, I did it to see how easy/difficult was to port some standard source code to AFL from other similar programming languages.
In the sample code below, you’ll see the reference to the site that I used to actually “copy & adapt” (mainly from C# examples) the different sorting algos.
I slightly modified them adding the possibility to sort a range instead of a full array.
While I did not test them quite extensively they seem to work as expected.
Obviously, the native Sort() is the fastest one (by a lot!) and the BubbleSort is the worst. The ShellSort is not that bad for small tasks.
If you test them with a symbol with a lot of quotes, keep in mind that it could take some seconds (minutes) to complete since some of these algos are quite slow.
As said, not very useful, but here it is:
//*****************************************************************
// Sorting Algorithms vs AmiBroker native Sort (QuickSort)
//
// Porting to AFL some common sorting algorithms
// Original C# code found at:
// https://rosettacode.org/wiki/Category:Sorting_Algorithms
// Added the feature to sort a range instead of the full array
//
// All the sorting algos are implemented as procedures that sort
// a "passed by reference" array in place (no return value)
// Each sorting procedure requires 3 parameters:
// SortXxxxxxxx(list, b, e)
// list: is an array and MUST be passed by reference (sort in place)
// b: is the index of the start of range to sort (b for beginning)
// e: is the index of the end of range to sort (e for ending)
//
// To be used in Analysis - Explore
// Apply to: "Current" - Range From/To Dates or All quotes
//
// Performances reported via _TRACEF to the internal/external log
//*****************************************************************
Version (6.26); // Uses passing by reference arrays
//// https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort
procedure BubbleSort(list, b, e) // Pass the array param by REFERENCE
{
// Because of its abysmal O(n2) performance, it is not used often for large
// (or even medium-sized) datasets.
itemCount = (e-b) + 1;
do
{
swapped = false;
itemCount--;
for (i = 0; i < itemCount; i++)
{
j = i+b; // offset from begin of interval
if (list[j] > list[j + 1]) {
temp = list[j + 1];
list[j + 1] = list[j];
list[j] = temp;
swapped = true;
}
}
} while (swapped);
}
/// https://rosettacode.org/wiki/Sorting_algorithms/Cocktail_sort
procedure CocktailSort(list, b, e) // Pass the array param by REFERENCE - a.k.a SharerSort
{
// The cocktail shaker sort is a small improvement on the Bubble Sort.
// Sometime, performance is slightly better.
itemCount = (e-b) + 1;
do
{
swapped = false;
for (i = 0; i <= itemCount - 2; i++)
{
j = i+b;
if (list[j] > list[j + 1])
{
// test whether the two elements are in the wrong order
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
swapped = true;
}
}
if (!swapped)
{
// We can exit the outer loop here if no swaps occurred.
break;
}
swapped = false;
for (i = itemCount - 2; i >= 0; i--)
{
j = i+b;
if (list[j] > list[j + 1])
{
temp = list[j];
list[j] = list[j + 1];
list[j + 1] = temp;
swapped = true;
}
}
// If no elements have been swapped, then the list is sorted
} while (swapped);
}
//// https://rosettacode.org/wiki/Sorting_algorithms/Selection_sort
procedure SelectionSort( list, b, e ) // Pass the array param by REFERENCE
{
// Its asymptotic complexity is O(n2) making it inefficient on large arrays.
itemCount = ( e - b ) + 1;
for( i = 0; i < itemCount; i++ ) {
k = i;
for( j = i + 1; j < itemCount; j++ ) {
if( list[j+b] < list[k+b] ) {
k = j;
}
}
temp = list[i+b];
list[i+b] = list[k+b];
list[k+b] = temp;
}
}
// https://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort
procedure InsertionSort( list, b, e ) // Pass the array param by REFERENCE
{
// An O(n2) sorting algorithm which moves elements one at a time into
// the correct position
for( i = 1+b; i <= e; i++ ) {
temp = list[i];
j = i;
while (( j > b ) AND( list[j - 1] > temp )) {
list[j] = list[j - 1];
j--;
}
list[j] = temp;
}
}
//// https://rosettacode.org/wiki/Sorting_algorithms/Comb_sort
procedure CombSort( list, b, e ) // Pass the array param by REFERENCE
{
// The Comb Sort is a variant of the Bubble Sort. Like the Shell sort,
// it increases the gap used in comparisons and exchanges.
// Frequently has a fairly rapid execution.
itemCount = ( e - b ) + 1;
gap = itemCount;
swaps = true;
while( ( gap > 1 ) OR swapped ) {
gap /= 1.247330950103979;
if( gap < 1 )
gap = 1;
i = 0;
swapped = false;
while( ( i + gap ) < itemCount ) {
igap = i + int(gap);
if( list[i+b] > list[igap+b] ) {
temp = list[i+b];
list[i+b] = list[igap+b];
list[igap+b] = temp;
swapped = true;
}
i++;
}
}
}
//// https://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
procedure ShellSort( list, b, e ) // Pass the param by REFERENCE
{
// Shellsort is a generalization of insertion sort that allows the
// exchange of items that are far apart.
// The running time of Shellsort is heavily dependent on the gap sequence it uses
// Using Shell's original gap sequence makes T(N2) comparisons in the worst case.
n = (e-b) + 1;
gap = 1;
while( gap < int( n / 2 ) ) {
gap = ( gap * 2 ) + 1;
}
while( gap >= 1 ) {
for( i = gap; i < n; i++ ) {
k = i - gap;
j = i;
for( j = i; (j >= gap) AND (list[j+b] < list[k+b] ); k -= gap ) {
temp = list[j+b];
list[j+b] = list[k+b];
list[k+b] = temp;
j = k;
}
}
gap = int( gap / 2 );
}
}
//// https://rosettacode.org/wiki/Sorting_algorithms/Shell_sort
//// https://oeis.org/search?q=shell+sort
procedure ShellSortCiura( list, b, e ) // Pass the param by REFERENCE
{
// ShellSort variation using predefined gaps sequence
n = (e-b) + 1;
// Using Marcin Ciura's gap sequence (2001) - https://oeis.org/A102549
gaps = MxFromString("{{1750, 701, 301, 132, 57, 23, 10, 4, 1 }}");
for (g = 0; g < MxGetSize(gaps, 1); g++) {
gap = gaps[0][g];
for( i = gap; i < n; i++ ) {
k = i - gap;
j = i;
for( j = i; (j >= gap) AND (list[j+b] < list[k+b] ); k -= gap ) {
temp = list[j+b];
list[j+b] = list[k+b];
list[k+b] = temp;
j = k;
}
}
}
}
// Sample code to test the sorting algos performance.
// Run in exploration mode: Apply to: "Current" - Range From/To Dates or All quotes
array = V / 1000; // Any array of values
if( Status( "Action" ) == actionExplore )
{
Filter = 1;
SetOption( "NoDefaultColumns", True );
AddTextColumn( Name(), "Symbol" );
AddColumn( DateTime(), "Date", formatDateTime );
AddColumn( array , "Array", 3.2);
bi = Barindex();
fbr = LastValue( Valuewhen( Status( "firstbarinrange" ), bi ) );
lbr = LastValue( Valuewhen( Status( "lastbarinrange" ), bi ) );
bsa = array; // BubbleSort
cka = array; // CocktailSort
sea = array; // SelectionSort
isa = array; // InsertionSort
csa = array; // CombSort
ssa = array; // ShellSort
sca = array; // ShellSort (Ciura)
qsa = array; // QuickSort (AmiBroker internal - FASTEST)
GetPerformanceCounter(True); // reset counter to zero
BubbleSort( &bsa, fbr, lbr );
bsa_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True); // reset counter to zero
CocktailSort( &cka, fbr, lbr );
cka_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True);
SelectionSort( &sea, fbr, lbr );
sea_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True);
InsertionSort( &isa, fbr, lbr );
isa_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True);
CombSort( &csa, fbr, lbr );
csa_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True);
ShellSort( &ssa, fbr, lbr );
ssa_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True);
ShellSortCiura( &sca, fbr, lbr );
sca_elapsed =GetPerformanceCounter();
GetPerformanceCounter(True);
qsa = Sort(qsa, fbr, lbr ); // AmiBroker sort is a function returning the sorted array
qsa_elapsed =GetPerformanceCounter();
AddColumn( bsa, "Bubble Sort" );
AddColumn( cka, "Cocktail Sort" );
AddColumn( sea, "Selection Sort" );
AddColumn( isa, "Insertion Sort" );
AddColumn( csa, "Comb Sort" );
AddColumn( ssa, "Shell Sort" );
AddColumn( sca, "Sh. Sort Ciura" );
AddColumn( qsa, "QuickSort (AB)" );
_TRACEF("----------------------------------------------------------------");
_TRACEF("Sorting arrays - Ticker: " + Name());
_TRACEF("BarCount %6.0f - FvB %6.0f - LvB %6.0f - Bars in range %6.0f",
BarCount, fbr, lbr, (lbr-fbr)+1);
_TRACEF("----------------------------------------------------------------");
_TRACEF("BubbleSort : %7.3f ms", bsa_elapsed);
_TRACEF("CocktailSort : %7.3f ms", cka_elapsed);
_TRACEF("SelectionSort : %7.3f ms", sea_elapsed);
_TRACEF("InsertionSort : %7.3f ms", isa_elapsed);
_TRACEF("CombSort : %7.3f ms", csa_elapsed);
_TRACEF("ShellSort : %7.3f ms", ssa_elapsed);
_TRACEF("Sh.Sort (Ciura) : %7.3f ms", sca_elapsed);
_TRACEF("QuickSort (AB) : %7.3f ms", qsa_elapsed); // A LOT FASTER!!!
_TRACEF("----------------------------- DONE -----------------------------");
}
…. Especially Tomasz