Dies ist eine Code-Golf-Frage.
Eingang
Eine Liste nicht negativer Ganzzahlen in einem beliebigen Format ist am bequemsten.
Ausgabe
Dieselbe Liste in sortierter Reihenfolge in dem Format, das am bequemsten ist.
Beschränkung
- Ihr Code muss im schlimmsten Fall in O (n log n) ausgeführt werden, wenn
n
die Anzahl der Ganzzahlen in der Eingabe angegeben ist. Dies bedeutet, dass beispielsweise eine randomisierte Quicksortierung nicht verfügbar ist. Es stehen jedoch viele andere Optionen zur Auswahl. - Verwenden Sie keine Sortierbibliothek / Funktion / Ähnliches. Verwenden Sie auch nichts, was den größten Teil der Sortierarbeit für Sie erledigt, wie eine Heap-Bibliothek. Was auch immer Sie implementieren, implementieren Sie es grundsätzlich von Grund auf neu.
Sie können eine Funktion definieren, wenn Sie möchten, aber dann zeigen Sie bitte ein Beispiel dafür in einem vollständigen Programm, das tatsächlich funktioniert. Es sollte in allen folgenden Testfällen erfolgreich und schnell ausgeführt werden.
Testfälle
In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]
In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]
In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324, 667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]
Deine Antworten
Bitte geben Sie den von Ihnen implementierten Sortieralgorithmus und die Länge Ihrer Lösung im Titel Ihrer Antwort an.
O (n log n) Zeitsortieralgorithmen
Es gibt viele O (n log n) Zeitalgorithmen. Diese Tabelle enthält eine Liste einiger davon.
intersect
automatische Sortieren des Arrays. Ich denke, Sie wollen das auch ausschließen. Wie wäre esunique
(Duplikate entfernen, Ergebnis sortieren)?intersect
kommt unter "ähnlich", wenn es automatisch das Array sortiert. Wenn Sie Duplikate entfernen, erhalten Sie die falsche Ausgabe.Antworten:
Haskell,
878089Dies ist eine Zusammenführungssortierung, die von unten nach oben implementiert wird. Zuerst packen wir jedes Element in eine eigene Liste und führen sie dann zwei mal zwei und dann zwei mal zwei zusammen, bis wir eine Liste haben.
(%)
ist die Zusammenführungsfunktion führtj
Paare in einer Liste von Listenr
zusammen führt eine vollständige Liste von Listen zusammens
ist die Sortierfunktion.Verwendung: Führen Sie einen Dolmetscher aus und geben Sie ein
s [3,5,2,6,7]
.Bearbeiten: Die Art und Weise, wie ich Dinge zusammengeführt habe, war nicht die richtige Reihenfolge. Um dies zu beheben, benötigte ich 9 weitere Zeichen.
quelle
main = print (s [5,3,6,8])
, mit der das Ergebnis der Sortierung hauptsächlich gedruckt wird.[]%s=s
, denn wenn das erste Element ist[]
,(x:a)
schlägt die Übereinstimmung fehl und der letzte Fall dreht die Elemente um, so dass diess%[]
erfolgreich ist.JavaScript (ES6),
195193191189188186183182179174172 BytesDies ist eine Heapsort-Implementierung. Ich erwarte, dass jemand einen kürzeren Mergesort einbringt, aber ich mag diesen: P.
Update: R Mergesort geschlagen. Rubin als nächstes: D.
Test (Firefox)
Code-Snippet anzeigen
quelle
Python3, 132 Bytes
Einfache Zusammenführung. Es wurden viele Bytes ausgegeben, um sicherzustellen, dass dies tatsächlich in O (n log n) ausgeführt wird. Wenn nur der Algorithmus , aber nicht die Implementierung O (n log n) sein muss, kann dies verkürzt werden:
Python3, 99 Bytes
Dies ist nicht O (n log n), da
.pop(0)
O (n) ist, wodurch die Zusammenführungsfunktion O (n ^ 2) wird. Dies ist jedoch ziemlich künstlich, wie.pop(0)
es leicht O (1) hätte sein können.quelle
Julia, 166 Bytes
Die primäre Funktion wird aufgerufen
M
und ruft eine Hilfsfunktion aufm
. Es verwendet die Zusammenführungssortierung , deren Worst-Case-Komplexität O ( n log n ) ist.Anwendungsbeispiel:
Ungolfed:
quelle
R, 181 Bytes, Mergesort
Eingedrückt, mit Zeilenumbrüchen:
Testfälle:
quelle
Scala, 243-Byte-Funktion (315-Byte-Standalone-App), Mergesort
Diese Antwort soll eine Funktion sein, kann aber zu einer eigenständigen Anwendung erweitert werden.
Nur Funktion (243 Byte):
Eigenständige Anwendung (315 Byte):
Verwendung:
Beispiel Eingabe:
Ausgabe:
Einschränkungen und Überlegungen:
Zuschreibung:
m()
die von dieser Antwort inspirierte Implementierung ( Funktion) zusammen: /codereview//a/21590/28856quelle
Gelee, 29 Bytes, Sortierung zusammenführen
Wie bei der Python-Antwort von orlp wird dies
list.pop(0)
unter der Haube verwendetO(n)
, aber die Implementierung erfolgt formalO(n log n)
.Probieren Sie es hier aus.
Erläuterung
quelle
.pop(0)
es O (n) ist, wodurch die Zusammenführungsfunktion O (n ^ 2) wird. Dies ist jedoch ziemlich künstlich, wie.pop(0)
es leicht O (1) hätte sein können.Ḣ
implementiert und wird als implementiert.pop(0)
.Ruby, 167 Bytes
Golfed Merge Sort Algorithmus, der O (n log n) im ungünstigsten Fall hat
Testen Sie es hier!
Kopieren Sie zum Testen den Code, fügen Sie ihn in das Fenster ein und fügen Sie ihn
puts f[x]
unten hinzu, wobei x ein Array mit der Eingabe ist. (Stellen Sie sicher, dass Sie Ruby als Sprache auswählen.) Zum Beispiel:puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]
quelle
Ruby, 297 Bytes
Zusammenführen, sortieren. Vollständiges Programm anstelle einer Funktion. Erfordert zur Laufzeit zwei Argumente: Eingabedatei und Ausgabedatei mit jeweils einem Element pro Zeile.
quelle
$stdin.readlines
ist schon weniger Bytes alsopen(ARGV[0]).readlines
, gleich mitputs
overopen(ARGV[1],"w"){|f|f.puts
if $0==__FILE__
sind in einem Code-Golf wirklich unnötig. Sie können auch jede Bedingung durch;
eine neue Zeile ersetzen - es ist die gleiche Anzahl von Bytes und (wahrscheinlich) entfernt die horizontale Schriftrolle des Codes. Außerdem empfehle ich Ihnen, Tipps zum Golfen in Ruby zu lesen .