Introsort (ordinamento introspettivo) con i puntatori di funzione - libreria per MetaTrader 5

Ordinamento introspettivo

Si tratta di una versione riveduta della libreria Introsort originale; orala funzione Introsort() accetta un puntatore opzionale a una funzione di confronto personalizzata.

Intro o Introspective sort è un algoritmo di ordinamento ibrido che fornisce prestazioni veloci. Si tratta di un algoritmo di ordinamento basato su tre fasi. Utilizza l'ordinamento quicksort insieme agli algoritmi heapsort e insertion-sort.

Quick Sort
Il quick sort è un algoritmo divide et impera che funziona selezionando un elemento pivot nell'array, quindi suddivide gli altri elementi in due sottoarray controllando se gli elementi sono maggiori o minori. In media l'ordinamento rapido richiede un tempo O(nlog(n)), con una complessità nel caso peggiore di O(ⁿ²).

Heap Sort
L'Heap sort algoirthm è un metodo di ordinamento basato su confronto binario-heap. Si tratta di un algoritmo di ordinamento instabile con complessità temporale nel caso peggiore e medio di O(nlog(n)) e complessità temporale nel caso migliore di O(n).

Insertion Sort
L'algoritmo Insertion sort è un metodo di ordinamento semplice che costruisce l'array finale ordinato un elemento alla volta. La sua complessità temporale per il caso peggiore e medio è O(ⁿ²) e per il caso migliore è O(n).

L'algoritmo Introsort combina le parti migliori di questi tre algoritmi. Inizia con l'ordinamento rapido, passa all'heapsort quando la profondità della ricorsione supera un livello basato sul numero di elementi da ordinare e passa all'ordinamento a inserzione quando il numero di elementi è inferiore a un valore di soglia.

• Se la dimensione della partizione è tale da consentire di superare il limite massimo di profondità, l'Introsort passa all'Heapsort.
• Se la dimensione della partizione è troppo piccola, Quicksort passa a Insertion Sort.
• Se la dimensione della partizione è inferiore al limite e non troppo piccola, allora esegue un semplice quicksort.

Introsort ha un comportamento particolarmente buono in fase di esecuzione. È uno degli algoritmi di ordinamento comparativo più veloci oggi in uso ed è l'implementazione abituale dell'algoritmo std::sort fornito con l'STL del C++, la Microsoft .NET Framework Class Library, la libreria GNU Standard C++ e la libreria LLVM libc++.

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * Ordina l'array di input in-place usando la funzione di confronto less.
 * È possibile specificare una propria funzione di confronto. Se non viene
 * specificata alcuna funzione, viene utilizzato l'ordinamento ascendente.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Introserisce utilizzando un puntatore alla funzione Less() personalizzata.
//| Una funzione Less() personalizzata prende due argomenti e contiene logica |
//| per decidere il loro ordine relativo nell'array ordinato. L'idea è che
//| per fornire flessibilità in modo che Introsort() possa essere usato per qualsiasi |
//| tipo (compresi i tipi definiti dall'utente come oggetti o strutture) |
//| e può essere utilizzato per ottenere qualsiasi ordine desiderato (ascendente, |
//| ordine decrescente o personalizzato dei campi della struttura).
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Funzione di confronto Meno:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- ordinamento per A (asc)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- se uguale su A, ordinare per B (asc)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- se uguale su B, ordinare per C (asc)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- tutte le chiavi sono uguali
   return(false);
  }


// Definire un tipo di puntatore alla funzione Less personalizzata.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Ordinare l'array di strutture utilizzando la funzione Less personalizzata.
Introsort(structArray, (pLess)MyLessFunc);