Wie im Lounge-Raum zum Stapelüberlauf beschrieben:
Wenn Sie den Quicksort-Algorithmus von en.wikipedia.org/wiki/Quicksort nicht in einer Sprache implementieren können, in der Sie nur minimale Kenntnisse haben, sollten Sie einen anderen Beruf in Betracht ziehen. @sbi
aber SBI merkte auch an, dass vielleicht BrainF *** eine Ausnahme war.
Also, hier ist das Rätsel / die Herausforderung: Implementiere QuickSort in BrainF *** . Die Umsetzung muss
code-challenge
sorting
brainfuck
Ronald
quelle
quelle
Antworten:
BrainF * (697 Bytes)
Unten ist eine kommentierte Version. Um zu verfolgen, was während der Entwicklung passieren sollte, habe ich eine Kommentarnotation verwendet, die so aussieht:
|a|b=0|c=A0|@d|A0|A1|```|
Der Speicher ist mit einem links wachsenden Stapel zu verarbeitender Partitionen, einem Arbeitsbereich in der Mitte und einem rechts sortierten Array ausgestattet. Die Array-Indizierung wird durchgeführt, indem ein "Datenbus", der den Index und den Arbeitsbereich enthält, durch das Array bewegt wird. So wird zum Beispiel ein 3er-Bus von
|i|data|0|A0|A1|A2
,|A0|i-1|data|0|A1|A2
nach dem um eins verschoben wird. Die Unterteilung wird durchgeführt, indem der Bus zwischen dem hohen und dem niedrigen Element gehalten wird.Hier ist die Vollversion:
quelle
if (i<j) {} else {}
mehrere Versuche, um es richtig zu machen. Und die Randfälle sind Mörder. Ich weiß nicht, wie oft ich dachte "nur dieses eine kleine Ding ist noch übrig ..." und dann einen Testfall entdeckte, der weitere Stunden Arbeit verursachte. Ich glaube, ich kann es um ein paar Dutzend Zeichen reduzieren, bin mir aber nicht sicher, ob ich mich anstrengen möchte.Brainfuck (178 Bytes)
Auch wenn Brainfuck umständlich ist, hilft es, mit der Körnung der Sprache zu arbeiten. Fragen Sie sich: "Muss ich diesen Wert explizit in einer Zelle speichern?" Sie können häufig an Geschwindigkeit und Präzision gewinnen, indem Sie etwas Feinsinnigeres tun. Und wenn der Wert ein Arrayindex (oder eine beliebige natürliche Zahl) ist, passt er möglicherweise nicht in eine Zelle. Natürlich können Sie dies als Grenze Ihres Programms akzeptieren. Das Entwerfen Ihres Programms für den Umgang mit großen Werten verbessert es jedoch häufig auf andere Weise.
Wie üblich war meine erste Arbeitsversion doppelt so lang wie nötig - 392 Bytes. Zahlreiche Modifikationen und zwei oder drei größere Änderungen führten zu dieser vergleichsweise eleganten 178-Byte-Version. (Obwohl eine lineare Zeitsortierung amüsanterweise nur 40 Bytes umfasst.)
Die Eingabewerte sind in Abständen von jeweils drei Zellen angeordnet: Für jede (V) Wertezelle gibt es eine (L) Wertezelle (für die Navigation) und eine weitere Zelle für den (S) Cratch-Raum. Das Gesamtlayout des Arrays ist
0 1 0 0 0 SVLSVL ... SVL 0 0 0 0 0 0 ...
Zu Beginn werden alle L-Zellen auf 1 gesetzt, um Teile des Arrays zu markieren, die noch sortiert werden müssen. Wenn wir mit dem Partitionieren eines Subarrays fertig sind, teilen wir es in kleinere Subarrays auf, indem wir die L-Zelle des Pivots auf 0 setzen, dann die am weitesten rechts liegende L-Zelle ausfindig machen, die noch 1 ist, und das Subarray als nächstes partitionieren. Seltsamerweise ist dies die gesamte Buchhaltung, die wir benötigen, um die rekursive Verarbeitung von Subarrays ordnungsgemäß zu handhaben. Wenn alle L-Zellen auf Null gesetzt wurden, wird das gesamte Array sortiert.
Um ein Subarray zu partitionieren, ziehen wir seinen äußersten rechten Wert in eine S-Zelle, um als Drehpunkt zu fungieren, und bringen ihn (und die entsprechende leere V-Zelle) nach links, vergleichen ihn mit dem Wert im Subarray und tauschen ihn nach Bedarf aus. Am Ende wird der Pivot mit demselben Swap-Code (der ungefähr 50 Bytes spart) wieder eingelagert. Während der Partitionierung werden zwei zusätzliche L-Zellen auf 0 gesetzt, um die zwei Zellen zu markieren, die möglicherweise gegeneinander ausgetauscht werden müssen. Am Ende der Partitionierung verschmilzt die linke 0 mit der 0 links vom Subarray und die rechte 0 markiert den Drehpunkt. Bei diesem Vorgang verbleibt außerdem eine zusätzliche 1 in der L-Zelle rechts neben dem Subarray. Die Hauptschleife beginnt und endet an dieser Zelle.
quelle