1. Epic GamesDeveloper
  3. Sortieralgorithmen in Verse

Sortieralgorithmen in Verse

Lerne, wie man Listen von Objekten mit Hilfe von Sortieralgorithmen sortiert

Sortieralgorithmen in Verse

Sortieren ist ein einfaches, aber mächtiges Konzept. Wenn du eine ungeordnete Liste von Objekten nimmst, kannst du einen Algorithmus verwenden, um sie in eine bestimmte Reihenfolge zu bringen. So einfach diese Idee auch klingen mag, das Sortieren kommt in der Informatik in vielen verschiedenen Aspekten und Formen vor. Eine der wichtigsten Anwendungen ist die Beschleunigung von Suchvorgängen. Zum Beispiel sortiert dein Computer die Dateien nach Name und Größe, damit du schnell die gewünschte Datei findest. Mit UEFN kannst du die Objekte im Outliner nach Typ sortieren, um die Dinge zusammenzufassen und dein Projekt zu organisieren. In Fortnite werden die Spieler auf der Punkteanzeige im Spiel nach vielen verschiedenen Statistiken wie Eliminierungen und Rundenzeiten sortiert, damit jeder weiß, wer an der Spitze steht.

Das Anwenden des Sortierens auf Verse-Code kann dir helfen, dein Gameplay zu verbessern und Aspekte deiner Entwicklung zu erweitern. Wie wäre es zum Beispiel, ein Array von Spielern nach ihrem Score in einem Turnier zu ordnen, wobei die Spieler, die in jeder Runde die wenigsten Punkte erzielt haben, eliminiert werden? Indem du dieses Array am Ende jeder Runde sortierst, kannst du schnell die niedrigsten Punktzahlen finden und sie als Zuschauer einstellen. Andererseits kannst du dir genauso schnell die Spieler mit dem besten Score holen und ihnen einen Bonus für die nächste Runde verleihen. Du kannst diese sortierte Liste sogar verwenden, um dauerhafte lokale Ranglisten zu erstellen, damit die Spieler wissen, auf wen sie während des Spiels achten müssen. Und wenn du eine Liste von Leuten hast, die du auf deiner Insel grüßen möchtest, kannst du ihre Namen alphabetisch sortieren, um sie leichter anzeigen zu können.

Jedes dieser Beispiele verwendet die Sortierung auf unterschiedliche Weise, aber unter der Haube verwenden sie alle einen Sortieralgorithmus, um ihr Ziel zu erreichen. Sortieralgorithmen implementieren die Logik, mit der deine Listen sortiert werden; es gibt viele verschiedene Typen, aus denen du je nach deinen Bedürfnissen wählen kannst. Sortieren ist ein mächtiges Werkzeug und es ist wichtig zu verstehen, wie es funktioniert, wenn du es in deine Projekte integrieren willst. Diese Seite behandelt die wichtigsten Ideen hinter dem Sortieren und zeigt dir, wie du den Algorithmus auswählst, der für dein Projekt am besten geeignet ist. Für Implementierungen von bestimmten Algorithmen besuche den Link am Ende dieser Seite.

Mergesort

Mergesort ist ein Divide-and-Conquer-Sortieralgorithmus. Das bedeutet, dass er die Gruppe der Elemente, die sortiert werden müssen, in kleinere Gruppen aufteilt und die kleineren Gruppen sortiert. Anschließend werden die kleineren Gruppen mit dem Wissen, dass sie bereits sortiert sind, zusammengeführt.

Implementieren von Mergesort

Die folgende Implementierung ruft sich selbst auf, um die geteilten Arrays zusammenzuführen, d. h. es handelt sich um eine rekursive Funktion. Bei einer rekursiven Funktion musst du einen Basisfall angeben, um unendliche Rekursionen zu verhindern. Da dieser Algorithmus die Arrays jedes Mal in zwei Hälften teilt, ist der Basisfall das Array mit nur einem Element. Daher wird das Array als sortiert betrachtet, um mit einem Element zu starten und kann mit einem anderen 1-Element-Array zusammengeführt werden und so weiter bis zum vollständigen Array mit allen Elementen.

Die folgende Implementierung ist generisch, indem sie parametrische Typen für ihre Parameter verwendet. Das heißt, du kannst jeden beliebigen Typ für die Elemente und deine eigene Vergleichsfunktion als Argumente verwenden. Du kannst also ein Ganzzahl-Array haben, das du sortierst, oder ein Array eines komplexeren Typs wie eine Klasse, die du sortieren kannst. Die Compare-Funktion ist ein weiterer Parameter, dem du deine eigenen benutzerdefinierten Funktionen übergeben kannst. Wenn du nach der kleinsten bis zur größten Klasse oder nach bestimmten Feldern einer Klasse sortieren möchtest, kannst du das in deiner benutzerdefinierten Funktion festlegen, ohne diese Implementierung der generischen Funktion zu ändern.

Befolge diese Schritte, um die Mergesort in Verse zu implementieren:

  1. Schreiben wir zunächst den Basisfall: nur ein Element im Array. Wenn es ein Element oder weniger gibt, gib das Array-Argument zurück, das an die Funktion übergeben wurde.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # Überprüfe, ob das Array mehr als ein Element enthält, sonst haben wir den Basisfall erreicht.
     else:
         # Gib das übergebene Array zurück, da wir den Basisfall erreicht haben.
         Array

  2. Teile dann das Array in zwei Hälften.

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # Überprüfe, ob das Array mehr als ein Element enthält, sonst haben wir den Basisfall erreicht.
         Mid:int = Floor(Length / 2) # Hol den mittleren Index des Arrays.
         Left:[]t = Array.Slice[0, Mid] # Teile das Array in zwei Hälften. Dies bewahrt Elemente vom Anfang bis zum Index Mid - 1.
         Right:[]t = Array.Slice[Mid] # Teile das Array in zwei Hälften. Dies bewahrt Elemente vom Index Mid bis zum Ende des Arrays.
     else:
         # Gib das übergebene Array zurück, da wir den Basisfall erreicht haben.
         Array

  3. Rufe MergeSort für jede Hälfte des ursprünglichen Arrays auf und füge dann die beiden Hälften zusammen (Merge).

     MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     Length:int = Array.Length
     if:
         Length > 1 # Überprüfe, ob das Array mehr als ein Element enthält, sonst haben wir den Basisfall erreicht.
         Mid:int = Floor(Length / 2) # Hol den mittleren Index des Arrays.
         Left:[]t = Array.Slice[0, Mid] # Teile das Array in zwei Hälften. Dies bewahrt Elemente vom Anfang bis zum Index Mid - 1.
         Right:[]t = Array.Slice[Mid] # Teile das Array in zwei Hälften. Dies bewahrt Elemente vom Index Mid bis zum Ende des Arrays.
     then:
         # MergeSort auf der linken Hälfte des Arrays aufrufen.
         LeftSorted:[]t = MergeSort(Left, Compare)

         # MergeSort auf der rechten Hälfte des Arrays aufrufen.
         RightSorted:[]t = MergeSort(Right, Compare)

         # Kombiniere die beiden Arrays und gib das Ergebnis zurück.
         Merge(LeftSorted, RightSorted, Compare)
     else:
         # Gib das übergebene Array zurück, da wir den Basisfall erreicht haben.
         Array

  4. Wenn du die beiden Hälften wieder zusammenfügst, vergleichst du die Elemente aus jedem Array und fügst sie zum resultierenden Array hinzu, bis alle Elemente aus beiden Arrays hinzugefügt wurden. Dazu brauchst du eine Indexvariable, um die Positionen in jedem Array zu verfolgen. Jedes Mal, wenn die Compare-Funktion erfolgreich ist, sollte das linke Element des Arrays hinzugefügt und seine Indexvariable auf die nächste Position im Array gesetzt werden, andernfalls wird das Gleiche mit dem rechten Element des Arrays gemacht. Sobald alle Elemente aus einem der Arrays hinzugefügt wurden, fügst du die restlichen Elemente aus dem anderen Array hinzu, da dieses bereits sortiert wurde.

     # Eine Hilfsfunktion für MergeSort, die die geteilten Arrays auf Basis der Compare-Funktion in einer bestimmten Reihenfolge kombiniert.
 Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
     var LeftIndex:int = 0
     var RightIndex:int = 0
     var MergedArray:[]t = array{}
    
     # Durchlaufe alle Elemente in den Arrays, um sie der Variable MergedArray hinzuzufügen.
     loop:
         if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
             # Prüfe das Element im Array der linken Hälfte mit dem Element im Array der rechten Hälfte.
             # Verwendet die als Argument übergebene Compare-Funktion
             if (Compare[LeftElement, RightElement]):
                 set MergedArray += array{LeftElement}
                 set LeftIndex += 1
             else:
                 set MergedArray += array{RightElement}
                 set RightIndex += 1
         else:
             # Wir haben an dieser Stelle alle Elemente aus einem der Arrays hinzugefügt.
             # Prüfe nun, welches Array noch Elemente zum Zusammenführen hat, und füge alle verbleibenden Elemente hinzu.
             if (LeftIndex >= Left.Length):
                 option{set MergedArray += Right.Slice[RightIndex]}
             else:
                 option{set MergedArray += Left.Slice[LeftIndex]}
             # Verlasse die Schleife, da wir alle Elemente hinzugefügt haben.
             break

     # Gib das zusammengeführte Array zurück.
     MergedArray

Vollständiges Script

    # Ein Divide-and-Conquer-Sortierungsalgorithmus, der ein Array in zwei Teile aufspaltet, jeden der Array-Teile sortiert und sie dann zusammenfügt.
    # Dies ist eine rekursive Implementierung, bei der die Funktion sich selbst aufruft, um die geteilten Arrays zusammenzuführen.
    # Der Basisfall (die Bedingung zum Stoppen der Rekursion) ist, dass das Array nur ein Element hat.
    # Dies ist eine generische Implementierung, die parametrische Typen verwendet, so dass du deinen eigenen Typ und deine eigene Vergleichsfunktion als Argumente bereitstellen kannst.
    MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        Length:int = Array.Length
        if:
            Length > 1 # Überprüfe, ob das Array mehr als ein Element enthält, sonst haben wir den Basisfall erreicht.
            Mid:int = Floor(Length / 2) # Hol den mittleren Index des Arrays.
            Left:[]t = Array.Slice[0, Mid] # Teile das Array in zwei Hälften. Dies bewahrt Elemente vom Anfang bis zum Index Mid - 1.
            Right:[]t = Array.Slice[Mid] # Teile das Array in zwei Hälften. Dies bewahrt Elemente vom Index Mid bis zum Ende des Arrays.
        then:
            # MergeSort auf der linken Hälfte des Arrays aufrufen.
            LeftSorted:[]t = MergeSort(Left, Compare)

            # MergeSort auf der rechten Hälfte des Arrays aufrufen.
            RightSorted:[]t = MergeSort(Right, Compare)

            # Kombiniere die beiden Arrays und gib das Ergebnis zurück.
            Merge(LeftSorted, RightSorted, Compare)
        else:

            # Gib das übergebene Array zurück, da wir den Basisfall erreicht haben.
            Array

    # Eine Hilfsfunktion für MergeSort, die die geteilten Arrays auf Basis der Compare-Funktion in einer bestimmten Reihenfolge kombiniert.
    Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
        var LeftIndex:int = 0
        var RightIndex:int = 0
        var MergedArray:[]t = array{}

        # Durchlaufe alle Elemente in den Arrays, um sie der Variable MergedArray hinzuzufügen.
        loop:
            if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
                # Prüfe das Element im Array der linken Hälfte mit dem Element im Array der rechten Hälfte.
                # Verwendet die als Argument übergebene Compare-Funktion
                if (Compare[LeftElement, RightElement]):
                    set MergedArray += array{LeftElement}
                    set LeftIndex += 1
                else:
                    set MergedArray += array{RightElement}
                    set RightIndex += 1
            else:
                # Wir haben an dieser Stelle alle Elemente aus einem der Arrays hinzugefügt.
                # Prüfe nun, welches Array noch Elemente zum Zusammenführen hat, und füge alle verbleibenden Elemente hinzu.
                if (LeftIndex >= Left.Length):
                    option{set MergedArray += Right.Slice[RightIndex]}
                else:
                    option{set MergedArray += Left.Slice[LeftIndex]}
                # Verlasse die Schleife, da wir alle Elemente hinzugefügt haben.
                break

        # Gib das zusammengeführte Array zurück.
        MergedArray

Auswahl eines Algorithmus

Auch wenn viele Sortieralgorithmen ähnlichen Ideen folgen, unterscheiden sie sich in einigen Punkten, die einen großen Einfluss auf die Performance des Algorithmus haben können.

Zeitkomplexität

Algorithmen brauchen Zeit, und je mehr Dinge sie zu tun haben, desto länger brauchen sie. Eine Reihe von Faktoren beeinflusst die Komplexität des Problems, das der Algorithmus zu lösen versucht, und die Zeit, die er dafür benötigt, wird als Zeitkomplexität bezeichnet.

Da es fast unmöglich ist, die genaue Zeit zu berechnen, die ein Algorithmus benötigt, um seine Arbeit zu erledigen – da viele Faktoren eine Rolle spielen, wie z. B. die Hardware des Computers, anderer laufender Code oder die Art der Daten, mit denen gearbeitet wird –, wird die Zeitkomplexität stattdessen in Operationen oder der Anzahl der Aktionen gemessen, die ein Algorithmus durchführen muss, um seine Arbeit zu erledigen. Da jeder Algorithmus anders ist, wird die für die Verarbeitung eines Datensatzes benötigte Zeit in der Big-O-Notation dargestellt. Die Big-O-Notation beschreibt nicht die genaue Anzahl der erforderlichen Operationen, sondern wie sich diese Zahl mit der Größe der Liste, die du als Eingabe für den Algorithmus verwendest, verändert.

Ein Beispiel: Du schreibst einen Algorithmus, der die kleinste Zahl in einer Liste finden soll. Du weißt nicht, ob die Liste geordnet ist, also muss dein Algorithmus jede Zahl prüfen, um zu ermitteln, ob sie die kleinste ist. Wenn die Liste drei Elemente enthält, führt dein Algorithmus drei Überprüfungen durch, und wenn sie zehn Elemente enthält, zehn. Da die Anzahl der Operationen linear mit der Eingabegröße deiner Liste ansteigt, ist die Zeitkomplexität linear, oder O(n), wobei n die Anzahl der Elemente in deiner Liste ist. Wenn dein Algorithmus zwei Operationen pro Element durchführen müsste, wie z. B. das Kopieren jedes Elements in eine andere Liste nach jeder Überprüfung, wäre die Zeitkomplexität O(2n), da die Anzahl der Operationen 2 * AnzahlDerElemente ist.

Was wäre, wenn dein Algorithmus nur prüfen wollte, ob Elemente in der Liste vorhanden sind? Da dein Algorithmus unabhängig von der Größe der Eingabe nur eine Operation durchführt, wäre die Zeitkomplexität konstant, also O(1). Es gibt noch viele andere Beispiele wie quadratische Zeit (O(n^2)) oder faktorielle Zeit (O(n!)), aber wichtig ist, dass jede dieser Angaben beschreibt, wie die Anzahl der durchgeführten Operationen mit der Eingabegröße wächst.

Komplexität beim Sortieren

Die Messung der Zeitkomplexität für Sortieralgorithmen wird aufgrund der verschiedenen Zustände, in denen sich eine Liste vor der Sortierung befinden kann, wesentlich komplizierter. Was ist, wenn sie schon sortiert ist? Was ist, wenn sie in umgekehrter Reihenfolge sortiert ist? Die Performance eines Algorithmus kann in Abhängigkeit von diesen Faktoren stark variieren. Deshalb werden Sortieralgorithmen in der Regel anhand ihrer Zeitkomplexität im besten, durchschnittlichen und schlechtesten Fall (Best Case, Average Case und Worst Case) gemessen.

Schauen wir uns zum Beispiel den Bubblesort-Algorithmus an. Im besten Fall muss Bubblesort bei einer bereits sortierten Liste nur jedes Paar von Elementen prüfen, aber keine Tauschvorgänge durchführen! Das bedeutet, dass die Zeitkomplexität im besten Fall O(n) beträgt, was großartig ist! Aber was ist mit dem umgekehrten Szenario, bei dem die Liste rückwärts sortiert ist? In diesem Fall muss Bubblesort n Prüfungen durchführen und jedes Element in der Liste n-mal tauschen, so dass die Zeitkomplexität im schlechtesten Fall n * n oder O(n^2) beträgt. Das gilt im Vergleich zu anderen Sortieralgorithmen als langsam und kann sehr schnell aus dem Ruder laufen, da der Algorithmus mindestens einhundert Operationen benötigen würde, um eine Liste mit zehn Elementen zu verarbeiten. Kannst du dir vorstellen, wie viele Operationen für einhundert Elemente nötig wären? Wie sieht es bei eintausend aus?

Anstelle von Best Case und Worst Case liefern Sortieralgorithmen in der Regel eine Performance, die näher an ihrem Average Case liegt. Zum Beispiel ist die durchschnittliche Zeitkomplexität von Mergesort O(nlogn). Dies gilt als guter Benchmark, da viele andere gewöhnliche Sortieralgorithmen im besten, schlechtesten und durchschnittlichen Fall eine Zeitkomplexität auf oder nahe diesem Niveau haben. Bubblesort von vorhin hat eine durchschnittliche Komplexität von O(n^2), also ist es selbst im durchschnittlichen Fall noch relativ langsam.

Wenn du einen Algorithmus auswählst, ist es wichtig, die Zeitkomplexität zu kennen, denn du möchtest, dass dein Code schnell läuft und unabhängig vom Eingabetyp die gleiche Performance hat. Beispiele für gängige effiziente Sortieralgorithmen findest du unter Mergesort und Quicksort. Diese beiden Algorithmen haben im besten, schlechtesten und durchschnittlichen Fall die gleiche Komplexität von O(nlogn) und sind ein guter Ausgangspunkt für jede Sortiersituation.

Platzkomplexität

Neben der Zeitkomplexität ist es auch wichtig zu bedenken, was dein Algorithmus alles erstellen muss, um den Sortiervorgang abzuschließen. Dies ist die Platzkomplexität oder die Menge an zusätzlichen Daten, die bei der Ausführung deines Algorithmus erstellt wird. Wie die Zeitkomplexität wird auch die Platzkomplexität mit der Big-_O -Notation gemessen, die von Algorithmus zu Algorithmus unterschiedlich ist. Weil Mergesort zum Beispiel eine Liste in _n Unterlisten aufteilt, hat es eine Platzkomplexität von O(n). Algorithmen, die Objekte an Ort und Stelle sortieren (d. h. sie verändern nur bestehende Daten, anstatt neue Daten zu erzeugen), haben eine Platzkomplexität von O(1). Wenn du mit sehr großen Listen arbeitest, solltest du bei der Auswahl deines Algorithmus auf die Platzkomplexität achten.

Da Verse eine funktionale Programmiersprache ist, geben Datenstruktur-API-Operationen modifizierte Versionen des ursprünglichen Elements zurück, der als Eingabe übergeben wurde. Zum Beispiel verändern sowohl die Array-Funktion Insert() als auch RemoveElement() nicht das ursprüngliche Array, sondern erstellen ein neues Array und geben dieses zurück, nachdem die Funktion ausgeführt wurde. Dies kann zu einem höheren Aufwand an Zeit und Platz für die Schaffung dieser neuen Elemente führen.

Stabilität

Beim Sortieren stößt dein Algorithmus oft auf unentschiedene Situationen. Wie soll der Algorithmus zum Beispiel bei zwei Spielern mit jeweils fünf Punkten die Spieler sortieren? In diesem Szenario behält ein stabiler Algorithmus die Reihenfolge bei, in der gleiche Elemente nach der Sortierung in der Liste erscheinen. Wenn also Spieler eins vor der Sortierung vor Spieler zwei in der Liste stand, steht in der sortierten Liste immer noch Spieler eins vor Spieler zwei.

Ein instabiler Algorithmus wird diese Reihenfolge jedoch nicht unbedingt beibehalten, was bedeutet, dass Spieler zwei vor Spieler eins erscheinen könnte. Das ist wichtig, wenn sich dein Code um die ersten paar Elemente in einer Liste kümmert, z. B. wenn du die drei besten Spieler nach Punktzahl in eine Rangliste holen willst. In diesem Fall würdest du dir einen stabilen Algorithmus wünschen, der sicherstellt, dass derjenige, der diese Punktzahl zuerst erreicht hat, in der Rangliste bleibt.

Testen und Profilieren deiner Algorithmen

Es ist zwar gut zu wissen, wie dein Algorithmus angesichts der Zeit- und Platzkomplexität voraussichtlich laufen wird, aber noch wichtiger ist es, zu messen, wie dein Algorithmus bei echten Eingaben tatsächlich abschneidet. Die Entwicklung von Sortieralgorithmen kann schwierig sein, und es kann schwierig sein zu erkennen, ob dein Code für alle Eingaben einheitlich funktioniert. Hier kommt das Testen ins Spiel. Indem du eine Testfunktion einrichtest, kannst du die Genauigkeit deines Codes überprüfen und während der Entwicklung feststellen, wie er sich verhält. Du kannst auch sehen, ob sich die Performance verschlechtert, wenn du die zu testende Implementierung änderst. Befolge diese Schritte, um eine Testdatei für deine Sortieralgorithmen einzurichten und Daten über deren Performance auszugeben:

  1. Erstelle eine fehlbare Funktion mit dem Namen RunArrayTest.

     # Testfunktion zum Sortieren von Arrays und zum Profilieren des Codes.
 RunArrayTest()<decides><transacts>:void=

  2. Füge das Argument für das Array, das du sortieren möchtest, und die zu verwendende Vergleichsfunktion hinzu.

     # Testfunktion zum Sortieren von Arrays und zum Profilieren des Codes.
 RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
     # Führe Mergesort aus
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

  3. Jetzt musst du das sortierte Array mit dem erwarteten Ergebnis vergleichen. Füge das Argument für das erwartete Array hinzu, um es mit dem sortierten tatsächlichen Array zu vergleichen und zu überprüfen, ob das Ergebnis korrekt ist.

    Vergleiche die Elemente in ResultArray mit den Elementen in ExpectedArray. Die Funktion RunArrayTest ist fehlbar, d. h. sobald ein Element nicht übereinstimmt, schlägt die Testfunktion fehl.

     # Testfunktion zum Sortieren von Arrays und zum Profilieren des Codes.
 RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void=
     # Führe Mergesort aus
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

     # Überprüfe, ob der Test bestanden wurde und das Array wie erwartet sortiert wurde.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

  4. Füge eine Argument-Funktion hinzu, um die Arrays bei jedem Schritt auszugeben, damit du sie vergleichen kannst, wenn der Test fehlgeschlagen ist, und damit du weißt, wie du den Code, den du testest, korrigieren kannst.

     # Testfunktion zum Sortieren von Arrays und zum Profilieren des Codes.
 RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
     # Führe Mergesort aus
     ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare)

     # Gib die Arrays Actual, Expected und Result zur Fehlersuche aus.
     ProjectLog("Actual: {ArrayToString(ActualArray)}")
     ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
     ProjectLog("Result: {ArrayToString(ResultArray)}")

     # Überprüfe, ob der Test bestanden wurde und das Array wie erwartet sortiert wurde.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

  5. Deine Testfunktion prüft auf die Richtigkeit des Ergebnisses, aber du kannst dir auch mehr Informationen aus deinem Test holen. Mit dem profile-Ausdruck kannst du die Performance deiner Algorithmen messen, indem du die Zeit protokollierst, die der Algorithmus zum Abschließen braucht.

    Dies ist nützlich, wenn du die Performance verschiedener Sortieralgorithmen vergleichen oder testen willst, wie deine Algorithmen bei unterschiedlichen Eingaben laufen. Einzelne Algorithmen können bei Best- und Worst-Case-Eingaben sehr unterschiedlich performen, und mit dem Profiling kannst du diese Fälle finden und testen, um zu erfahren, worauf du achten musst. Über mehrere Tests kannst du die durchschnittliche Performance deines Algorithmus ermitteln und abschätzen, wie er bei Eingaben von beliebiger Größe abschneidet.

  6. Füge ein String-Argument mit dem Namen Description hinzu, das erklärt, worauf der Test fokussiert ist. Du kannst dies zum profileAusdruck hinzufügen, um die Beschreibung mit dem zeitlichen Wert zu protokollieren.

     # Testfunktion zum Sortieren von Arrays und zum Profilieren des Codes.
 RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=

     # Führe Mergesort aus und profiliere den Code.
     ResultArray := profile(Description):
         SortingAlgorithms.MergeSort(ActualArray, Compare)

     # Gib die Arrays Actual, Expected und Result zur Fehlersuche aus.
     ProjectLog("Actual: {ArrayToString(ActualArray)}")
     ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
     ProjectLog("Result: {ArrayToString(ResultArray)}")
    
     # Überprüfe, ob der Test bestanden wurde und das Array wie erwartet sortiert wurde.
     for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
         Result = Expected

Schreiben von Testfällen

Beginne einfach. Isoliere, was du testest. Teste ein Ganzzahl-Array, das vom kleinsten zum größten Wert sortiert wird.

  1. Erstelle eine Vergleichsfunktion für Ganzzahlen.

     # Vergleichsfunktion, die als Argument für die Sortierung von Ganzzahlen von der kleinsten zur größten Zahl verwendet werden kann.
 IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
     Left < Right

  2. Erstelle eine Hilfsfunktion, um ein Ganzzahl-Array in einen String umzuwandeln.

     # Hilfsfunktion, um ein Array aus Ganzzahlen in einen String umzuwandeln.
 IntArrayToString(Array:[]int)<transacts>:string=
     var ConvertedToString:string = "["
     for (Index -> Element : Array):
         set ConvertedToString += "{Element}"
         if (Index < Array.Length - 1):
             set ConvertedToString += ", "
     set ConvertedToString += "]"

  3. Erstelle ein Verse-Gerät, um den Test durchzuführen.

     # Diese Datei enthält Tests, mit denen überprüft werden kann, ob sich der Algorithmus wie erwartet verhält.
 # Die Tests umfassen auch die Profilierung des Codes, um die Performance des Algorithmus zu sehen.

 using { /Fortnite.com/Devices }
 using { /UnrealEngine.com/Temporary/Diagnostics }
 using { /Verse.org/Simulation }
 using { /Verse.org/Random }

 my_log_channel<public> := class(log_channel):

 # Ein projektweiter „Logger“ zur Ausgabe von Nachrichten von Funktionen, die sich in keiner Klasse mit einem Protokoll befinden
 # Die Ausgabe ohne Logger ist <no_rollback>, sodass sie nicht in einer <transacts>-Funktion verwendet werden kann.
 ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
     Logger := log{Channel := my_log_channel}
     Logger.Print(Message, ?Level := Level)

 # Ein mit Verse erstelltes Kreativmodus-Gerät, das in einem Level platziert werden kann
 # Im Level platzieren, um Tests durchzuführen und Code zu profilieren.
 test_sorting := class(creative_device):

     # Wird ausgeführt, wenn das Gerät in einem laufenden Spiel gestartet wird
     OnBegin<override>()<suspends>:void=
         # Beispiel-Arrays, die für den Test verwendet werden.
         Test1ExpectedIntArray:[]int = array{}
         Test1ActualIntArray:[]int = array{}

         # Führe die Tests durch und melde, ob sie fehlgeschlagen sind oder erfolgreich waren.
         if:
             RunArrayTest["Integer-Array in aufsteigender Reihenfolge vom kleinsten zum größten Wert", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
         then:
             ProjectLog("Alle Tests bestanden.")
         else:
             ProjectLog("Einer oder mehrere Tests sind fehlgeschlagen.")

  4. Bevölkere nun die Test-Arrays mit Werten.

     var ArrayLength:int = GetRandomInt(10, 100)
         Test1ExpectedIntArray:[]int =
             for (Count := 0..ArrayLength):
             	Anzahl
         Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

  5. Führe den Test durch, indem du das Verse-Gerät in dein Level ziehst

Im Folgenden findest du mehr Ideen für Tests, die du durchführen kannst:

* Sortiere ein Ganzzahl-Array vom größten zum kleinsten Wert.

        # Vergleichsfunktion, die als Argument für die Sortierung von Ganzzahlen von der größten zur kleinsten Zahl verwendet wird.
        IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
            Left > Right

* Sortiere ein Ganzzahl-Array, das doppelte Werte enthält.

        Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
        Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

* Sortiere eine Klasse nach einem ihrer Felder.

        # Eine Beispielklasse zum Testen der Sortierung.
        player_stats := class<unique>:
            Wins:int = 0
            RoundsPlayed:int = 0

        # Vergleichsfunktion, die als Argument für die Sortierung von Siegen vom kleinsten zum größten verwendet wird.
        IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
            Left.Wins < Right.Wins
            Links

        # Hilfsfunktion, um die Vergleichswerte der Spieler-Statistiken in einen String zu konvertieren.
        PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
            var ConvertedToString:string = "["

            for (Index -> Element : Array):
                set ConvertedToString += "{Element.Wins}"
                if (Index < Array.Length - 1):
                    set ConvertedToString += ", "
            set ConvertedToString += "]"

Vollständiges Script

    # Diese Datei enthält Tests, mit denen überprüft werden kann, ob sich der Algorithmus wie erwartet verhält.
    # Die Tests umfassen auch die Profilierung des Codes, um die Performance des Algorithmus zu sehen.

    using { /Fortnite.com/Devices }
    using { /UnrealEngine.com/Temporary/Diagnostics }
    using { /Verse.org/Simulation }
    using { /Verse.org/Random }

    my_log_channel<public> := class(log_channel):

    # Ein projektweiter „Logger“ zur Ausgabe von Nachrichten von Funktionen, die sich in keiner Klasse mit einem Protokoll befinden
    # Die Ausgabe ohne Logger ist <no_rollback>, sodass sie nicht in einer <transacts>-Funktion verwendet werden kann.
    ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
        Logger := log{Channel := my_log_channel}
        Logger.Print(Message, ?Level := Level)

    # Ein mit Verse erstelltes Kreativmodus-Gerät, das in einem Level platziert werden kann
    # Im Level platzieren, um Tests durchzuführen und Code zu profilieren.
    test_sorting := class(creative_device):

        # Wird ausgeführt, wenn das Gerät in einem laufenden Spiel gestartet wird
        OnBegin<override>()<suspends>:void= 

            # Beispiel-Arrays, die für den Test verwendet werden.
            var ArrayLength:int = GetRandomInt(10, 100)

            Test1ExpectedIntArray:[]int =
                for (Count := 0..ArrayLength):
                	Anzahl

            Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)

            set ArrayLength = GetRandomInt(10, 100)

            Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
                ArrayLength - Count

            Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)

            Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}

            Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)

            set ArrayLength = GetRandomInt(10, 100)
            Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
                player_stats:
                    Wins := ArrayLength - Count
                    RoundsPlayed := GetRandomInt(Count, Count * 30)

            Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)

            # Führe die Tests durch und melde, ob sie fehlgeschlagen sind oder erfolgreich waren.
            if:
                RunArrayTest["Integer-Array in aufsteigender Reihenfolge vom kleinsten zum größten Wert", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
                RunArrayTest[„Ganzzahl-Array in der Reihenfolge vom größten zum kleinsten", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
                RunArrayTest[„Ganzzahl-Array in der Reihenfolge vom kleinsten zum größten mit Wiederholungen", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
                RunArrayTest[„Spieler-Statistiken-Array in der Reihenfolge von der größten Anzahl an Siegen zur kleinsten", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
            then:
                ProjectLog("Alle Tests bestanden.")
            else:
                ProjectLog("Einer oder mehrere Tests sind fehlgeschlagen.")

    # Testfunktion zum Sortieren von Arrays und zum Profilieren des Codes.
    RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=

        # Führe Mergesort aus und profiliere den Code.
        ResultArray := profile(Description):
            SortingAlgorithms.MergeSort(ActualArray, Compare)

        # Gib die Arrays Actual, Expected und Result zur Fehlersuche aus.
        ProjectLog("Actual: {ArrayToString(ActualArray)}")
        ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
        ProjectLog("Result: {ArrayToString(ResultArray)}")

        # Überprüfe, ob der Test bestanden wurde und das Array wie erwartet sortiert wurde.
        for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
            Result = Expected

    # Hilfsfunktion, um ein Array aus Ganzzahlen in einen String umzuwandeln.
    IntArrayToString(Array:[]int)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"

    # Hilfsfunktion, um die Vergleichswerte der Spieler-Statistiken in einen String zu konvertieren.
    PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
        var ConvertedToString:string = "["
        for (Index -> Element : Array):
            set ConvertedToString += "{Element.Wins}"
            if (Index < Array.Length - 1):
                set ConvertedToString += ", "
        set ConvertedToString += "]"

    # Vergleichsfunktion, die als Argument für die Sortierung von Ganzzahlen von der kleinsten zur größten Zahl verwendet werden kann.
    IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
        Left < Right

    # Vergleichsfunktion, die als Argument für die Sortierung von Ganzzahlen von der größten zur kleinsten Zahl verwendet wird.
    IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
        Left > Right

    # Eine Beispielklasse zum Testen der Sortierung.
    player_stats := class<unique>:
        Wins:int = 0
        RoundsPlayed:int = 0

    # Vergleichsfunktion, die als Argument für die Sortierung von Siegen vom kleinsten zum größten verwendet wird.
    IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
        Left.Wins < Right.Wins
        Links

    # Vergleichsfunktion, die als Argument für die Sortierung von Siegen vom größten zum kleinsten verwendet wird.
    IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
        Left.Wins > Right.Wins
        Links

Auf eigene Faust

  • Implementiere einen anderen Sortieralgorithmus. Du findest hier folgende weitere Algorithmen:

  • Füge weitere Testfälle hinzu, um die Abdeckung des Testers zu erhöhen. Fallen dir Grenzfälle ein, die der Tester noch nicht abdeckt? Oder wie sieht es mit komplexeren Datentypen aus?

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page