Eine klassische Sortiercode-Golf-Frage

11

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 ndie 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.


quelle
Einige Set-Funktionen wie das intersectautomatische Sortieren des Arrays. Ich denke, Sie wollen das auch ausschließen. Wie wäre es unique(Duplikate entfernen, Ergebnis sortieren)?
Luis Mendo
@ DonMuesli mache ich .. Ich denke, intersectkommt unter "ähnlich", wenn es automatisch das Array sortiert. Wenn Sie Duplikate entfernen, erhalten Sie die falsche Ausgabe.
Über falsche Eingaben, überlasse das mir :-) Könnte dann "Duplikate entfernen und sortieren" verwendet werden?
Luis Mendo
3
Nitpick: 0 ist keine positive ganze Zahl. (Unter Eingabe )
Becher
1
Ich mag es, wenn sich die Frage, sobald die Frage etwas mit der Leistung zu tun hat, von den Golfsprachen entfernt, obwohl dies immer noch Code-Golf ist und die kürzeste Lösung immer noch gewinnt.
Cyoce

Antworten:

8

Haskell, 87 80 89

s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

Dies 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ührt
jPaare in einer Liste von Listen
rzusammen führt eine vollständige Liste von Listen zusammen
sist 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.

stolzer haskeller
quelle
1
@Lembik Wenn Sie das Programm testen und Haskell nicht installieren möchten, können Sie ideone verwenden und eine Zeile wie hinzufügen main = print (s [5,3,6,8]), mit der das Ergebnis der Sortierung hauptsächlich gedruckt wird.
stolzer Haskeller
Ich denke, Sie brauchen nicht []%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 dies s%[]erfolgreich ist.
Nimi
Du bist der Sieger! Die einzige Antwort mit weniger Bytes wurde nicht in O (n log n) ausgeführt.
@Lembik Richtig, ich habe vergessen, dass die Jelly-Antwort nicht übereinstimmte.
stolzer Haskeller
1
Es ist jetzt, wie es scheint :)
5

JavaScript (ES6), 195 193 191 189 188 186 183 182 179 174 172 Bytes

Dies 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.

S=l=>{e=l.length
W=(a,b)=>[l[a],l[b]]=[l[b],l[a]]
D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)}
for(s=e>>1;s;)D(--s)
for(;--e;D(0))W(0,e)}

Test (Firefox)

PurkkaKoodari
quelle
Ich hätte gerne eine Heapsort-Antwort geschrieben, aber mit Haskell funktioniert das nicht wirklich gut. Mein nächster Versuch wäre JS, aber Sie haben es geschafft. Vielleicht mache ich das trotzdem. Idk
stolzer Haskeller
@proudhaskeller Ah ja .. ich habe gerade stackoverflow.com/a/2186785/2179021 nachgeschlagen .
3

Python3, 132 Bytes

def S(l):
 if len(l)<2:return l
 a,b,o=S(l[::2]),S(l[1::2]),[]
 while a and b:o.append([a,b][a[-1]<b[-1]].pop())
 return a+b+o[::-1]

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

def m(a,b):
 while a+b:yield[a,b][a<b].pop(0)
S=lambda l:l[1:]and list(m(S(l[::2]),S(l[1::2])))or l

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.

orlp
quelle
Danke dafür. Ich meinte definitiv, dass der Algorithmus und die Implementierung O (n log n) sein sollten.
Dies bedeutet, dass die 132-Version in Ordnung ist, die 99-Byte-Version jedoch nicht den Anforderungen entspricht.
2

Julia, 166 Bytes

m(a,b,j=1,k=1,L=endof)=[(j<=L(a)&&k<=L(b)&&a[j]<b[k])||k>L(b)?a[(j+=1)-1]:b[(k+=1)-1]for i=1:L([a;b])]
M(x,n=endof(x))=n>1?m(M(x[1:(q=ceil(Int,n÷2))]),M(x[q+1:n])):x

Die primäre Funktion wird aufgerufen Mund ruft eine Hilfsfunktion auf m. Es verwendet die Zusammenführungssortierung , deren Worst-Case-Komplexität O ( n log n ) ist.

Anwendungsbeispiel:

x = [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
println(M(x))              # prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
println(M(x) == sort(x))   # prints true

Ungolfed:

function m(a, b, i=1, k=1, L=endof)
    return [(j <= L(a) && k <= L(b) && a[j] < b[k]) || k > L(b) ?
            a[(j+=1)-1] : b[(k+=1)-1] for i = 1:L([a; b])]
end

function M(x, n=endof(x))
    q = ceil(Int, n÷2)
    return n > 1 ? m(M(x[1:q]), M([q+1:n])) : x
end
Alex A.
quelle
Schön, Julia hier zu sehen. Jetzt brauchen wir auch Nim und Rost :)
1
@Lembik Ich denke, Sp3000 und Doorknob sind unsere ansässigen Nim- bzw. Rust-Experten. Hoffentlich machen sie auch mit. ;)
Alex A.
2

R, 181 Bytes, Mergesort

L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}

Eingedrückt, mit Zeilenumbrüchen:

L=length
s=function(S)
    if(L(S)<2){
        S
    }else{
        h=1:(L(S)/2)
        A=s(S[h])
        B=s(S[-h])
        Z=c()
        if(A[L(A)]>B[1])
#Merge helper function incorporated from here ...
            while(L(A)&L(B))
                if(A[1]<B[1]){
                    Z=c(Z,A[1])
                    A=A[-1]
                }else{
                    Z=c(Z,B[1])
                    B=B[-1]
                }
#...to here. Following line both finishes merge function and handles 'else' case:
        c(Z,A,B)
    }

Testfälle:

> L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}
> s(c(2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269))
 [1]  667269 1925225 2276714 2397725 3088926 3304534 4274324 4487711 7806949 8337622
> s(c(2, 2, 1, 9, 3, 7, 4, 1, 6, 7))
 [1] 1 1 2 2 3 4 6 7 7 9
> s(c(72, 59, 95, 68, 84))
 [1] 59 68 72 84 95
> s(c(9, 8, 3, 2, 4, 6, 5, 1, 7, 0))
 [1] 0 1 2 3 4 5 6 7 8 9
Planapus
quelle
2

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):

object G{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
}

Eigenständige Anwendung (315 Byte):

object G extends App{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
println(s(args(0).split(",").map(_.toInt).toStream).toList)
}

Verwendung:

Funktion: G.s(List(**[Paste your array here]**).toStream).toList

Anwendung: sbt "run **[Paste your array here]**"

Beispiel Eingabe:

scala> G.s(List(10,2,120,1,8,3).toStream).toList

(OR)

$ sbt "run 5423,123,24,563,65,2,3,764"

Ausgabe:

res1: Liste [Int] = Liste (1, 2, 3, 8, 10, 120)

ODER

Liste (2, 3, 24, 65, 123, 563, 764, 5423)

Einschränkungen und Überlegungen:

  • Benötigt Scalaz (sehr häufige Bibliothek, hier nicht zum Sortieren verwendet)
  • Ist 100% funktionsfähig (nichts veränderlich!)

Zuschreibung:

Ruslan
quelle
2

Gelee, 29 Bytes, Sortierung zusammenführen

Wie bei der Python-Antwort von orlp wird dies list.pop(0)unter der Haube verwendet O(n), aber die Implementierung erfolgt formal O(n log n).

ṛð>ṛḢð¡Ḣ;ñ
ç;ȧ?
s2Z߀ç/µL>1µ¡

Probieren Sie es hier aus.

Erläuterung

               Define f(x, y):    (merge helper)
                 Implicitly store x in α.
ṛ    ð¡          Replace it with y this many times:
 ð>ṛḢ              (x > y)[0].
       Ḣ         Pop the first element off that list (either x or y).
        ;ñ       Append it to g(x, y).

               Define g(x, y):    (merge)
  ȧ?             If x and y are non-empty:
ç                  Return f(x, y)
                 Else:
 ;                 Return concat(x, y).

               Define main(z):    (merge sort)
       µL>1µ¡    Repeat (len(z) > 1) times:
s2                 Split z in chunks of length two.   [[9, 7], [1, 3], [2, 8]]
  Z                Transpose the resulting array.     [[9, 1, 2], [7, 3, 8]]
   ߀              Apply main() recursively to each.  [[1, 2, 9], [3, 7, 8]]
     ç/            Apply g on these two elements.     [1, 2, 3, 7, 8, 9]
Lynn
quelle
Würde es Ihnen etwas ausmachen, eine Erklärung hinzuzufügen?
Es gibt viel zu erklären :) Lassen Sie mich sehen, ob ich die letzte Linie ein bisschen mehr Golf spielen kann
Lynn
Wenn Sie sagen, dass die Implementierung O (n log n) ist, aber list.pop (0) unter der Haube verwendet, was O (n) ist, bin ich verwirrt. Was meinen Sie?
Ich meine genau das, was orlp in seiner Antwort geschrieben hat: Dies ist nicht O (n log n), weil .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.
Lynn
Jelly ist in Python implementiert und wird als implementiert .pop(0).
Lynn
1

Ruby, 167 Bytes

Golfed Merge Sort Algorithmus, der O (n log n) im ungünstigsten Fall hat

f=->x{m=->a,b{i,j,l,y,z=0,0,[],a.size,b.size
while i<y&&j<z
c=a[i]<b[j]
l<<(c ?a[i]:b[j])
c ?i+=1:j+=1
end
l+=a[i,y]+b[j,z]}
l=x.size
l>1?m[f[x[0,l/2]],f[x[l/2,l]]]:x}

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]]

Wert Tinte
quelle
Danke dafür! Können Sie zeigen, dass es auch funktioniert?
1
Ich habe einen Link hinzugefügt, damit Sie ihn testen können.
Value Ink
1

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.

if $0==__FILE__;v=open(ARGV[0]).readlines.map{|e|e.to_i}.map{|e|[e]};v=v.each_slice(2).map{|e|a,b,r=e[0],e[1],[];while true;if(!a)||a.empty?;r+=b;break;end;if(!b)||b.empty?;r+=a;break;end;r<<(a[0]<b[0]?a:b).shift;end;r}while v.size>1;open(ARGV[1],"w"){|f|f.puts(v[0].join("\n"))if !v.empty?};end
jose_castro_arnaud
quelle
Wenn dies Ihren Code verkürzen würde, sollten Sie in Betracht ziehen, den Code an eine Funktion anzupassen, die ein Array als Eingabe erhält und die sortierte Sequenz zurückgibt. Es scheint, als würden Sie viele Bytes loswerden.
stolzer Haskeller
Wenn Sie es als vollständiges Programm anstelle einer Funktion behalten möchten, kann ich vorschlagen, STDIN und STDOUT als Eingabe / Ausgabe zu verwenden? $stdin.readlinesist schon weniger Bytes als open(ARGV[0]).readlines, gleich mit putsoveropen(ARGV[1],"w"){|f|f.puts
Value Ink
2
Und solche Sachen 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 .
Daniero