Introsort (Introspektive Sortierung) mit Funktionszeigern - Bibliothek für den MetaTrader 5

Introspektive Sortierung

Dies ist eine überarbeitete Version der ursprünglichen Introsort-Bibliothek. Jetzt akzeptiertdie Funktion Introsort() einen optionalen Funktionszeiger auf eine benutzerdefinierte Vergleichsfunktion.

Intro oder Introspective Sort ist ein hybrider Sortieralgorithmus, der schnelle Leistung bietet. Es handelt sich um einen vergleichsbasierten Sortieralgorithmus, der auf drei Phasen basiert. Er verwendet die Quicksort-Sortierung zusammen mit den Algorithmen Heapsort und Insertion-Sort.

Quick Sort
Quick Sort ist ein Divide-and-Conquer-Algorithmus, der ein Pivot-Element im Array auswählt und dann die anderen Elemente in zwei Subarrays aufteilt, wobei die Bedingung geprüft wird, ob die Elemente größer oder kleiner sind. Im Durchschnitt benötigt der Quick-Sort-Algorithmus O(nlog(n)) Zeit, wobei die Komplexität im schlimmsten Fall O(ⁿ²) beträgt.

Heap-Sort
Heap-Sort algoirthm ist eine Sortiermethode auf der Basis eines binären Heap-Vergleichs. Es handelt sich um einen instabilen Sortieralgorithmus mit einer Zeitkomplexität im schlimmsten und mittleren Fall von O(nlog(n)) und einer Zeitkomplexität im besten Fall von O(n).

Einfügungssortierung
Der Algorithmus der Einfügungssortierung ist eine einfache Sortiermethode, die das endgültige sortierte Array ein Element nach dem anderen aufbaut. Die Zeitkomplexität für den schlechtesten Fall und den durchschnittlichen Fall beträgt O(ⁿ²) und für den besten Fall O(n).

Der Introsort-Algorithmus kombiniert die guten Eigenschaften dieser drei Algorithmen. Er beginnt mit Quick Sort, wechselt zu Heapsort, wenn die Rekursionstiefe einen Wert überschreitet, der auf der Anzahl der zu sortierenden Elemente basiert, und wechselt zu Insertion Sort, wenn die Anzahl der Elemente unter einem bestimmten Schwellenwert liegt.

• Wenn die Partitionsgröße so groß ist, dass die Möglichkeit besteht, die maximale Tiefe zu überschreiten, schaltet Introsort auf Heapsort um.
• Wenn die Partitionsgröße zu klein ist, schaltet Quicksort auf Insertion Sort um.
• Liegt die Partitionsgröße unter dem Grenzwert und ist nicht zu klein, führt er ein einfaches Quicksort aus.

Introsort hat ein besonders gutes Laufzeitverhalten. Es ist einer der schnellsten Vergleichssortieralgorithmen, die heute verwendet werden, und ist die übliche Implementierung des std::sort-Algorithmus, der in der C++ STL, der Microsoft .NET Framework Class Library, der GNU Standard C++-Bibliothek und der LLVM libc++-Bibliothek enthalten ist.

//+------------------------------------------------------------------+
//| Introsort|
//+------------------------------------------------------------------+
/**
 * Sortiert das Eingabe-Array in-place mit der Vergleichsfunktion less.
 * Sie können Ihre eigene Vergleichsfunktion angeben. Wenn keine Funktion
 * angegeben wird, wird eine aufsteigende Sortierung verwendet.
 */
template<typename T>
void Introsort(T &arr[]);

//+------------------------------------------------------------------+
//| Introsortieren unter Verwendung eines Zeigers auf eine eigene Less()-Funktion.
//| Eine benutzerdefinierte Less()-Funktion benötigt zwei Argumente und enthält Logik.
//| um ihre relative Reihenfolge in der sortierten Anordnung zu bestimmen. Die Idee ist, //|
//| um Flexibilität zu bieten, so dass Introsort() für jede beliebige Funktion verwendet werden kann.
//| Typ (einschließlich benutzerdefinierter Typen wie Objekte oder Strukturen) |
//| und kann verwendet werden, um eine beliebige Sortierreihenfolge zu erhalten (aufsteigend, |
//| absteigende oder benutzerdefinierte Reihenfolge der Strukturfelder). |
//+------------------------------------------------------------------+
template<typename T, typename LessFunc>
void Introsort(T &arr[], LessFunc pfnLess);

Vergleichsfunktion Weniger:

bool MyLessFunc(const MyStruct &x, const MyStruct &y)
  {
//--- sortieren nach A (aufsteigend)
   if(x.A < y.A) return(true);
   if(x.A > y.A) return(false);

//--- bei Gleichheit nach A, Sortierung nach B (aufsteigend)
   if(x.B < y.B) return(true);
   if(x.B > y.B) return(false);

//--- bei Gleichheit mit B, Sortierung nach C (aufsteigend)
   if(x.C < y.C) return(true);
   if(x.C > y.C) return(false);

//--- alle Schlüssel sind gleich
   return(false);
  }


// Definieren Sie einen Zeigertyp für eine benutzerdefinierte Less-Funktion.
typedef bool (*pLess)(const MyStruct &x, const MyStruct &y);


// Array von Strukturen mit benutzerdefinierter Less-Funktion sortieren.
Introsort(structArray, (pLess)MyLessFunc);