Herausforderung
Bei einem nicht leeren Array von ganzen Zahlen, zB:
[5, 2, 7, 6, 4, 1, 3]
Teilen Sie es zunächst in Arrays auf, in denen kein Element größer als das vorherige ist (dh nicht aufsteigende Arrays):
[5, 2] [7, 6, 4, 1] [3]
Kehren Sie als Nächstes jedes Array um:
[2, 5] [1, 4, 6, 7] [3]
Zum Schluss verketten Sie sie alle miteinander:
[2, 5, 1, 4, 6, 7, 3]
Dies sollte sein, was Ihre Programmausgaben / -funktion zurückgibt. Wiederholen Sie diesen Vorgang so oft, bis das Array vollständig sortiert ist.
Regeln
- Die Ein- und Ausgabe kann durch beliebige Standardmethoden erfolgen und in einem beliebigen vernünftigen Array-Format erfolgen.
- Das Eingabearray ist niemals leer, kann jedoch Negative und / oder Duplikate enthalten.
- Der absolute Wert jeder Ganzzahl ist immer kleiner als 2 31 .
Testfälle
Hoffentlich decken diese alle Randfälle ab:
[1] -> [1]
[1, 1] -> [1, 1]
[1, 2] -> [1, 2]
[2, 1] -> [1, 2]
[2, 3, 1] -> [2, 1, 3]
[2, 1, 3] -> [1, 2, 3]
[2, 1, 2] -> [1, 2, 2]
[2, 1, 1] -> [1, 1, 2]
[3, 1, 1, 2] -> [1, 1, 3, 2]
[3, 2, 1, 2] -> [1, 2, 3, 2]
[3, 1, 2, 2] -> [1, 3, 2, 2]
[1, 3, 2, 2] -> [1, 2, 2, 3]
[1, 0, 5, -234] -> [0, 1, -234, 5]
[1, 0, 1, 0, 1] -> [0, 1, 0, 1, 1]
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
[5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]
[2, 1, 5, 4, 3] -> [1, 2, 3, 4, 5]
[2, 3, 1, 5, 4] -> [2, 1, 3, 4, 5]
[5, 1, 4, 2, 3] -> [1, 5, 2, 4, 3]
[5, 2, 7, 6, 4, 1, 3] -> [2, 5, 1, 4, 6, 7, 3]
[-5, -2, -7, -6, -4, -1, -3] -> [-5, -7, -2, -6, -4, -3, -1]
[14, 5, 3, 8, 15, 7, 4, 19, 12, 0, 2, 18, 6, 11, 13, 1, 17, 16, 10, 9] -> [3, 5, 14, 8, 4, 7, 15, 0, 12, 19, 2, 6, 18, 11, 1, 13, 9, 10, 16, 17]
Wertung
Das ist Code-Golf , also gewinnt der kürzeste Code in Bytes.
code-golf
array-manipulation
sorting
ETHproductions
quelle
quelle
O(n^2)
O(n)
. Tauschen Sie das erste und das letzte Element aus. Tauschen Sie dann das vorletzte und das vorletzte Element usw. aus, wenn Sie den mittleren Anschlag erreicht haben.O(n)
Umkehren ist , aber das Umkehren kann direkt in den Algorithmus eingebaut werden (das ist, was meine JS-Antwort tut). Da jede Iteration jedes Element im Array einmal durchläuft, handelt es sich um eine einzelne IterationO(n)
. (Ich denke ...)Antworten:
JavaScript (ES6), 64 Byte
Rekursion FTW! Der hier verwendete grundlegende Algorithmus besteht darin, den aktuellen nicht aufsteigenden Lauf in einem Array zu verfolgen und ihn "zurückzugeben", wenn ein aufsteigendes Element gefunden wird. Wir tun dies rekursiv und verketten die Ergebnisse fortlaufend, bis wir keine Objekte mehr haben. Durch die Erstellung jedes Laufs in umgekehrter Reihenfolge (
[n,...z]
anstelle von[...z,n]
) können wir das Langwierige kostenlos vermeiden.reverse()
.Testschnipsel
Code-Snippet anzeigen
quelle
[n,...a]
. Was istn
? Ist das nur das erste Element in Ihrem Array?n
ist das erste Element im Array unda
der Rest des Arrays. Weitere Infos finden Sie hier ....a
? Ist das nur so, dass Sie davon profitieren könnenn
? Eine weitere Sache, wenn Sie anrufenf(a,q)
, wirdq
auf den Parameter gesetztz
?f=([n])=>...
würde nur das erste Elementf=([n,a])=>...
erfassen und würde nur das erste inn
und das zweite in erfassena
. Ein anderer Weg, was zu tunf=([n,...a])=>,,,
wäref=a=>(n=a.unshift(),...
.z
ist der zweite Parameter in der Funktion, wennf(a,q)
aufgerufen wird,f
sieht es alsz
. Hoffe das hilft!Python 3 , 63 Bytes
Probieren Sie es online!
quelle
Gelee , 8 Bytes
Probieren Sie es online!
Erläuterung:
quelle
JavaScript (ES6), 70 Byte
Sicher, dies wird bereits von ETHproductions Antwort übertroffen , aber das ist das Beste, was ich bisher ohne Verwendung von Rekursion finden konnte.
Hinweis: Das Initialisieren von beiden
r
undo
von genau demselben Objekt mitr = o = []
kann wie eine gefährliche Idee aussehen. Dies ist aber hier sicher, da bei der ersten Iteration mitr
sofort eine eigene Instanz (die das erste Element von enthälta
) zugewiesen wirdr = [n, ...r]
.Testfälle
Code-Snippet anzeigen
quelle
MATL , 15 Bytes
Die Eingabe ist ein Spaltenvektor mit dem Format
[5; 2; 7; 6; 4; 1; 3]
(Semikolon ist das Zeilentrennzeichen).Probieren Sie es online!
Nehmen Sie die Eingabe
[5; 2; 7; 6; 4; 1; 3]
als Beispiel.Erläuterung
quelle
Mathematica,
3027 Bytes3 Bytes gespart durch @Martin Ender .
Anonyme Funktion. Nimmt eine Liste von Zahlen als Eingabe und gibt eine Liste von Zahlen als Ausgabe zurück.
quelle
Python 2, 100 Bytes
Ein wirklich furchtbares Golf, aber ich wollte meine Lösung posten (man übertrifft einfach nicht Dennis) ...
Test auf repl.it!
Die Eingabe sollte als Python-Listenliteral erfolgen, z
[5, 3, 4, 2, 6, 1]
.Die Grundidee besteht darin, die Python-Slicing-Syntax umfassend zu nutzen, jeden erforderlichen Abschnitt aus dem Array zu entfernen, ihn umzukehren und dem neuen Array hinzuzufügen.
quelle
d,L,x=input(),[],0;d+=...
.Pyke,
118 Bytes ( alte Version )Probieren Sie es hier aus! (Funktioniert mit der neuesten Version)
quelle
Netzhaut , 163 Bytes
Ja, ich weiß, wie schrecklich das ist. Unterstützung von Nullen und Negative war Super Spaß. Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.
Probieren Sie es online aus
Erläuterung:
quelle
05AB1E ,
19181614 BytesMit Luis Mendos Sortiertrick 2 Bytes gespeichert
Probieren Sie es online!
Erläuterung
Beispiel Eingabe
[5, 2, 7, 6, 4, 1, 3]
Vorherige 16-Byte-Lösung
quelle
JavaScript (ECMA 6),
121128125119108 BytesDer Lambda-Ausdruck verwendet einen einzelnen
Array
Parametera
.Vielen Dank an @ETHproductions, die mir geholfen haben, meinen ersten Fehler zu erkennen.
quelle
return(b+","+c).split`,`
, um ein paar Bytes am Ende zu sparen.c.unshift
anstattc.push
die Notwendigkeit zu entfernen, umzukehrenc
. Danach habe ich 94 Bytes .Rubin,
6055 BytesZiemlich genau das, wonach die Herausforderung verlangte. I definiert einen Lambda
s
, die ein Array nimmtx
und Sever (slices) in kleinere Stücke , in denen das folgende Element größer ist als sein würde. Dies gibt einen Enumerator zurück, den wir map aufrufen und die Reihenfolge der Teile umkehren können , bevor wir alles mit flat zusammenführen, wodurch die Elemente in der definierten Reihenfolge zu einem Array verkettet werden .Tests
quelle
Brachylog , 10 Bytes
Probieren Sie es online!
Erläuterung
quelle
c
Versuchen Brachylogs , wenn sie in umgekehrter Reihenfolge ausgeführt werden, zuerst, sie in weniger Listen aufzuteilen?Dyalog APL ,
715 BytesBenötigt
⎕ML←3
, was bei vielen Systemen Standard ist. *∊
eintreten (abflachen)⌽¨
jeweils umgekehrt⍵⊂⍨
Das Argument wird durch Abschneiden partitioniert, wobei jedes entsprechende Element größer ist als sein Vorgänger in1+
eins plus⍵-
das Argument minus⌊/⍵
das kleinste Element des ArgumentsDie alte 7-Byte-Lösung schlägt mit nicht positiven ganzen Zahlen fehl:
Benötigt
⎕ML←3
, was bei vielen Systemen Standard ist. *∊
eintragen (platt machen)⌽¨
jeweils umgekehrt⊂⍨
selbst partitioniert ** Partition (
⊂
) ist eine Funktion, die das rechte Argument abschneidet, wenn das entsprechende linke Argument größer als das vorhergehende ist. (Leider werden nur nicht negative ganze Zahlen akzeptiert, und Null hat eine besondere Bedeutung.) Ab Version 16 ist diese Funktionalität⊂
auf allen Systemen (auch solchen, auf denen⎕ML≠3
) verfügbar , die das Symbol verwenden⊆
.quelle
Haskell, 49 Bytes
Anwendungsbeispiel:
(%[]) [5,2,7,6,4,1,3]
->[2,5,1,4,6,7,3]
.Rekursiver Ansatz. Die Funktion verwendet
%
die Eingabeliste als ersten Parameter und einen Akkumulatorl
, der den bisher nicht aufsteigenden Block verfolgt (in umgekehrter Reihenfolge). Der Basisfall ist erreicht, wenn die Eingabeliste leer ist und das Ergebnis der Akkumulator ist. Wenn die Eingabeliste nicht leer ist und das erste Elementa
nicht in den aktuellen Block (any(<a)l
) passt , geben Sie den Akkumulator zurück und fügen Sie einen rekursiven Aufruf an den Rest der Liste unda
als neuen Akkumulator (l++b%[a]
) an. Anderenfalls rufen Sie den Rest der Liste rekursiv auf und stellen Sie ihn vora
den Akku (b%(a:l)
). Die Hauptfunktion(%[])
ruft%
bei leerem Akku auf.quelle
Retina , 98 Bytes
Die Anzahl der Bytes setzt die Kodierung nach ISO 8859-1 voraus.
Probieren Sie es online!
quelle
R, 64 Bytes
Liest die Eingabe von stdin. Wir teilen die Eingabe in eine Liste von Vektoren auf, für
split()
die eine Faktorvariable erforderlich ist, die die Eingabe gruppiert. Der Faktor ergibt sich aus der kumulativen Summe des logischen Vektors, für den die Differenz positiv ist.Betrachten Sie den Vektor:
Wenn Sie nun den Unterschied nehmen und
F
durch Ausführen voranstelleny=c(F,diff(x)>0)
, wird der folgende logische Vektor erzeugt:Die kumulative Summe
cumsum(y)
ergibt einen Vektor, in dem jede Gruppe durch einen eindeutigen Faktor dargestellt wird, auf den wir mit dersplit
Funktion kombinieren können:quelle
diffinv
anstattcumsum
.Oktave,
7544 BytesBasierend auf der MATL-Antwort von @LuisMendo
Probieren Sie es online!
Vorherige Antwort
Probieren Sie es online!
kehren Sie das Array um
nimm den ersten Unterschied von
f
Finden Sie die Position, an der das nächste Element kleiner als das vorherige Element ist
Die erste Differenz der Positionen gibt die Länge jedes Unterarrays zurück
Verwenden Sie die Länge jedes Unterarrays
mat2cell
, um das Array in eine verschachtelte Liste von Arrays aufzuteilenkehren Sie die verschachtelte Liste um
Reduzieren Sie die verschachtelte Liste
quelle
Pyth - 15 Bytes
Probieren Sie es hier online aus .
quelle
Perl 6 , 59 Bytes
Regex-basierte Lösung.
Weil das
SpartaPerl ist !!m/ /
: Stringifiziere das Eingabearray und vergleiche einen regulären Ausdruck damit.(\-? \d+)
: Passen Sie eine Zahl an und erfassen Sie sie als$0
.<?{ [>=] $0 }>
: Null-Breiten-Zusicherung, die nur dann zutrifft, wenn alle$0
bisher in der aktuellen Teilübereinstimmung erfassten in nicht aufsteigender Reihenfolge sind.([ ] +)+
: Wiederholen Sie die letzten beiden Schritte so oft wie möglich, andernfalls starten Sie eine neue Teilübereinstimmung.map , [0]
: Iteriere über die Submatches.|+«*.[0].reverse
: Nehmen Sie für jeden Wert die Liste mit den übereinstimmenden Werten$0
, kehren Sie sie um, setzen Sie die Werte in Zahlen um (+«
) und fügen Sie sie in die äußere Liste ein (|
).Perl 6 , 63 Bytes
Lösung für die Verarbeitung rekursiver Listen.
Mühsamer als ich gehofft hatte.
Obwohl die Sprache viele praktische integrierte Funktionen hat, scheint es keine für die Listenpartitionierung zu geben (z. B. Ruby's
slice_when
oder Haskell'stakeWhile
).quelle
Gestapelt , nicht konkurrierend, 34 Bytes
Entwickelt diese Sprache immer weiter.
Das Argument liegt auf TOS. Probieren Sie es hier aus!
chunkby
Nimmt eine Funktion und sammelt Arrays zusammenhängender Daten, die die Funktion erfüllen. Die Funktion ist dann:Dies ergibt ein streng abnehmendes Array.
$revmap
ist im Grunde[rev]map
und kehrt jedes Element.flat
Zum Schluss wird das Array abgeflacht.Ein bisschen Spaß beim Sortieren des Arrays:
Diese Ausgabe (zum Beispiel):
quelle
Python,
151139 Bytes12 Bytes gespart dank @ Flp.Tkc!
Nirgendwo in der Nähe von @ Flp.Tkc, geschweige denn ...
quelle
+= data,
implizit ein Tupel erstellt, das dann mit der Liste verkettet wird, wobei die Daten als letztes Element in der Liste hinzugefügt werden. In diesem Zusammenhang machen Sier+=l[i:j+1][::-1],
Python 2, 74 Bytes
Eingabe in
a
, Ausgabe inc
quelle
Python 3, 191 Bytes
Ich bin mir nicht sicher, ob die Verwendung der
sorted
Funktion zum Überprüfen hier zulässig ist, aber ich konnte mir keinen guten Grund dafür vorstellen, und meine Byteanzahl wurde um ~ 30 Bytes gesenkt.quelle
Clojure, 105 Bytes
Trennwände in Paaren auf fortlaufende Nummern, setzt
true
oderfalse
zwischen ihnen, Partitionennot
zutrue
und Zahlen werdenfalse
undfalse
true
kehrt Partitionen und numerische Werte hält.quelle