Der Sortieralgorithmus sieht folgendermaßen aus:
Wenn die Liste nicht sortiert ist, fangen Sie die Hälfte aller Elemente (entfernen Sie sie aus der Liste). Fahren Sie fort, bis die Liste sortiert ist oder nur noch ein Element vorhanden ist (standardmäßig sortiert). Dieser Sortieralgorithmus kann je nach Implementierung unterschiedliche Ergebnisse liefern.
Über das Verfahren zum Entfernen von Elementen entscheidet die Implementierung. Die Liste sollte jedoch nach einem Durchgang des Verfahrens zum Entfernen von Elementen halb so lang sein wie zuvor. Ihr Algorithmus kann entscheiden, entweder die erste Hälfte oder die Liste, die letzte Hälfte der Liste, alle ungeraden Elemente, alle geraden Elemente nacheinander zu entfernen, bis die Liste halb so lang ist, oder alle nicht erwähnten.
Die Eingabeliste kann eine beliebige Anzahl von Elementen enthalten (innerhalb des vorgegebenen Rahmens, sagen wir bis zu 1000 Elemente), nicht nur perfekt unterteilbare Listen mit 2 ^ n Elementen. Sie müssen entweder (n + 1) / 2 oder (n-1) / 2 Elemente entfernen, wenn die Liste ungerade ist, entweder fest codiert oder während der Laufzeit zufällig entschieden wird. Überlegen Sie selbst: Was würde Thanos tun, wenn das Universum eine ungerade Menge an Lebewesen enthalten würde?
Die Liste wird sortiert, wenn kein Element kleiner als ein vorheriges Element ist. Duplikate können in der Eingabe und in der Ausgabe auftreten.
Ihr Programm sollte ein Array von Ganzzahlen (über stdin oder als Parameter, entweder einzelne Elemente oder einen Array-Parameter) aufnehmen und das sortierte Array zurückgeben (oder auf stdout ausgeben).
Beispiele:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5]
könnte zu unterschiedlichen Ergebnissen führen:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
oder:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
oder:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
oder:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
[9, 1, 1, 1, 1]
. Mein eigener Algorithmus ist bei diesem Eingang fehlgeschlagenAntworten:
R , 41 Bytes
Probieren Sie es online!
quelle
is.unsorted
Stattdessenany(...)
wären es auch 41 Bytes.Python 3 ,
384239 BytesProbieren Sie es online!
-3 bytes
danke an @JoKing und @Quuxplusonequelle
!= sorted(t)
muss> sorted(t)
.Python 2 , 39 Bytes
Probieren Sie es online!
quelle
Brachylog (v2), 6 Bytes
Probieren Sie es online!
Dies ist eine Funktionsübermittlung. Eingabe von links, Ausgabe nach rechts wie gewohnt. (Der TIO-Link verwendet ein Befehlszeilenargument, das die Funktion automatisch in ein vollständiges Programm einbindet, damit Sie es in Aktion sehen können.)
Erläuterung
Bonusrunde
Probieren Sie es online!
Der Schnappschuss soll zufällig sein, nicht wahr? Hier ist eine Version des Programms, die die überlebenden Elemente nach dem Zufallsprinzip auswählt (wobei sichergestellt wird, dass die Hälfte bei jeder Runde überlebt).
Dies wäre eher kürzer , wenn wir die Elemente neu anordnen könnte, aber whyever möchte ein Sortieralgorithmus zu tun , dass ?
quelle
Perl 6 , 30 Bytes
Probieren Sie es online!
Rekursive Funktion, die die zweite Hälfte der Liste entfernt, bis die Liste sortiert ist.
Erläuterung:
quelle
C # (Visual C # Interactive Compiler) , 76 Byte
Probieren Sie es online!
quelle
Java 10,
10697 Bytes-9 Bytes dank @ OlivierGrégoire .
Probieren Sie es online aus.
Erläuterung:
quelle
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}
ist mit Streams kürzer, aber ich konnte nicht herausfinden, wie derjava.lang.IllegalStateException: stream has already been operated upon or closed
Fehler nach der Rückgabe des Streamsreduce
es sich um eine Terminaloperation handelt, die den Stream schließt. Sie werden niemalsreduce
zweimal im selben Stream telefonieren können . Sie können jedoch einen neuen Stream erstellen.Wolfram Language (Mathematica) , 30 Byte
Probieren Sie es online!
@Doorknob hat 12 Bytes gespeichert
quelle
x[[;;;;2]]
).OrderedQ
, aber es könnte nicht funktionierenOrderedQ
in meinem ersten Ansatz verwendet (siehe Änderungen)JavaScript (ES6),
4948 Bytes1 Byte dank @tsh gespeichert
Entfernt jedes 2. Element.
Probieren Sie es online!
quelle
p++&1
->a^=1
Ruby , 37 Bytes
Probieren Sie es online!
quelle
05AB1E ,
87 Bytes-1 Byte dank @Emigna .
Probieren Sie es online aus oder überprüfen Sie einige weitere Testfälle (oder überprüfen Sie diese Testfälle schrittweise für jede Iteration ).
7 Bytes Alternative von @Grimy :
Probieren Sie es online aus oder überprüfen Sie einige weitere Testfälle (oder überprüfen Sie diese Testfälle schrittweise für jede Iteration ).
Erläuterung:
quelle
ι
stattdessen jede andere Elementstrategie verwenden,2ä
wenn Sie zu einer Beibehaltungsstrategie wechseln .ΔÐ{Ê>äн
TI-BASIC (TI-84),
47424544 Byte-1 Byte Danke an @SolomonUcko!
Eingabeliste ist in
Ans
.Die Ausgabe erfolgt in
Ans
und wird implizit ausgedruckt.Erläuterung:
Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.
quelle
not(min(L1=Ans
mitmax(L1≠Ans
einem Byte zu speichern.Gelee , 7 Bytes
Probieren Sie es online!
quelle
Haskell ,
5755 Bytes (nur dank ASCII)Probieren Sie es online!
Ursprünglicher Code:
Probieren Sie es online!
Ungolfed:
quelle
Oktave , 49 Bytes
Probieren Sie es online! Dies war eine Reise, auf der mehr Langeweile besser ist. Beachten Sie die zwei viel interessanteren Einträge unten:
50 Bytes
Probieren Sie es online! Anstelle der uninteressanten Imperativlösung können wir für nur ein zusätzliches Byte eine rekursive Lösung durchführen.
53 Bytes
Probieren Sie es online! Ja. Eine rekursive anonyme Funktion, dank @ ceilingcat die glänzende Antwort auf meine Tipps Frage. Eine anonyme Funktion, die eine rekursive anonyme Funktion zurückgibt, indem sie sich in ihrer Argumentliste definiert. Ich mag anonyme Funktionen. Mmmmm.
quelle
MATL , 11 Bytes
Probieren Sie es online!
Dies funktioniert, indem jeder zweite Gegenstand entfernt wird.
Erläuterung
quelle
Japt , 10 Bytes
Versuch es
quelle
Java (JDK) , 102 Byte
Da es bereits eine C # -Antwort gibt, habe ich beschlossen, mich an einer Java-Antwort zu versuchen.
Probieren Sie es online!
quelle
Kristall , 58 Bytes
Mit
Array#sort
( 58 Bytes ):Probieren Sie es online!
Ohne
Array#sort
( 101 Bytes ):Probieren Sie es online!
quelle
Schale ,
65 Bytes1 Byte gespart dank Zgarb
Probieren Sie es online!
Erläuterung
quelle
Ċ2
anstelle von(←½
, um ein Byte zu speichern.Gaia ,
98 BytesProbieren Sie es online!
Erläuterung:
quelle
Julia 1.0 , 30 Bytes
Probieren Sie es online!
Nimmt jedes zweite Element des Arrays, wenn es nicht sortiert ist.
quelle
-
für 20 Byte. auch zählen wir fast immer keine zeichen: | also wäre es schön, wenn das aus dem Header entfernt würdeC ++ (gcc) , 103 Bytes
Ich kann nichts dazu sagen, aber ich habe die Version von movatica verbessert, indem ich die Includes reduziert und auto verwendet habe.
-2 Bytes: ceilingcat
-2 Bytes: Nur ASCII
Probieren Sie es online!
quelle
l.size()/2
?(n+1)/2
oder(n-1)/2
sind beide gültig. hmm ....VDM-SL , 99 Bytes
Nie zuvor in vdm eingereicht, daher sprachspezifisch nicht sicher. Ich habe also eine Funktionsdefinition übergeben, die a annimmt
seq of int
und a zurückgibtseq of int
Ein vollständiges Programm könnte so aussehen:
quelle
Pyth, 10 Bytes
Probieren Sie es hier online aus . Dadurch wird die zweite Hälfte bei jeder Iteration entfernt und abgerundet. Um die erste Hälfte abzurunden, ändern Sie die
h
aufe
.quelle
hc
durch%
. Auf diese Weise können Sie auch dieZ
nachfolgende Lambda-Variable löschen und von Pyth implizit füllen lassen, sodass insgesamt 2 Bytes gespeichert werden.C ++ (gcc) ,
139137116 Bytes-2 Bytes Danke an Ceilingcat, -21 Bytes Danke an PeterZuger
Ändern Sie die Größe des Vektors auf die erste Hälfte, bis er sortiert ist.
Probieren Sie es online!
quelle
include
K (OK) ,
2220 BytesLösung:
Probieren Sie es online!
Durchlaufen Sie die Eingabe, bis sie sortiert ist. Wenn sie nicht sortiert ist, nehmen Sie zuerst n / 2 Elemente.
Bearbeitungen:
quelle
(.5*#x)#x
->*2 0N#x
2 0N
aber angenommen, es würde länger dauern (ohne zu testen), danke!Julia 1.0 , 33 Bytes
Probieren Sie es online!
quelle
Retina , 38 Bytes
Probieren Sie es online! Nimmt durch Kommas getrennte Zahlen. Erläuterung:
In Unary konvertieren.
Wiederholen, während die Liste nicht sortiert ist ...
... lösche jedes gerade Element.
In Dezimalzahl konvertieren.
quelle
C (gcc) , 66 Bytes
Fängt die zweite Hälfte der Liste bei jeder Iteration ab (
n/2+1
Elemente, wenn die Länge ungerade ist).Probieren Sie es online!
Übernimmt die Eingabe als Zeiger auf den Anfang eines Arrays
int
gefolgt von seiner Länge. Ausgabe durch Rückgabe der neuen Länge des Arrays (direkte Sortierung).Ungolfed-Version:
quelle
~i+n
stattdessen vori<n-1