Von den Grundlagen zur Mittelstufe: Bubblesort anpassen und optimieren

Einleitung

Im vorherigen Artikel „Von den Grundlagen zur Mittelstufe: Orientierung in der Sandbox“ haben wir uns damit befasst, wie man sich in einer der von MetaTrader 5 unterstützten Sandboxen zurechtfindet. Es wurde außerdem gezeigt, dass wir dies auf zwei völlig unterschiedliche Weisen und zu unterschiedlichen Zwecken tun können. Eine Möglichkeit zur Navigation bestand darin, ein im Betriebssystem selbst integriertes Dialogfeld zu verwenden, was diese Methode zur praktischsten, einfachsten und bequemsten Art machte, sich innerhalb der Sandbox zu bewegen.

Es wurde jedoch auch eine zweite Navigationsmethode vorgeführt. Diese Methode wird direkt im Code der zu entwickelnden Anwendung implementiert, was sie etwas komplexer macht. Tatsache ist, dass der Zweck des Navigationssystems in diesem Fall nicht in einer einfachen, schnellen Interaktion mit dem Benutzer besteht, sondern in einer ganz anderen Aufgabe: festzustellen, welche Dateitypen dort vorhanden sind und wie die Verzeichnisstruktur innerhalb der Sandbox aufgebaut ist.

Dieser zweite Ansatz – oder besser gesagt: diese Art, sich in der Sandbox zurechtzufinden – eröffnet uns bestimmte Möglichkeiten, die wir gleich ein wenig erkunden können. Das liegt daran, dass zwar bei Anwendungstests alles perfekt zu laufen scheint, in der Praxis aber oft Probleme auftreten können. Dateien und Verzeichnisse können in einer völlig chaotischen Reihenfolge angezeigt werden, und noch wahrscheinlicher ist es, dass ihre Namen nicht sortiert sind.

Dies ist in der Regel der häufigste Fall: Wir möchten beispielsweise einen Filter erstellen, der auf dem Erstellungs- oder Änderungsdatum einer Datei oder eines Verzeichnisses basiert. Dies würde zu Suchzwecken erfolgen, um Dateien und Verzeichnisse in einer bestimmten Reihenfolge darzustellen und so das Auffinden der gewünschten Informationen zu erleichtern. In der Implementierung, die wir im vorherigen Artikel betrachtet haben, gibt es keine Möglichkeit, die Ergebnisse sortiert auszugeben, und es fehlt auch jegliche Filterung – so einfach deren Umsetzung auch sein mag.

Um Werte zu sortieren – das heißt, um die Ergebnisse sortiert anzuzeigen –, müssen wir bestimmte Elemente in den Code einfügen. In dieser Situation verlieren viele Anfänger oft völlig den Überblick. Das hängt mit der Art der Aufgabe zusammen, die erledigt werden muss. Die Aufgabe ist an sich nicht schwierig; die Herausforderung besteht darin, dass dasselbe Ziel auf verschiedene Weisen erreicht werden kann. Eine solche Umsetzung in einer bestimmten Programmiersprache kann jedoch etwas verwirrend sein. Oft muss man Code anpassen, der in einer anderen Sprache geschrieben wurde – etwas, wozu viele weniger erfahrene Leute nicht in der Lage sind.

Wir wollen hier jedoch ganz offen sein: Ich werde keine besonderen Anstrengungen unternehmen und auch keine neuen Konzepte einführen. Wir werden uns einfach ansehen, wie man etwas verwendet, das in der Programmierung sehr verbreitet ist, dessen innere Funktionsweise viele Anfänger jedoch gar nicht kennen. Kommen wir also zum nächsten Abschnitt und beginnen wir mit dem interessantesten Teil des Artikels. Denn genau diese Art von Thema macht mir besonders viel Spaß, wenn ich es in der Praxis anwenden muss.

Das Blasenprinzip

Super, sprechen wir zunächst über etwas, das Sie zweifellos schon einmal verwendet haben. Ich meine damit, ein Array mit Zahlen in aufsteigender Reihenfolge zu sortieren. Warum spreche ich das eigentlich an? Der Grund dafür ist ganz einfach, lieber Leser. Die MQL5-Bibliothek mit Funktionen und Prozeduren enthält eine Funktion namens ArraySort. Diese Funktion dient dazu, den Inhalt eines Arrays in aufsteigender Reihenfolge zu sortieren.

Für alle, die diese Funktion noch nicht in Aktion gesehen haben, sehen wir uns anhand des folgenden kleinen Codeausschnitts an, wie sie funktioniert.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     uchar info[10];
07. 
08.     MathSrand(GetTickCount());
09. 
10.     for (uint c = 0; c < info.Size(); c++)
11.         info[c] = (uchar) MathRand();
12. 
13.     Print("Array content before ordering...");
14.     ArrayPrint(info);
15.     
16.     ArraySort(info);
17. 
18.     Print("Array content after sorting...");
19.     ArrayPrint(info);
20. }
21. //+------------------------------------------------------------------+

Code 01

In Code 01 verwenden wir einen Pseudozufallszahlengenerator, um ein kleines Array zu initialisieren. Das Array wird in Zeile 06 deklariert. Die Initialisierung erfolgt durch die Schleife in Zeile 10. Uns interessieren hier jedoch insbesondere die folgenden Zeilen. In diesen Zeilen geben wir das Array zunächst vor dem Sortieren aus und anschließend nach dem Sortieren erneut. Da die Generierung auf Zufallswerten basiert, wird das Ergebnis höchstwahrscheinlich von dem abweichen, was Sie in der folgenden Abbildung sehen.

Abbildung 01

Das liegt daran, dass bei jeder Ausführung eine neue Folge von Werten generiert wird. Es geht aber gerade darum, zu erkennen, dass die Werte in aufsteigender Reihenfolge sortiert wurden. Dies liegt an der Funktion in Zeile 16, die im Code 01 enthalten ist.

Aber was hat das mit unserer Idee zu tun, durch die Sandbox zu navigieren? Nun, lieber Leser, hier fängt es erst richtig an, spannend zu werden. Vielen Anfängern ist hier möglicherweise ein wichtiger Punkt nicht klar. Wenn Daten in einer bestimmten Reihenfolge dargestellt werden – sei es in aufsteigender oder absteigender Reihenfolge –, müssen sie einen Sortiermechanismus durchlaufen. Wenn Sie verstehen, wie diese Mechanismen funktionieren, können Sie eine Vielzahl von Aufgaben bewältigen. Tatsache ist, dass eine Programmiersprache – egal welche – nicht immer über eine integrierte Implementierung verfügt, mit der man absolut jeden Datentyp sortieren kann. Wenn Sie verstehen, wie der Sortiermechanismus funktioniert, können Sie eine Funktion oder Prozedur erstellen, die den Sortiervorgang verallgemeinert. Auf diese Weise können Sie sowohl numerische Daten als auch Text sowie andere Datentypen sortieren.

Wenn Sie beispielsweise versuchen, Code 01 durch den folgenden Code zu ersetzen, werden Sie feststellen, dass dieser nicht kompiliert werden kann.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info[10];
07. 
08.     MathSrand(GetTickCount());
09. 
10.     for (uint c = 0; c < info.Size(); c++)
11.         info[c] = (string) MathRand();
12. 
13.     Print("Array content before ordering...");
14.     ArrayPrint(info);
15.     
16.     ArraySort(info);
17. 
18.     Print("Array content after sorting...");
19.     ArrayPrint(info);
20. }
21. //+------------------------------------------------------------------+

Code 02

Aber warum? Der Grund dafür ist gerade, dass der Compiler keine geeignete Implementierung für Zeichenketten finden kann. Dies liegt nicht am Array selbst, sondern an der Funktion ArraySort, die nicht für die Verarbeitung und Sortierung von Zeichenketten in aufsteigender Reihenfolge konzipiert oder implementiert wurde. „Aber Moment mal. Wollen Sie also sagen, dass wir ein Ergebnis erhalten, wenn wir Zeile 16 aus Code 02 entfernen? Das liegt daran, dass der Compiler eine ausführbare Anwendung generieren kann.“ Ja, das stimmt, lieber Leser. Die Sache ist die: Wenn Sie das tun, sehen Sie beim Ausführen von Code 02 etwas Ähnliches wie in der folgenden Abbildung – natürlich nachdem Sie Zeile 16 aus dem Code entfernt haben.

Abbildung 02

Bitte beachten Sie nun Folgendes. Abbildung 02 zeigt Zeichenketten, die jedoch nicht in aufsteigender Reihenfolge sortiert sind. Der Grund dafür ist, dass wir über keinen Mechanismus verfügen, der diese Sortierung für uns übernehmen würde. Betrachten wir nun folgendes Detail: Wenn Sie eine Methode zum Sortieren derselben Zeichenkettendaten implementieren – selbst wenn diese numerische Werte enthalten –, können Sie denselben Mechanismus nutzen, um Dateien und Verzeichnisse in einer bestimmten Reihenfolge anzuordnen – entweder in aufsteigender Reihenfolge oder in absteigender Reihenfolge. Genau hier ergibt sich die Notwendigkeit, Sortiermechanismen zu untersuchen, die innerhalb einer Programmiersprache implementiert werden können.

Um die Aufgabe zu vereinfachen und für alle verständlich zu machen – denn unser Ziel ist es, so lehrreich wie möglich zu sein und den Stoff auch für Anfänger leicht verständlich darzustellen –, gehen wir Schritt für Schritt vor. Auf diese Weise kann jeder den Ablauf verfolgen und genau nachvollziehen, was wir tun. Es ist viel wichtiger, genau zu verstehen, was hier vor sich geht, als den Code einfach nur zu kopieren, wenn man etwas Ähnliches machen muss. Fangen wir also mit dem folgenden Code an:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     uchar info[10];
07. 
08.     MathSrand(512);
09. 
10.     for (uint c = 0; c < info.Size(); c++)
11.         info[c] = (uchar) MathRand();
12. 
13.     Print("Array content before ordering...");
14.     ArrayPrint(info);
15.     
16.     BubbleSort(info);
17. 
18.     Print("Array content after sorting...");
19.     ArrayPrint(info);
20. }
21. //+------------------------------------------------------------------+
22. template <typename T>
23. void BubbleSort(T &arr[])
24. {
25.     #define macroSWAP(A, B) {                           \
26.                                 temp = arr[j - 1];      \
27.                                 arr[j - 1] = arr[j];    \
28.                                 arr[j] = temp;          \
29.                             }
30. 
31.     uint nElements = arr.Size();
32.     T    temp;
33. 
34.     for (uint i = 1; i < nElements; i++)
35.         for (uint j = nElements - 1; j >= i; j--)
36.             if (typename(T) == "string")
37.             {
38.             }else
39.                 if (arr[j - 1] > arr[j])
40.                     macroSWAP(arr[j - 1], arr[j])
41. 
42.     #undef macroSWAP
43. }
44. //+------------------------------------------------------------------+

Code 03

Code 03 wird unser Ausgangspunkt sein. Bitte beachten Sie, dass wir hier ganz ähnlich vorgehen wie in Code 01. Wir richten den Code hier jedoch so ein, dass Sie dieselben Ergebnisse erhalten wie in den folgenden Abbildungen dargestellt. Das liegt daran, dass wir zwar nach wie vor einen Pseudozufallszahlengenerator zur Initialisierung des Arrays verwenden, diesen jedoch mit einem bestimmten Wert initialisieren. Das können Sie in Zeile 08 sehen.

Und nun, lieber Leser, passen Sie bitte gut auf. Im Gegensatz zu Code 01 und Code 02 enthält Code 03 in Zeile 16 einen Aufruf der von uns implementierten Prozedur. Der Zweck dieser Prozedur besteht darin, die Daten im Array in aufsteigender Reihenfolge zu sortieren. Kommen wir nun zum wichtigen Teil: In den vorherigen Artikeln wurde erläutert, wie man Funktions- und Prozedurvorlagen erstellt. Außerdem erläuterten sie, wie wir diesen Ansatz in der Praxis anwenden können. Nun, hier ist ein Beispiel dafür, wie man das Wissen aus den vorherigen Artikeln anwenden kann. Im Gegensatz zur Bibliotheksfunktion „ArraySort“, die nicht jeden Datentyp sortieren kann, bietet unsere Implementierung diese Möglichkeit.

Um dies zu ermöglichen, verwenden wir die Prüfung in Zeile 36, um festzustellen, ob wir Zeichenketten oder Daten eines anderen Typs sortieren. Bitte beachten Sie: WIR SORTIEREN NOCH KEINE ZEICHENKETTEN. Aber die übrigen Datentypen können wir bereits sortieren. Das lässt sich anhand des in der folgenden Abbildung dargestellten Ergebnisses erkennen.

Abbildung 03

Auch wenn der im Code implementierte Mechanismus nicht der beste verfügbare ist – da er bei großen Arrays sehr langsam ist –, ist er für unsere Demonstration schnell genug und funktioniert einwandfrei. Dies ist in Abbildung 03 zu sehen. „Ist das alles?“ Ja, mein lieber Leser. Kommen wir nun zum interessantesten Teil: der Anpassung des Codes, um das Sortieren von Zeichenketten zu ermöglichen. Bevor wir das tun, machen wir erst einmal einen kleinen Schritt. Dies wird im folgenden Code veranschaulicht:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info[10];
07. 
08.     MathSrand(512);
09. 
10.     for (uint c = 0; c < info.Size(); c++)
11.         info[c] = (string) (uchar) MathRand();
12. 
13.     Print("Array content before ordering...");
14.     ArrayPrint(info);
15.     
16.     BubbleSort(info);
17. 
18.     Print("Array content after sorting...");
19.     ArrayPrint(info);
20. }
21. //+------------------------------------------------------------------+
22. template <typename T>
23. void BubbleSort(T &arr[])
24. {
25.     #define macroSWAP(A, B) {                           \
26.                                 temp = arr[j - 1];      \
27.                                 arr[j - 1] = arr[j];    \
28.                                 arr[j] = temp;          \
29.                             }
30. 
31.     uint nElements = arr.Size();
32.     T    temp;
33. 
34.     for (uint i = 1; i < nElements; i++)
35.         for (uint j = nElements - 1; j >= i; j--)
36.             if (typename(T) == "string")
37.             {
38.             }else
39.                 if (arr[j - 1] > arr[j])
40.                     macroSWAP(arr[j - 1], arr[j])
41. 
42.     #undef macroSWAP
43. }
44. //+------------------------------------------------------------------+

Code 04

Achten Sie bitte genau darauf, was sich zwischen Code 03 und diesem Code 04 geändert hat. Alle vorgenommenen Änderungen sollen sicherstellen, dass in beiden Fällen dieselben Werte verwendet werden. Dennoch sortieren wir noch immer keine Zeichenketten. Das Ergebnis der Ausführung von Code 04 ist jedoch unten dargestellt:

Abbildung 04

Nun, lieber Leser, ich möchte, dass Sie gut aufpassen. Was wir nun tun werden, mag vielen Lesern ziemlich verwirrend erscheinen. Das liegt daran, dass das Sortieren von Zeichenketten – anders als das Sortieren numerischer Werte – kein so einfacher Vorgang ist. Damit die Sortierung korrekt funktioniert, muss dies auf genau festgelegte Weise erfolgen. Wie Sie jedoch in Code 03 und Code 04 sehen können, gibt es zwischen den Zeilen 37 und 38 eine Stelle, an der Sie den Sortiercode selbst implementieren können. Um zu verstehen, wie diese Sortierung durchgeführt werden sollte, müssen Sie zunächst verstehen, welche Ergebnisse wir mit bestimmten Methoden zu ihrer Umsetzung erzielen. Verwenden wir zunächst die Funktion StringCompare, da sie naheliegenderweise die erste Wahl ist. Dazu verwenden wir den folgenden Code.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info[10];
07. 
08.     MathSrand(512);
09. 
10.     for (uint c = 0; c < info.Size(); c++)
11.         info[c] = (string) (uchar) MathRand();
12. 
13.     Print("Array content before ordering...");
14.     ArrayPrint(info);
15.     
16.     BubbleSort(info);
17. 
18.     Print("Array content after sorting...");
19.     ArrayPrint(info);
20. }
21. //+------------------------------------------------------------------+
22. template <typename T>
23. void BubbleSort(T &arr[])
24. {
25.     #define macroSWAP(A, B) {                           \
26.                                 temp = arr[j - 1];      \
27.                                 arr[j - 1] = arr[j];    \
28.                                 arr[j] = temp;          \
29.                             }
30. 
31.     uint nElements = arr.Size();
32.     T    temp;
33. 
34.     for (uint i = 1; i < nElements; i++)
35.         for (uint j = nElements - 1; j >= i; j--)
36.             if (typename(T) == "string")
37.             {
38.                 if (StringCompare(arr[j - 1], arr[j]) > 0)
39.                     macroSWAP(arr[j - 1], arr[j])
40.             }else
41.                 if (arr[j - 1] > arr[j])
42.                     macroSWAP(arr[j - 1], arr[j])
43. 
44.     #undef macroSWAP
45. }
46. //+------------------------------------------------------------------+

Code 05

Wenn wir diesen Code ausführen, erhalten wir das in der folgenden Abbildung gezeigte Ergebnis:

Abbildung 05

„Was soll dieser Wahnsinn? Anscheinend herrscht hier überhaupt keine Ordnung. Allerdings scheinen die Elemente auf den ersten Blick tatsächlich sortiert zu sein. Wenn ich genauer hinschaue, fällt mir auf, dass an dieser Anordnung etwas Seltsames ist.“

Genau, lieber Leser, Sie haben recht. Der Code ist in der Lage, die in einem Array von Zeichenketten enthaltenen Werte zu sortieren. Aber hier gibt es etwas Seltsames, nämlich die Tatsache, dass 37 und 78 kleiner sind als 113. Diese beiden Werte stehen jedoch am Ende der Folge. Warum? Der Grund dafür ist, dass beim Sortieren ausschließlich der Inhalt der Zeichenkette berücksichtigt wird. Daher bleiben alle Werte zwischen 113 und 189 in der richtigen Reihenfolge. Wenn wir jedoch die Anzahl der Zeichen in einer Zeichenkette nicht mehr berücksichtigen, erscheint die Sortierung etwas seltsam, auch wenn sie funktioniert hat.

Interessanterweise werden Sie feststellen, dass die Sortierung tatsächlich wie erwartet funktioniert, wenn Sie Wörter aus einem Wörterbuch verwenden statt Zahlenwerte wie in unserem Beispiel. Für das, was wir tun – oder zu tun versuchen –, war die Sortierung jedoch nicht zu 100 Prozent perfekt. Nun, um dieses Problem zu lösen, müssen wir auch die Anzahl der Zeichen in der Zeichenkette als einen der verwendeten Filter einbeziehen. Somit kann die Bubblesort-Routine das Zeichenketten-Array korrekt sortieren. Die erforderlichen Änderungen sind im folgenden Code dargestellt:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info[10];
07. 
08.     MathSrand(512);
09. 
10.     for (uint c = 0; c < info.Size(); c++)
11.         info[c] = (string) (uchar) MathRand();
12. 
13.     Print("Array content before ordering...");
14.     ArrayPrint(info);
15.     
16.     BubbleSort(info);
17. 
18.     Print("Array content after sorting...");
19.     ArrayPrint(info);
20. }
21. //+------------------------------------------------------------------+
22. template <typename T>
23. void BubbleSort(T &arr[])
24. {
25.     #define macroSWAP(A, B) {                           \
26.                                 temp = arr[j - 1];      \
27.                                 arr[j - 1] = arr[j];    \
28.                                 arr[j] = temp;          \
29.                             }
30. 
31.     uint nElements = arr.Size();
32.     T    temp;
33. 
34.     for (uint i = 1; i < nElements; i++)
35.         for (uint j = nElements - 1; j >= i; j--)
36.             if (typename(T) == "string")
37.             {
38.                 if ((StringLen(arr[j - 1]) > StringLen(arr[j])))
39.                     macroSWAP(arr[j - 1], arr[j])
40.                 if ((StringCompare(arr[j - 1], arr[j]) > 0) && (StringLen(arr[j - 1]) == StringLen(arr[j])))
41.                     macroSWAP(arr[j - 1], arr[j])
42.             }else
43.                 if (arr[j - 1] > arr[j])
44.                     macroSWAP(arr[j - 1], arr[j])
45. 
46.     #undef macroSWAP
47. }
48. //+------------------------------------------------------------------+

Code 06

Wenn wir Code 06 ausführen, erhalten wir das folgende Ergebnis.

Abbildung 06

„Nun, wir haben tatsächlich das Ergebnis erzielt, das wir uns gewünscht und erwartet hatten. In gewisser Weise gibt es einige Dinge, die ich nicht verstehe. Sie haben kürzlich gesagt, dass Code 05 sortieren kann – genauer gesagt, dass er Wörter aus einem Wörterbuch in aufsteigender Reihenfolge sortieren kann. Es ist uns jedoch nicht gelungen, die Zahlenwerte in der richtigen Reihenfolge anzuordnen, wie aus Abbildung 05 deutlich hervorgeht. Durch die Verwendung dieser modifizierten Version von Code 06 konnten wir die Daten jedoch korrekt sortieren. Aber führt diese Änderung in Code 06 nicht dazu, dass der Code Wörter aus einem Wörterbuch nicht mehr korrekt sortieren kann?“ Nun, vielleicht würden viele, die sich als Programmierer bezeichnen, sagen: Natürlich nicht. Der Code wurde geändert, sortiert die Wörter aber weiterhin korrekt.

Wer jedoch Zweifel an dem Code hat, könnte durchaus denken, dass das Programm möglicherweise nicht richtig funktioniert. Wer diesen Zweifeln nachgeht, und die Tragfähigkeit der an der Codestruktur vorgenommenen Änderungen hinterfragen, erkennt letztlich – wenn ich es so sagen darf –, dass es keine Lösung gibt, die jeden möglichen Fall abdeckt. Sie stellen außerdem fest, dass ab einem bestimmten Punkt das Wissen und Verständnis darüber, wie Mechanismen im Inneren funktionieren, zum entscheidenden Faktor werden kann, der ein zufriedenstellendes Ergebnis von einem mittelmäßigen unterscheidet.

Machen wir also einen einfachen Test: Ändern wir Code 06 noch einmal, um zu sehen, ob wir diese Implementierung in jedem Fall verwenden können. Dazu müssen wir lediglich Code 06 wie im folgenden Beispiel gezeigt anpassen:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info[] = {"value", "data", "time", "assembly", "checking" };
07. 
08.     Print("Array content before ordering...");
09.     ArrayPrint(info);
10.     
11.     BubbleSort(info);
12. 
13.     Print("Array content after sorting...");
14.     ArrayPrint(info);
15. }
16. //+------------------------------------------------------------------+
17. template <typename T>
18. void BubbleSort(T &arr[])
19. {
20.     #define macroSWAP(A, B) {                           \
21.                                 temp = arr[j - 1];      \
22.                                 arr[j - 1] = arr[j];    \
23.                                 arr[j] = temp;          \
24.                             }
25. 
26.     uint nElements = arr.Size();
27.     T    temp;
28. 
29.     for (uint i = 1; i < nElements; i++)
30.         for (uint j = nElements - 1; j >= i; j--)
31.             if (typename(T) == "string")
32.             {
33.                 if ((StringLen(arr[j - 1]) > StringLen(arr[j])))
34.                     macroSWAP(arr[j - 1], arr[j])
35.                 if ((StringCompare(arr[j - 1], arr[j]) > 0) && (StringLen(arr[j - 1]) == StringLen(arr[j])))
36.                     macroSWAP(arr[j - 1], arr[j])
37.             }else
38.                 if (arr[j - 1] > arr[j])
39.                     macroSWAP(arr[j - 1], arr[j])
40. 
41.     #undef macroSWAP
42. }
43. //+------------------------------------------------------------------+

Code 07

Jetzt ist das ein bisschen anders. Der einzige wirkliche Unterschied besteht jedoch in den Werten des Zeichenketten-Arrays. In diesem Fall handelt es sich um Wörter, deren Reihenfolge Sie genau kennen, da sie in aufsteigender Reihenfolge angeordnet sind. Zu Ihrer Überraschung erhalten wir jedoch beim Ausführen von Code 07 das in der folgenden Abbildung dargestellte Ergebnis:

Abbildung 07

Zweifellos entspricht das in Abbildung 07 dargestellte Ergebnis nicht der Reihenfolge, in der dieselben Wörter in einem Wörterbuch erscheinen würden. Dennoch wurde die Sortierung hier genau so durchgeführt wie bei der Ausführung von Code 05, dessen Ergebnis in Abbildung 05 dargestellt wurde. Genau aus diesem Grund, lieber Leser, ist es wichtig zu verstehen, dass die von der Anwendung zurückgegebene Antwort nicht immer vollkommen korrekt sein wird, aber auch nicht unbedingt falsch sein muss. Kernpunkt: Welche Art von Ergebnis wurde von der Anwendung erwartet? Je nach konkreter Situation kann dieses Ergebnis für die Erreichung des angestrebten Ziels geeignet sein oder auch nicht. In diesem Fall ist es nicht geeignet. Wir sind in eine Sackgasse geraten.

In diesem Fall liefert die Prozedur, die für diese Aufgabe – hier das Sortieren der Daten in einem Array – erstellt wurde, Ergebnisse, die für uns sinnvoll sein können oder auch nicht. Wir können eine kleine, kaum wahrnehmbare Änderung am Code vornehmen, um diesen Vorgang etwas besser steuerbar zu machen. Der folgende Code enthält diese Änderung.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info_01[10];
07.     string info_02[] = {"value", "data", "time", "assembly", "checking" };
08. //+----------------+
09.     MathSrand(512);
10. 
11.     for (uint c = 0; c < info_01.Size(); c++)
12.         info_01[c] = (string) (uchar) MathRand();
13. //+----------------+
14.     Print("Number array before ordering...");
15.     ArrayPrint(info_01);
16.     
17.     BubbleSort(info_01, true);
18. 
19.     Print("Number array after ordering...");
20.     ArrayPrint(info_01);
21. //+----------------+
22.     Print("Dictionary before ordering...");
23.     ArrayPrint(info_02);
24.     
25.     BubbleSort(info_02);
26. 
27.     Print("Dictionary after sorting...");
28.     ArrayPrint(info_02);
29. }
30. //+------------------------------------------------------------------+
31. template <typename T>
32. void BubbleSort(T &arr[], const bool bUsingLength = false)
33. {
34.     #define macroSWAP(A, B) {                           \
35.                                 temp = arr[j - 1];      \
36.                                 arr[j - 1] = arr[j];    \
37.                                 arr[j] = temp;          \
38.                             }
39. 
40.     uint nElements = arr.Size();
41.     T    temp;
42. 
43.     for (uint i = 1; i < nElements; i++)
44.         for (uint j = nElements - 1; j >= i; j--)
45.             if (typename(T) == "string")
46.             {
47.                 if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j]))))
48.                     macroSWAP(arr[j - 1], arr[j])
49.                 if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength))
50.                     macroSWAP(arr[j - 1], arr[j])
51.             }else
52.                 if (arr[j - 1] > arr[j])
53.                     macroSWAP(arr[j - 1], arr[j])
54. 
55.     #undef macroSWAP
56. }
57. //+------------------------------------------------------------------+

Code 08

Mit Code 08 können Sie die Änderungen überprüfen und sicherstellen, dass sie korrekt sind, sowie das Array von Zeichenketten wie erwartet sortieren. Schauen wir mal, was passiert, wenn wir Code 08 im MetaTrader 5-Terminal ausführen. Daraus ergibt sich folgende Abbildung:

Abbildung 08

Einfach perfekt. Bitte beachten Sie, dass sowohl das Array mit den numerischen Zeichenketten als auch das Array mit den Wörtern aus dem Wörterbuch korrekt sortiert sind. Oder besser gesagt: wie erwartet. Das war zuvor unmöglich. Die entscheidende Frage ist hier, was genau umgesetzt werden musste, damit diese Sortierung das erwartete Ergebnis liefert. Wir mussten lediglich eine zusätzliche Überprüfung in den Block einfügen, in dem wir Zeichenketten verarbeiten.

Auch wenn Sie vielleicht denken, dass die hier vorgestellte Sortiermethode ein ideales Modell ist und in jeder Situation angewendet werden kann, möchte ich Sie, lieber Leser, bitten, diese Annahme noch einmal zu überdenken. Diese Sortiermethode ist zweifellos die schlechteste aller bestehenden Methoden. Obwohl der Code sehr leicht zu verstehen ist, beeinträchtigt er sehr schnell die Gesamtleistung des Systems. Das liegt daran, dass wir für jedes Element des zu sortierenden Arrays die Schleife sehr oft durchlaufen müssen.

Genauer gesagt entspricht die Anzahl der Iterationen, die die Schleife ausführen muss, im schlimmsten Fall der Anzahl der Elemente zum Quadrat. Mit anderen Worten: Um fünf Elemente zu sortieren, müssen wir die Schleife 25 Mal durchlaufen. Bei zehn Elementen – das sind nur doppelt so viele wie im ersten Fall – steigt die Anzahl der Schleifeniterationen auf 100. Bitte beachten Sie, dass die Anzahl der Durchläufe der Schleife sehr schnell zunimmt, sobald dem Array neue Elemente hinzugefügt werden.

Aus diesem Grund bezeichnen manche Programmierer die bisher beschriebene Methode oft als „Bubble Hell“. Dies liegt daran, dass jedes neu hinzugefügte Element potenziell die Anzahl der Iterationen erhöhen kann, die für eine erfolgreiche Sortierung erforderlich sind.

Auch wenn die hier vorgestellte rudimentäre und unvollkommene Methodik problematisch ist, gibt es Fälle, in denen wir die Schleife nicht so oft durchlaufen müssen, um ein sortiertes Array als Ausgabe zu erhalten. Das liegt daran, dass möglicherweise schon wenige Iterationen mit Vertauschungen ausreichen, um das Array vollständig zu sortieren. So unglaublich es auch klingen mag: Eine einfache Änderung im Code – die auf den ersten Blick vielleicht wirkungslos erscheint – kann diese „Bubble Hell“ unter bestimmten Umständen in etwas durchaus Akzeptables verwandeln.

Um zu verstehen, wie sich diese Änderung auf den Code auswirkt – und vor allem, wie sie dessen Ausführung beschleunigen kann –, müssen Sie, lieber Leser, verstehen, wie der Sortiervorgang in der bisher beschriebenen Implementierung funktioniert.

Sobald Sie das verstanden haben, können wir damit fortfahren, den Code zu verbessern. Auf diese Weise wollen wir das Sortiersystem in bestimmten Situationen etwas schneller machen bzw. die CPU-Auslastung und die Verarbeitungszeit verringern.

Nun, damit wir verstehen können, wie sich diese Änderung, die wir gleich vornehmen werden, auf die Codeausführung auswirkt, müssen wir zunächst eine Möglichkeit schaffen, um zu sehen, was im Sortieralgorithmus vor sich geht. Dazu ersetzen wir Code 08 durch den folgenden Code:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info_01[10];
07.     string info_02[] = {"value", "data", "time", "assembly", "checking" };
08. //+----------------+
09.     MathSrand(512);
10. 
11.     for (uint c = 0; c < info_01.Size(); c++)
12.         info_01[c] = (string) (uchar) MathRand();
13. //+----------------+
14.     Print("+----------------+\nNumber array before ordering...");
15.     ArrayPrint(info_01);
16.     
17.     BubbleSort(info_01, true);
18. 
19.     Print("Number array after ordering...");
20.     ArrayPrint(info_01);
21. //+----------------+
22.     Print("+----------------+\nDictionary before ordering...");
23.     ArrayPrint(info_02);
24.     
25.     BubbleSort(info_02);
26. 
27.     Print("Dictionary after sorting...");
28.     ArrayPrint(info_02);
29. }
30. //+------------------------------------------------------------------+
31. template <typename T>
32. void BubbleSort(T &arr[], const bool bUsingLength = false)
33. {
34.     #define macroSWAP(A, B) {                           \
35.                                 temp = arr[j - 1];      \
36.                                 arr[j - 1] = arr[j];    \
37.                                 arr[j] = temp;          \
38.                             }
39. 
40.     uint nElements = arr.Size();
41.     T    temp;
42.     uint count = 0;    
43. 
44.     for (uint i = 1; i < nElements; i++)
45.     {
46.         for (uint j = nElements - 1; j >= i; j--, count++)
47.             if (typename(T) == "string")
48.             {
49.                 if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j]))))
50.                     macroSWAP(arr[j - 1], arr[j])
51.                 if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength))
52.                     macroSWAP(arr[j - 1], arr[j])
53.             }else
54.                 if (arr[j - 1] > arr[j])
55.                     macroSWAP(arr[j - 1], arr[j])
56.     }
57. 
58.     Print("Number of interactions: ", count);
59. 
60.     #undef macroSWAP
61. }
62. //+------------------------------------------------------------------+

Code 09

Bitte beachten Sie, dass wir in Code 09 lediglich eine Möglichkeit hinzugefügt haben, die Anzahl der Iterationen innerhalb der Sortierroutine zu zählen. Dies geschah, indem Zeile 42 hinzugefügt und anschließend in Zeile 46 die Anzahl der Iterationen gezählt wurde. Schließlich geben wir in Zeile 58 das Ergebnis aus, um festzustellen, wie viele Iterationen stattgefunden haben. Bitte beachten Sie Folgendes: Diese Implementierung führt nicht nElements² Operationen aus. Das liegt daran, dass die Schleife in Zeile 46 mit jeder Iteration der Schleife in Zeile 44 eine Iteration weniger ausführt. Es ist sehr wichtig, dass Sie dies verstehen, damit Sie sich nicht von dem Wert verwirren lassen, der als Anzahl der durchgeführten Iterationen angezeigt wird.

Super, wenn wir diesen Code also ausführen, erhalten wir das in der folgenden Abbildung gezeigte Ergebnis:

Abbildung 09

Was uns hier und jetzt wirklich interessiert, sind die in Abbildung 09 hervorgehobenen Bereiche. Beachten Sie, dass eine bestimmte Anzahl von Iterationen durchgeführt wird. Nun frage ich: Ist das ein gutes oder ein schlechtes Ergebnis? Und die Antwort auf diese Frage lautet: Das hängt ganz von den Umständen ab. Hier gibt es eine Besonderheit, und genau darauf möchte ich hinaus. Beachten Sie, dass die zu sortierenden Werte auf den ersten Blick stark ungeordnet erscheinen. Aber was wäre, wenn sie der gewünschten Sortierreihenfolge bereits näherkämen? Würde dies die Anzahl der Iterationen im Vergleich zum vorherigen Ergebnis verringern? Na gut, probieren wir es einfach mal aus und schauen, was passiert. Dazu verwenden wir den folgenden Code:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info_01[] = {"37", "78", "0", "145", "113", "139", "148", "247", "174", "189"};
07.     string info_02[] = {"value", "data", "time", "assembly", "checking" };
08. //+----------------+
09.     Print("+----------------+\nNumber array before ordering...");
10.     ArrayPrint(info_01);
11.     
12.     BubbleSort(info_01, true);
13. 
14.     Print("Number array after ordering...");
15.     ArrayPrint(info_01);
16. //+----------------+
17.     Print("+----------------+\nDictionary before ordering...");
18.     ArrayPrint(info_02);
19.     
20.     BubbleSort(info_02);
21. 
22.     Print("Dictionary after sorting...");
23.     ArrayPrint(info_02);
24. }
25. //+------------------------------------------------------------------+
26. template <typename T>
27. void BubbleSort(T &arr[], const bool bUsingLength = false)
28. {
29.     #define macroSWAP(A, B) {                           \
30.                                 temp = arr[j - 1];      \
31.                                 arr[j - 1] = arr[j];    \
32.                                 arr[j] = temp;          \
33.                             }
34. 
35.     uint nElements = arr.Size();
36.     T    temp;
37.     uint count = 0;    
38. 
39.     for (uint i = 1; i < nElements; i++)
40.     {
41.         // interact = false;
42.         for (uint j = nElements - 1; j >= i; j--, count++)
43.             if (typename(T) == "string")
44.             {
45.                 if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j]))))
46.                     macroSWAP(arr[j - 1], arr[j])
47.                 if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength))
48.                     macroSWAP(arr[j - 1], arr[j])
49.             }else
50.                 if (arr[j - 1] > arr[j])
51.                     macroSWAP(arr[j - 1], arr[j])
52.     }
53. 
54.     Print("Number of interactions: ", count);
55. 
56.     #undef macroSWAP
57. }
58. //+------------------------------------------------------------------+

Code 10

Beachten Sie, dass wir in Zeile 6 von Code 10 dieselben Werte definieren, die in Abbildung 09 dargestellt wurden. Sie sind, wenn ich es so sagen darf, ein bisschen weniger chaotisch. Auf den ersten Blick könnte man meinen, dass dies den Sortiervorgang beschleunigen oder weniger Iterationen erfordern würde, um ihn abzuschließen. Zu Ihrer Überraschung wird jedoch bei der Ausführung von Code 10 das in der folgenden Abbildung dargestellte Ergebnis angezeigt.

Abbildung 10

Obwohl es also den Anschein macht, als bräuchten wir weniger Iterationen, um das Array in Zeile 06 von Code 10 zu sortieren, führen wir dennoch dieselbe Anzahl an Iterationen durch. Das mag vielen seltsam erscheinen, aber was stimmt dann mit Code 10 nicht, sodass er nicht mit weniger Iterationen auskommt? Eigentlich ist der Code in Ordnung. Jetzt muss nur noch eine Überprüfung hinzugefügt werden, um festzustellen, ob das Array sortiert ist.

Na gut, aber diese Überprüfung scheint ziemlich kompliziert zu sein, denn um herauszufinden, ob das Array sortiert ist, müssten wir es überprüfen. Das wird Zeit in Anspruch nehmen und eine zusätzliche Iteration erfordern. Das ist unerwünscht, da unser Ziel gerade darin besteht, die Anzahl der Iterationen zu verringern. Na gut, aber wie lösen wir das Problem? Meiner Meinung nach ist das der interessanteste Teil, gerade weil wir zur Lösung dieses Problems lediglich ein paar kleine Änderungen am Code vornehmen müssen. Sehen Sie sich nun an, welche Änderung am folgenden Code vorgenommen werden muss:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. void OnStart(void)
05. {
06.     string info_01[] = {"37", "78", "0", "145", "113", "139", "148", "247", "174", "189"};
07.     string info_02[] = {"value", "data", "time", "assembly", "checking" };
08. //+----------------+
09.     Print("+----------------+\nNumber array before ordering...");
10.     ArrayPrint(info_01);
11.     
12.     BubbleSort(info_01, true);
13. 
14.     Print("Number array after ordering...");
15.     ArrayPrint(info_01);
16. //+----------------+
17.     Print("+----------------+\nDictionary before ordering...");
18.     ArrayPrint(info_02);
19.     
20.     BubbleSort(info_02);
21. 
22.     Print("Dictionary after sorting...");
23.     ArrayPrint(info_02);
24. }
25. //+------------------------------------------------------------------+
26. template <typename T>
27. void BubbleSort(T &arr[], const bool bUsingLength = false)
28. {
29.     #define macroSWAP(A, B) {                           \
30.                                 temp = arr[j - 1];      \
31.                                 arr[j - 1] = arr[j];    \
32.                                 arr[j] = temp;          \
33.                                 interact = true;        \
34.                             }
35. 
36.     uint nElements = arr.Size();
37.     T    temp;
38.     bool interact = true;
39.     uint count = 0;    
40. 
41.     for (uint i = 1; (i < nElements) && interact; i++)
42.     {
43.         interact = false;
44.         for (uint j = nElements - 1; j >= i; j--, count++)
45.             if (typename(T) == "string")
46.             {
47.                 if ((bUsingLength) && ((StringLen(arr[j - 1]) > StringLen(arr[j]))))
48.                     macroSWAP(arr[j - 1], arr[j])
49.                 if ((StringCompare(arr[j - 1], arr[j]) > 0) && ((StringLen(arr[j - 1]) == StringLen(arr[j])) || !bUsingLength))
50.                     macroSWAP(arr[j - 1], arr[j])
51.             }else
52.                 if (arr[j - 1] > arr[j])
53.                     macroSWAP(arr[j - 1], arr[j])
54.     }
55. 
56.     Print("Number of interactions: ", count);
57. 
58.     #undef macroSWAP
59. }
60. //+------------------------------------------------------------------+

Code 11

Wenn wir Code 11 ausführen, erhalten wir folgendes Ergebnis:

Abbildung 11

Beachten Sie, dass in Abbildung 11 die Anzahl der Iterationen nun geringer ist, ohne dass der Code selbst wesentlich geändert wurde. Wir mussten lediglich Zeile 38 hinzufügen und dann einige Stellen im Code anpassen. Zum Beispiel die Schleife in Zeile 41 und das Makro. Beachten Sie, dass der Code selbst überprüft, ob im Array Vertauschungen vorgenommen wurden. Wenn die Schleife in Zeile 44 ausgeführt wird, Zeile 33 jedoch in keiner Iteration ausgeführt wird, können wir sicher sein, dass das Array bereits korrekt sortiert ist. Somit können wir bei der nächsten Iteration der Schleife in Zeile 41 die Prozedur zum Sortieren beenden. Interessant, nicht wahr?

Abschließende Gedanken

In diesem Artikel wurde ein sehr einfacher und leicht verständlicher Mechanismus zur Sortierung beliebiger Arrays erläutert. Es hat sich zudem gezeigt, dass das erzielte Ergebnis nicht immer mit dem übereinstimmt, was wir eigentlich erwarten. Daher muss die Implementierung angepasst werden, um korrekte Ergebnisse zu gewährleisten.

Wir haben außerdem gezeigt, dass wir mit nur geringem Aufwand eine ursprünglich langsame Implementierung in eine flexiblere umwandeln können. Dies geschieht, wenn die Situation es zulässt, dass bestimmte Arrays schneller verarbeitet werden können. Es kann sein, dass das erwartete Ergebnis bereits mit nur geringfügigen Anpassungen erzielt wurde. Dadurch sind weitere Iterationen überflüssig, da sie das erzielte Ergebnis nicht mehr verändern würden.

Da es sich bei den hier behandelten Themen größtenteils um Änderungen handelt, die zu Lehrzwecken vorgenommen wurden, enthalten die beigefügten Unterlagen ausschließlich die endgültigen Fassungen des Codes. Wenn Sie also verstehen möchten, warum ein bestimmter Ansatz gewählt wurde, schauen Sie einfach in die Codelistings, die in diesem Artikel vollständig wiedergegeben sind. Ansonsten bleibt uns nur noch, den bereits behandelten Stoff durchzuarbeiten und das Gelernte zu üben, um zu verstehen, wie der hier gezeigte Mechanismus funktioniert.