Die Herausforderung

Es ist wirklich ganz einfach, eine Liste von Zahlen zu sortieren.

Einzelheiten

Sie müssen eine Liste mit Zahlen in aufsteigender Reihenfolge sortieren, ohne die integrierten Sortierfunktionen / libraries / etc (dh list.sort()in Python) zu verwenden.

Die Ein- / Ausgabe kann in jeder von Ihnen gewählten Methode erfolgen, sofern dies für den Menschen lesbar ist.

Standardlücken sind wie immer verboten.

Kürzester Code in Bytes gewinnt.

Sie müssen erklären / auflisten, welche Sortiermethode Sie verwendet haben (Blase, Einfügung, Auswahl usw.)

Die Eingabe enthält keine Duplikate.

Sample Input / Output

Eingang: 99,-2,53,4,67,55,23,43,88,-22,36,45

Ausgabe: -22,-2,4,23,36,43,45,53,55,67,88,99

Hinweis: Nahezu genau das Gegenteil von Liste mit Zahlen sortieren

05AB1E , 2 Bytes

Code:

ϧ

Gleicher Algorithmus wie die Jelly-Antwort . Berechnet alle Permutationen der Eingabe und gibt die kleinste aus.

Probieren Sie es online!

Eine effizientere Methode ist:

E[ß,Ž

Führt eine Auswahlsortierung durch . Verwendet die CP-1252- Codierung.

Probieren Sie es online!

Gelee, 3 Bytes

Œ!Ṃ

Dies generiert alle Permutationen der Eingabeliste und wählt dann die lexographisch kleinste Permutation aus. Sehr effizient

Dank an @Adnan, der selbständig die gleiche Idee hatte.

Probieren Sie es online!

Gelee, 4 Bytes

ṂrṀf

Dadurch wird der Bereich vom Minimum der Liste bis zum Maximum der Liste erstellt. Anschließend werden die in der ursprünglichen Liste nicht vorhandenen Bereichselemente verworfen. Dies ist technisch eine Eimersorte mit sehr kleinen Eimern. Mir ist kein Name für diese bestimmte Variante bekannt.

Probieren Sie es online!

Wie es funktioniert

ṂrṀf  Main link. Argument: A (list/comma-separated string)

Ṃ     Compute the minimum of A.
  Ṁ   Compute the maximum of A.
 r    Yield the inclusive range from the minimum to the maximum.
   f  Filter the range by presence in A.

Python, 46 45 Bytes

lambda l:[l.pop(l.index(min(l)))for _ in 1*l]

Einfache Auswahlsortierung.

Brachylog , 12 7 Bytes

p.'(s>)

Dies verwendet die Permutationssorte, die offensichtlich schrecklich ist, aber hey, sie ist kürzer als Pyth!

Erläuterung

p.       Unifies the output with a permutation of the input
  '(  )  True if what's inside the parentheses cannot be proven, else backtrack and
         try with another permutation of the input.
    s    Take an ordered subset from the output
     >   True if the first element is bigger than the second (hence not sorted)
         We don't need to check that the subset is 2 elements long because > will be false
         for inputs that are not 2 elements long anyway

Haskell, 38 Bytes

h%t|(a,b)<-span(<h)t=a++h:b
foldr(%)[]

Die Binärfunktion %fügt ein neues Element hin eine sortierte Liste ein, tindem sie es tin ein Präfix avon Elementen <hund ein Suffix bvon Elementen unterteilt >hund hdazwischen einfügt.

Die Operation erstellt foldr(%)[]dann eine sortierte Liste aus leeren Elementen, indem wiederholt Elemente aus der Eingabeliste eingefügt werden.

Dies ist ein Byte kürzer als die direkte rekursive Implementierung

f(h:t)|(a,b)<-span(<h)$f t=a++h:b
f x=x

Eine andere Strategie für 41 Bytes:

f[]=[]
f l|x<-minimum l=x:f(filter(/=x)l)

JavaScript (ES6), 51 Byte

a=>a.map(_=>m=Math.min(...a.filter(e=>e>m)),m=-1/0)

Jede Schleife findet die kleinste Nummer, die noch nicht gefunden wurde.

Python 2, 34 Bytes

def f(s):m=min(s);print m;f(s-{m})

Nimmt die Eingabe als Gruppe, druckt die Elemente in aufsteigender Reihenfolge und endet mit einem Fehler.

Eine saubere Beendigung kann in 41 Bytes erfolgen:

def f(s):
 if s:m=min(s);print m;f(s-{m})

oder

l=input()
while l:m=min(l);print m;l-={m}

Die Eingabe kann als Liste für 39 Bytes oder 38 Bytes in Python 3.5 erfolgen:

def f(l):m=min(l);print m;f(set(l)-{m})
def f(l):m=min(l);print(m);f({*l}-{m})

Haskell, 42 41 38 Bytes

f u=filter(`elem`u)[(minBound::Int)..]

Durchläuft alle Ganzzahlen (64-Bit mit Vorzeichen auf meinem Computer) und behält diejenigen bei, die sich in befinden u. Natürlich ist es nicht in angemessener Zeit fertig.

Die vorherige Version durchlief [minimum u..maximum u]die gleiche Worst-Case-Laufzeit.

Edit: @xnor hat ein Byte gespeichert. Vielen Dank!

Oracle SQL 11.2, 205 Byte

WITH s AS(SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))),v(p,f)AS(SELECT e,e FROM s UNION ALL SELECT p||','||e,e FROM v,s WHERE e+0>f)SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1);         

Nicht golfen

WITH 
s AS  -- Split the string using ',' as separator
(     -- ||'' cast the xml type to varchar
  SELECT COLUMN_VALUE||''e FROM XMLTABLE(('"'||REPLACE(:1,',','","')||'"'))
),  
v(p,f) AS  -- Recursive view : p = sorted string, f last number added
(
  SELECT e,e FROM s -- use each number as seed
  UNION ALL         -- only add a number if it is > the last added
  SELECT p||','||e,e FROM v,s WHERE e+0>f  -- +0 is needed to compare int and not strings
)  
-- The valid string has the same length as the input
SELECT p FROM v WHERE LENGTH(p)=LENGTH(:1)          

Was für eine Art Methode es ist, ich habe keine Ahnung, ORDER BYstellte sicher , dass ich sie vergessen habe.

x86-16-Maschinencode (BubbleSort int8_t), 20 bis 19 Byte

x86-64 / 32-Maschinencode (JumpDownSort) 21 19 Bytes

Änderungsprotokoll:

• Vielen Dank an @ ped7g für die lodsb/ cmp [si],al-Idee und das Zusammenfügen mit einem Zeigerinkrement / -Reset, das ich mir angesehen habe. Wir brauchen nicht al/ ahlassen uns fast den gleichen Code für größere ganze Zahlen verwenden.

• Neuer (aber verwandter) Algorithmus, viele Implementierungsänderungen: Bubbly SelectionSort ermöglicht eine kleinere x86-64-Implementierung für Bytes oder Dwords; Break-Even auf x86-16 (Bytes oder Wörter). Vermeidet auch den Fehler bei Größe = 1, den mein BubbleSort hat. Siehe unten.

• Es stellt sich heraus, dass meine Bubbly Selection Sort mit Swaps jedes Mal, wenn Sie eine neue Min finden, bereits ein bekannter Algorithmus ist, JumpDown Sort. Es wird in Bubble Sort: Eine archäologische algorithmische Analyse erwähnt (dh wie Bubble Sort trotz Saugen populär wurde).

Sortiert 8-Bit-Ganzzahlen mit Vorzeichen direkt . (Unsigned hat die gleiche Codegröße, ändern Sie einfach die jgein a jae). Duplikate sind kein Problem. Wir tauschen mit einer 16-Bit-Drehung um 8 (mit einem Speicherziel).

Bubble Sort ist der Hammer für die Leistung , aber ich habe gelesen, dass es eines der kleinsten ist, das in Maschinencode implementiert werden kann. Dies scheint insbesondere dann der Fall zu sein, wenn es spezielle Tricks zum Austauschen benachbarter Elemente gibt. Dies ist so ziemlich der einzige Vorteil, aber manchmal (in realen eingebetteten Systemen) reicht dieser Vorteil aus, um ihn für sehr kurze Listen zu verwenden.

Ich habe die vorzeitige Kündigung für keine Swaps ausgelassen . Ich habe die "optimierte" BubbleSort-Schleife von Wikipedia verwendet, die es vermeidet, die letzten n − 1Elemente zu betrachten, wenn sie zum n-ten Mal ausgeführt werden, sodass der Zähler der äußeren Schleife die Obergrenze für die innere Schleife ist.

NASM-Auflistung ( nasm -l /dev/stdout) oder einfache Quelle

 2 address  16-bit       bubblesort16_v2:
 3          machine      ;; inputs: pointer in ds:si,  size in in cx
 4          code         ;; requires: DF=0  (cld)
 5          bytes        ;; clobbers: al, cx=0
 6                       
 7 00000000 49               dec     cx          ; cx = max valid index.  (Inner loop stops 1 before cx, because it loads i and i+1).
 8                       .outer:                 ; do{
 9 00000001 51               push    cx          ;   cx = inner loop counter = i=max_unsorted_idx
10                       .inner:                 ;   do{
11 00000002 AC               lodsb               ;     al = *p++
12 00000003 3804             cmp     [si],al     ;     compare with *p (new one)
13 00000005 7D04             jge     .noswap
14 00000007 C144FF08         rol     word [si-1], 8    ; swap
15                       .noswap:
16 0000000B E2F5             loop    .inner      ;   } while(i < size);
17 0000000D 59               pop     cx          ;  cx = outer loop counter
18 0000000E 29CE             sub     si,cx       ;  reset pointer to start of array
19 00000010 E2EF             loop    .outer      ; } while(--size);
20 00000012 C3               ret

22 00000013  size = 0x13 = 19 bytes.

push / pop von cxum die innere Schleife herum bedeutet, dass sie mit cx= outer_cx bis auf 0 läuft .

Beachten Sie, dass rol r/m16, imm8es sich nicht um einen 8086-Befehl handelt, der später hinzugefügt wurde (186 oder 286), aber es wird nicht versucht, 8086-Code zu sein, sondern nur 16-Bit x86. Wenn SSE4.1phminposuw helfen würde, würde ich es verwenden.

Eine 32-Bit-Version davon (die immer noch mit 8-Bit-Ganzzahlen, aber mit 32-Bit-Zeigern / Zählern arbeitet) hat eine Größe von 20 Byte (Präfix für Operandengröße aktiviert rol word [esi-1], 8).

Bug: size = 1 wird als size = 65536 behandelt, weil nichts uns davon abhält, das äußere do / while mit cx = 0 zu betreten. (Sie würden normalerweise dafür verwenden jcxz.) Aber zum Glück ist die 19-Byte-JumpDown-Sortierung 19 Byte und hat dieses Problem nicht.

Original x86-16 20-Byte-Version (ohne die Idee von Ped7g). Aus Platzgründen ausgelassen, finden Sie im Bearbeitungsverlauf eine Beschreibung.

Performance

Teilweise überlappendes Speichern / Neuladen (beim Rotieren des Speicherziels) führt bei modernen x86-CPUs (außer Atom in der richtigen Reihenfolge) zu einem Stillstand der Speicherweiterleitung. Wenn ein hoher Wert nach oben sprudelt, ist diese zusätzliche Latenzzeit Teil einer durch eine Schleife übertragenen Abhängigkeitskette. Das Speichern / Neuladen ist an erster Stelle scheiße (wie die Speicherweiterleitungsverzögerung von 5 Zyklen bei Haswell), aber ein Weiterleitungsstopp bringt es auf mehr als 13 Zyklen. Bei der Ausführung außerhalb der Reihenfolge kann dies nur schwer ausgeblendet werden.

Siehe auch: Stapelüberlauf: Blasensortierung zum Sortieren von Zeichenfolgen für eine Version mit einer ähnlichen Implementierung, jedoch mit einem frühen Aus, wenn keine Auslagerungen erforderlich sind. Es verwendet xchg al, ah/ mov [si], axzum Austauschen, was 1 Byte länger ist und bei einigen CPUs einen Teilregister-Stillstand verursacht. (Aber es kann immer noch besser sein, als den Speicher zu drehen, der den Wert erneut laden muss). Mein Kommentar dort hat einige Vorschläge ...

x86-64 / x86-32 JumpDown-Sortierung, 19 Byte (sortiert nach int32_t)

Aufrufbar von C unter Verwendung der x86-64-System-V-Aufrufkonvention als
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size); (Rückgabewert = max (array [])).

Dies ist https://en.wikipedia.org/wiki/Selection_sort , aber anstatt sich an die Position des Elements min zu erinnern, tauschen Sie den aktuellen Kandidaten in das Array . Wenn Sie die minimale (unsortierte_Region) gefunden haben, speichern Sie sie wie bei der normalen Auswahlsortierung am Ende der sortierten Region. Dies vergrößert den sortierten Bereich um eins. (Zeigen Sie im Code rsiauf eins nach dem Ende des sortierten Bereichs, lodsdschieben Sie ihn vor und mov [rsi-4], eaxspeichern Sie die Min zurück.)

Der Name Jump Down Sort wird in Bubble Sort: An Archaeological Algorithmic Analysis verwendet . Ich denke, meine Sortierung ist wirklich eine Jump Up-Sortierung, da hohe Elemente nach oben springen und den unteren Teil sortiert lassen, nicht das Ende.

Dieses Austauschdesign führt dazu, dass der unsortierte Teil des Arrays größtenteils in umgekehrter Reihenfolge abläuft, was später zu vielen Auslagerungen führt. (Da Sie mit einem großen Kandidaten beginnen und immer niedrigere Kandidaten sehen, tauschen Sie weiter.) Ich habe es "sprudelnd" genannt, obwohl es Elemente in die andere Richtung bewegt. Die Art und Weise, wie Elemente verschoben werden, ist auch ein bisschen wie beim Einfügen in Rückwärtsrichtung. Um es in Aktion zu sehen, verwenden Sie GDBs display (int[12])buf, setzen Sie einen Haltepunkt für die innere loopAnweisung und verwenden Sie c(continue). Drücken Sie die Eingabetaste, um den Vorgang zu wiederholen. (Der Befehl "display" veranlasst GDB, jedes Mal, wenn wir den Haltepunkt erreichen, den gesamten Array-Status zu drucken.)

xchgwith mem hat ein implizites lockPräfix, das dies besonders langsam macht. Vermutlich um eine Größenordnung langsamer als ein effizienter Load / Store-Swap; xchg m,rbeträgt eins pro 23c Durchsatz bei Skylake, aber Laden / Speichern / Verschieben mit einem tmp-Register für einen effizienten Tausch (reg, mem) kann ein Element pro Takt verschieben. Auf einer AMD-CPU, bei der die loopAnweisung schnell ist und die innere Schleife nicht so stark beeinträchtigt, ist dies möglicherweise ein schlechteres Verhältnis. Verzweigungsausfälle sind jedoch immer noch ein großer Engpass, da Auslagerungen häufig auftreten (und häufiger auftreten, wenn die unsortierte Region kleiner wird) ).

 2 Address               ;; hybrib Bubble Selection sort
 3        machine         bubblyselectionsort_int32:   ;; working, 19 bytes.  Same size for int32 or int8
 4        code               ;; input: pointer in rsi, count in rcx
 5        bytes              ;; returns: eax = max
 6                       
 7                           ;dec  ecx           ; we avoid this by doing edi=esi *before* lodsb, so we do redundant compares
 8                                               ; This lets us (re)enter the inner loop even for 1 element remaining.
 9                       .outer:
10                           ; rsi pointing at the element that will receive min([rsi]..[rsi+rcx])
11 00000000 56               push   rsi
12 00000001 5F               pop    rdi
13                           ;mov    edi, esi     ; rdi = min-search pointer
14 00000002 AD               lodsd
16 00000003 51               push   rcx          ; rcx = inner counter
17                       .inner:                   ; do {
18                           ; rdi points at next element to check
19                           ; eax = candidate min
20 00000004 AF               scasd                 ; cmp eax, [rdi++]
21 00000005 7E03             jle  .notmin
22 00000007 8747FC           xchg   [rdi-4], eax   ; exchange with new min.
23                         .notmin:
24 0000000A E2F8             loop  .inner          ; } while(--inner);
26                           ; swap min-position with sorted position
27                           ; eax = min.  If it's not [rsi-4], then [rsi-4] was exchanged into the array somewhere
28 0000000C 8946FC           mov    [rsi-4], eax
29 0000000F 59               pop   rcx           ; rcx = outer loop counter = unsorted elements left
30 00000010 E2EE             loop  .outer        ; } while(--unsorted);
32 00000012 C3               ret

34 00000013 13           .size: db $ - bubblyselectionsort_int32
           0x13 = 19 bytes long

Gleiche Code - Größe für int8_t: Verwendung lodsb/ scasb, ALund ändern Sie die [rsi/rdi-4]zu-1 . Derselbe Maschinencode funktioniert im 32-Bit-Modus für 8/32-Bit-Elemente. Der 16-Bit-Modus für 8/16-Bit-Elemente muss mit geänderten Offsets neu erstellt werden (und die 16-Bit-Adressierungsmodi verwenden eine andere Codierung). Aber immer noch 19 Bytes für alle.

Es vermeidet die Initiale, dec ecxindem es mit dem Element vergleicht, das es gerade geladen hat, bevor es weitergeht. Bei der letzten Iteration der äußeren Schleife lädt sie das letzte Element, prüft, ob es kleiner ist als sie selbst und ist dann fertig. Dies ermöglicht es, mit Größe = 1 zu arbeiten, wo mein BubbleSort fehlschlägt (behandelt es als Größe = 65536).

Ich habe diese Version (in GDB) mit dem folgenden Aufrufer getestet: Online ausprobieren ! . Sie können dies auf TIO ausführen, aber natürlich keinen Debugger oder Drucker. Das, das _startes aufruft, wird mit exit-status = größtes Element = 99 beendet, sodass Sie sehen können, dass es funktioniert.

C 72 Bytes

i,j;a(int*l,int n){for(i=0;i=i?:--n;j>l[n]?l[i]=l[n],l[n]=j:0)j=l[--i];}

Bubblesort. Das erste Argument ist ein Zeiger auf das Array, das zweite Argument ist die Länge des Arrays. Funktioniert mit gcc.

MATL , 11 10 Bytes

Y@t!d0>AY)

Extrem ineffiziente Prüfung aller Permutationen der Eingabe.

Probieren Sie es online!

Erläuterung

        % Implicitly grab input array
Y@      % Compute all permutations (each permutation as a row)
t       % Duplicate this matrix
!d      % Transpose and take the differences between the values
0>A     % Find the rows where all differences are > 0
Y)      % Return only the row where this is true
        % Implicitly display the result

Ruby, 40 Bytes

Auswahl sortieren. Anonyme Funktion; Nimmt die Liste als Argument.

->a{r=[];r<<a.delete(a.min)while[]!=a;r}

Python, 120 Bytes

def f(a):import time,threading;[threading.Thread(None,lambda b=b,c=min(a):print(time.sleep(b-c)or b)).start()for b in a]

Dies ist wahrscheinlich nicht die kürzeste Antwort, aber ich glaube, dieser Algorithmus gehört hierher. Wenn Sie eine Liste mit ganzen Zahlen aufrufen, werden diese sortiert nach stdout gedruckt. Ich würde es aber nicht mit zu großen Zahlen versuchen.

MIPS, 68 Bytes

Ich habe vor einiger Zeit eine einfache, nicht optimierte Implementierung für die Blasensortierung geschrieben. Die Anzahl der Bytes beginnt bei loopund endet bei li $v0, 10, vorausgesetzt, die Listenadresse und die Listenlänge sind bereits im Speicher.

 Address    Code        Basic                     Source

0x00400000  0x3c011001  lui $1,4097           5    main:   la      $s0, list       # List address
0x00400004  0x34300000  ori $16,$1,0               
0x00400008  0x2411000a  addiu $17,$0,10       6            li      $s1, 10         # List length
0x0040000c  0x24080000  addiu $8,$0,0         8    loop:   li      $t0, 0          # swapped
0x00400010  0x24090001  addiu $9,$0,1         9            li      $t1, 1          # for loop "i"
0x00400014  0x1131000b  beq $9,$17,11         11   for:    beq     $t1, $s1, fend  # break if i==length
0x00400018  0x00095080  sll $10,$9,2          13           sll     $t2, $t1, 2     # Temp index, multiply by 4
0x0040001c  0x01505020  add $10,$10,$16       14           add     $t2, $t2, $s0   # Combined address
0x00400020  0x8d4b0000  lw $11,0($10)         15           lw      $t3, 0($t2)     # list[i]
0x00400024  0x8d4cfffc  lw $12,-4($10)        16           lw      $t4, -4($t2)    # list[i-1]
0x00400028  0x21290001  addi $9,$9,1          18           addi    $t1, $t1, 1     # i++
0x0040002c  0x016c082a  slt $1,$11,$12        20           ble     $t4, $t3, for   # if list[i-1] > list[i]
0x00400030  0x1020fff8  beq $1,$0,-8               
0x00400034  0xad4bfffc  sw $11,-4($10)        21           sw      $t3, -4($t2)    # swap and store
0x00400038  0xad4c0000  sw $12,0($10)         22           sw      $t4, 0($t2)     
0x0040003c  0x24080001  addiu $8,$0,1         23           li      $t0, 1          # swapped=true
0x00400040  0x08100005  j 0x00400014          24           j       for
0x00400044  0x20010001  addi $1,$0,1          26   fend:   subi    $s1, $s1, 1     # length--
0x00400048  0x02218822  sub $17,$17,$1             
0x0040004c  0x1500ffef  bne $8,$0,-17         27           bnez    $t0, loop       # Repeat if swapped==true
0x00400050  0x2402000a  addiu $2,$0,10        29           li      $v0, 10        
0x00400054  0x0000000c  syscall               30           syscall

Jetzt warte ich darauf, mit x86 aus dem Wasser geblasen zu werden ...

Awk, 66 Bytes

{b=$0;a[b]}m<b{m=b}n>b{n=b}END{for(i=n;i<=m;i++)if(i in a)print i}

Arrays in awk sind wie Wörterbücher, nicht wie C-Arrays. Die Indizes können nicht zusammenhängend sein und werden nach Bedarf erweitert (und erstellt). Also erstellen wir ein Array afür die Eingabe, wobei jede Zeile ein Schlüssel ist. Und wir speichern die min und max Werte. Dann durchlaufen wir eine Schleife von min nach max und drucken alle Schlüssel, die in existieren a. bist nur zu vermeiden, wiederholte Verwendung von $0.

Python 3, 91 62 47 Bytes

def f(z):
 while z:m=min(z);z.remove(m);yield m

Danke an wnnmaw und Seeq für die Hilfe beim Golfen.

Das Argument zsollte eine Liste sein. Dies ist eine Variante der Auswahlsortierung.

Ich bin mir nicht sicher, wie es sich minschlagen lässt built-in sorting functions, da ich nicht sicher bin, wie Python implementiert wird min. Hoffentlich ist diese Lösung immer noch in Ordnung. Anregungen zum Golfen in den Kommentaren oder im PPCG-Chat sind willkommen.

MATL , 11 Bytes

`t4#X<2#)tn

Probieren Sie es online!

Dies sortiert nach der folgenden Prozedur, die O ( n ² ) ist:

1. Nehmen Sie das Minimum des Arrays.
2. Entfernen Sie diesen Wert aus dem Array und speichern Sie ihn für die spätere Anzeige.
3. Wenden Sie das gleiche Verfahren auf den Rest des Arrays an, bis es leer ist.
4. Zeigen Sie alle Nummern in der Reihenfolge an, in der sie abgerufen wurden.

MATL ist stapelbasiert. Das Array mit den verbleibenden Werten wird oben im Stapel gespeichert. Die entfernten Werte sind der Reihe nach unten aufgeführt. Am Ende des Programms werden alle diese Werte angezeigt. Das Array oben wird ebenfalls angezeigt, aber da es leer ist, wird es nicht angezeigt.

`        % Do...while loop
  t      %   Duplicate. Implicitly take input in the first iteration
  4#X<   %   Compute index of mininum of the array
  2#)    %   Push the minimum, and then the array with remaining entries
  tn     %   Duplicate and push number of elements, to be used as loop condition
         % Implicitly end do...while loop
         % Implicitly display stack contents

Pyth - 15 13 11 10 Bytes

Zwei Bytes gespart dank @Jakube.

Bogosort.

f!s>VTtT.p

Probieren Sie es hier online aus .

Ich brauche das nicht, hweil wir garantiert keine Duplikate haben.

Im Ernst, 6 Bytes

,;l@╨m

Probieren Sie es online!

Dies funktioniert genauso wie bei vielen anderen Antworten: Alle Permutationen generieren, Minimum auswählen. Ich habe irgendwie vergessen, dass dies funktionieren würde, während ich an der folgenden Lösung arbeitete.

Erläuterung:

,;l@╨m
,;l@    push len(input), input
    ╨m  minimum permutation

Im Ernst, 25 Bytes (nicht konkurrierend)

Dies wäre wettbewerbsfähig, wenn es keinen Fehler im Shuffle-Befehl gäbe, den ich gerade behoben habe.

,1WX╚;;pX@dXZ`i@-0<`MπYWX

Probieren Sie es online! Dies implementiert den besten Sortieralgorithmus aller Zeiten: Bogosort !

Erläuterung:

,1WX╚;;pX@dXZ`i@-0<`MπYWX
,                          get input
 1W                    WX  do-while:
   X                         discard
    ╚                        shuffle
     ;;                      dupe twice
       pX@dX                 remove first element of first dupe and last element of second dupe
            Z                zip
             `i@-0<`MπY      test if all differences are positive (if any are not, the list is not sorted), negate (1 if not sorted else 0)

MATL, 17 16 Bytes

Dank @LuisMendo ein Byte bei der Erstellung eines Null-Arrays gespart

vTbtX<-QI$(f8M+q

Eimer sortieren. Versuchen Sie es nicht mit einem Bereich von mehr als 2 ³¹ -1.

Probieren Sie es online!

Erläuterung

v                  % push an empty array
 T                 % push 1
  b                % bubble the input array up to the top of the stack
   t               % duplicate it
    X<             % find the minimum
      -            % subtract min from input array
       Q           % and increment to adjust for 1-based indexing
        I$(        % resulting array used as indices of empty array 
                   % (the [] way up at the top) that are assigned 1 (from T)
           f       % find the nonzero indices
            8M     % magically retrieve the 4th previous function input :/
                     (aka, the min input array value)
              +    % add it to the indices
               q   % and decrement

Bis:

• Sie können ein leeres Array in MATL mit initialisieren [] wie in MATLAB mit und vergrößern
• Verwendung (für die Zuweisungsindizierung
• So verwenden Sie die Mautomatische Zwischenablage

Neuer Tag, neuer TIL:

• vertcat Erstellt auf magische Weise ein leeres Array, wenn auf dem Stapel nichts zu verketten ist

Julia, 28 27 Bytes

x->colon(extrema(x)...)∩x

Probieren Sie es online!

R, 68 Bytes

Übernimmt die Ein- iund Ausgaben oder sortierten Liste.

o<-i
for(j in 1:length(i)){
x<-(i-min(i))==0
o[j]<-i[x]
i<-i[!x]
}
o

Erläuterung:

o<-i                      # Defines output as o
 for(j in 1:length(i)){   # Initializes loop for length of input
  x<-(i-min(i))==0        # Generates logical vector by finding the value 0 
                          # of input less the minimum of input. 
   o[j]<-i[x]             # Puts the smallest value at position j
    i<-i[!x]              # Removes the smallest value from input
      }                   # Ends loop
       o                  # Returns sorted list

Durch das Vermeiden von Permutationen können große Listen relativ schnell sortiert werden. Der "Trick" ist, dass das Subtrahieren des kleinsten Werts von der Eingabe eine einzelne 0 hinterlässt, die sowohl den kleinsten Wert als auch die Position des kleinsten Werts bestimmt.

Java 8, 112 92 Bytes

Hier ist eine andere Auswahlsorte. Die Eingabe ist eine List tGanzzahl und die sortierte Ausgabe wird standardmäßig ausgegeben.

t->{for(;0<t.size();System.out.println(t.remove(t.indexOf(java.util.Collections.min(t)))));}

Aktualisieren

• -20 [16-08-21] Verwendet ein Lambda

Retina, 95

Modifizierte Blasensortierung. Ich vermute, es gibt viel bessere Möglichkeiten, dies zu tun, auch ohne die eingebaute Netzhaut.

-\d+
$*n
\d+
$*11
+`(1+) (n+)
$2 $1
+`\b(n+) (\1n+)|(1+)(1+) \3\b
$2$3 $1$3$4
1(1*)
$.1
n+
-$.&

• Stufe 1 - Konvertieren von -ve ganzen Zahlen in unäre Zahlen mit nder Ziffer; Lass fallen- Schilder fallen.
• Stufe 2 - Konvertieren von Ganzzahlen + ve und Null in Unärzahl mit 1als Ziffer; hinzufügen1zu jedem , so dass Null durch dargestellt wird 1.
• Stufe 3 - Bewegen Sie alle -ves nach vorne.
• Stufe 4 - Sortieren: Verschiebt alle -ves mit der größten Größe (dh der kleinsten Zahl) vor die höheren -ves. Bewegen Sie kleinere + ves vor größere + ves.
• Stufe 5 - Entfernen Sie 1 von und konvertieren Sie + ve Unaries zurück in Dezimalzahlen.
• Stufe 6 - Konvertieren Sie -ve Unaries zurück in Dezimalzahlen, einschließlich Vorzeichen.

Probieren Sie es online aus.

Ruby, 22 Bytes

Eine schnelle Art der Permutation. Läuft in O (n!) Raum und Zeit.

->a{a.permutation.min}

Clojure, 73 35 Bytes

Bogosort :)

#(if(apply < %)%(recur(shuffle %)))

Frühere Version:

#(reduce(fn[r i](let[[a b](split-with(partial > i)r)](concat a[i]b)))[]%)

Reduziert auf eine sortierte Liste, rindem es in Teile "kleiner als ich" und "größer als ich" aufgeteilt wird. Ich denke, das ist die Einfügesorte .

Ruby, 26 24 Bytes

Auswahlsortierung, ähnlich der Antwort von Value Ink, jedoch mit einem anderen Ansatz für mehr Golf.

Gemäß der Spezifikation: "Eingabe / Ausgabe kann in jeder von Ihnen gewählten Methode erfolgen, sofern sie für den Menschen lesbar ist". Ich denke, das passt zur Beschreibung, die Ausgabe ist ein Array von Arrays mit einem einzelnen Element.

->l{l.map{l-l-=[l.min]}}

Beispiel:

->l{l.map{l-l-=[l.min]}}[[2,4,3,1]]
=> [[1], [2], [3], [4]]

Java 7, 106 104 Bytes

void a(int[]a){for(int b=a.length-1,d=0,c=0,e;d<b*b;c=++d%b)if(a[c]>a[c+1]){e=a[c];a[c++]=a[c];a[c]=e;}}

Hier ist eine gute alte Blasensorte. Der Funktionsparameter wurde geändert, sodass ich nichts zurückgeben muss. Ich versuche immer noch, ein paar Bytes daraus zu quetschen, damit ich das von jemandem gepostete Java Lambda schlagen kann.

-1 Byte danke an Geobits für den Hinweis, dass normales Tauschen besser ist als
-1 Byte dank Leaky Nun für den Hinweis, dass ich alle int-Deklarationen in die for-Schleife verschieben kann

Probieren Sie es online!

Ruby, 22 Bytes

->a{[*a.min..a.max]&a}

Erstellt ein Array aus dem Bereich zwischen den minimalen und maximalen Elementen des Eingabearrays. Gibt den Schnittpunkt zwischen den beiden Arrays zurück.