Le défi

C'est assez simple vraiment, trier une liste de nombres.

Détails

Vous devez trier une liste de nombres dans l'ordre croissant, sans utiliser de fonctions de tri / bibliothèques / etc intégrées (c'est- list.sort()à- dire en Python).

L'entrée / sortie peut être effectuée dans n'importe quelle méthode que vous choisissez, tant qu'elle est lisible par l'homme.

Les failles standard sont toujours interdites.

Le code le plus court en octets gagne.

Vous devez expliquer / lister la méthode de tri que vous avez utilisée (bulle, insertion, sélection, etc.)

L'entrée ne contiendra pas de doublons.

Exemple d'entrée / sortie

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

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

Remarque: Un opposé presque direct de Trier une liste de nombres

05AB1E , 2 octets

Code:

ϧ

Même algorithme que la réponse Jelly . Calcule toutes les permutations de l'entrée et sort la plus petite.

Essayez-le en ligne!

Une méthode plus efficace consiste à:

E[ß,Ž

Effectue un tri par sélection . Utilise l' encodage CP-1252 .

Essayez-le en ligne!

Gelée, 3 octets

Œ!Ṃ

Cela génère toutes les permutations de la liste d'entrée, puis sélectionne la permutation lexographiquement la plus petite. Très efficace.

Crédits à @Adnan qui a eu la même idée indépendamment.

Essayez-le en ligne!

Gelée, 4 octets

ṂrṀf

Cela construit la plage du minimum de la liste au maximum de la liste, puis supprime les éléments de la plage non présents dans la liste d'origine. Il s'agit techniquement d'une sorte de seau , avec de très petits seaux. Je ne connais pas de nom pour cette variante spécifique.

Essayez-le en ligne!

Comment ça marche

Ṃ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 octets

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

Tri par sélection simple.

Brachylog , 12 7 octets

p.'(s>)

Cela utilise le tri par permutation, ce qui est évidemment terrible, mais bon c'est plus court que Pyth!

Explication

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 octets

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

La fonction binaire %insère un nouvel élément hdans une liste triée ten partitionnant ten un préfixe ad'éléments <het un suffixe bd'éléments >h, et se colle hentre eux.

L'opération foldr(%)[]crée ensuite une liste triée à partir de vide en insérant à plusieurs reprises des éléments de la liste d'entrée.

C'est un octet plus court que l'implémentation récursive directe

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

Une autre stratégie pour 41 octets:

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

JavaScript (ES6), 51 octets

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

Chaque boucle trouve le plus petit nombre qui n'a pas été trouvé jusqu'à présent.

Python 2, 34 octets

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

Prend l'entrée comme un ensemble, imprimant ses éléments dans un ordre croissant, se terminant par une erreur.

Une terminaison propre peut être effectuée en 41 octets:

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

ou

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

L'entrée peut être considérée comme une liste de 39 octets, ou 38 octets en Python 3.5:

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 octets

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

Boucle sur tous les entiers (signé 64 bits, sur ma machine) et conserve ceux qui sont dedans u. Bien sûr, cela ne se termine pas dans un délai raisonnable.

La version précédente a bouclé à travers [minimum u..maximum u]laquelle a le même temps d'exécution pire cas.

Modifier: @xnor a enregistré un octet. Merci!

Oracle SQL 11.2, 205 octets

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

Non golfé

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)          

Quant à la méthode de tri, je n'en ai aucune idée, ORDER BYje me suis assuré de les oublier.

code machine x86-16 (BubbleSort int8_t), 20 19 octets

code machine x86-64 / 32 (JumpDownSort) 21 19 octets

Journal des modifications:

• Merci à @ ped7g pour l' idée lodsb/ cmp [si],al, et à mettre cela ensemble avec une augmentation / réinitialisation du pointeur que je regardais. Ne pas avoir besoin al/ ahpermet d'utiliser presque le même code pour les entiers plus grands.

• Nouvel algorithme (mais lié), de nombreux changements d'implémentation: Bubbly SelectionSort permet une implémentation x86-64 plus petite pour les octets ou les mots-clés; seuil de rentabilité sur x86-16 (octets ou mots). Évite également le bug sur size = 1 que mon BubbleSort a. Voir ci-dessous.

• Il s'avère que mon Bubbly Selection Sort avec des swaps chaque fois que vous trouvez un nouveau min est déjà un algorithme connu, JumpDown Sort. Il est mentionné dans Bubble Sort: une analyse algorithmique archéologique (c'est-à-dire comment Bubble Sort est devenu populaire malgré la succion).

Trie les entiers signés 8 bits sur place . (Non signé a la même taille de code, changez simplement le jgeen a jae). Les doublons ne sont pas un problème. Nous échangeons en utilisant une rotation de 16 bits par 8 (avec une destination mémoire).

Bubble Sort craint pour les performances , mais j'ai lu que c'est l'un des plus petits à implémenter dans le code machine. Cela semble particulièrement vrai lorsqu'il existe des astuces spéciales pour échanger des éléments adjacents. C'est à peu près son seul avantage, mais parfois (dans les systèmes embarqués réels), c'est assez d'avantage pour l'utiliser pour des listes très courtes.

J'ai omis la résiliation anticipée sur aucun échange . J'ai utilisé la boucle BubbleSort «optimisée» de Wikipédia qui évite de regarder les derniers n − 1éléments lors de l'exécution pour la ncinquième fois, donc le compteur de la boucle externe est la limite supérieure de la boucle interne.

Liste NASM ( nasm -l /dev/stdout) ou source simple

 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 cxautour de la boucle interne signifie qu'il s'exécute avec cx= externe_cx jusqu'à 0.

Notez qu'il rol r/m16, imm8ne s'agit pas d'une instruction 8086, elle a été ajoutée plus tard (186 ou 286), mais cela n'essaie pas d'être du code 8086, juste du x86 16 bits. Si SSE4.1 phminposuwpouvait aider, je l'utiliserais.

Une version 32 bits de ceci (fonctionnant toujours sur des entiers 8 bits mais avec des pointeurs / compteurs 32 bits) est de 20 octets (préfixe de taille d'opérande activé rol word [esi-1], 8)

Bug: size = 1 est traité comme size = 65536, car rien ne nous empêche d'entrer dans le do / while externe avec cx = 0. (Vous l'utiliseriez normalement jcxzpour cela.) Mais heureusement, le tri JumpDown de 19 octets fait 19 octets et n'a pas ce problème.

Version originale x86-16 de 20 octets (sans idée de Ped7g). Omis pour économiser de l'espace, consultez l' historique des modifications avec une description.

Performance

Le stockage / rechargement partiellement chevauchant (dans la rotation de destination de la mémoire) provoque un blocage de transfert de magasin sur les processeurs x86 modernes (sauf Atom dans l'ordre). Lorsqu'une valeur élevée se propage vers le haut, cette latence supplémentaire fait partie d'une chaîne de dépendance portée par la boucle. Le stockage / rechargement aspire en premier lieu (comme la latence de transfert de magasin à 5 cycles sur Haswell), mais un blocage de transfert le ramène à plus ou moins 13 cycles. Une exécution dans le désordre aura du mal à le masquer.

Voir aussi: Stack Overflow: bubble sort pour trier la chaîne pour une version de ceci avec une implémentation similaire, mais avec un early-out quand aucun swap n'est nécessaire. Il utilise xchg al, ah/ mov [si], axpour l'échange, qui est de 1 octet de plus et provoque un blocage de registre partiel sur certains processeurs. (Mais cela peut être encore mieux que la rotation de mémoire-dst, qui doit charger à nouveau la valeur). Mon commentaire a quelques suggestions ...

Tri JumpDown x86-64 / x86-32, 19 octets (tri int32_t)

Appelable depuis C en utilisant la convention d'appel System V x86-64 as
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size); (valeur de retour = max (tableau [])).

Il s'agit de https://en.wikipedia.org/wiki/Selection_sort , mais au lieu de se souvenir de la position de l'élément min, permutez le candidat actuel dans le tableau . Une fois que vous avez trouvé le min (unsorted_region), stockez-le à la fin de la région triée, comme le tri de sélection normal. Cela agrandit la région triée d'une unité. (Dans le code, rsipointe vers un après la fin de la région triée; l' lodsdavance et y mov [rsi-4], eaxstocke le min.)

Le nom Jump Down Sort est utilisé dans Bubble Sort: An Archaeological Algorithmic Analysis . Je suppose que mon tri est vraiment un tri par saut, car les éléments hauts sautent vers le haut, laissant le bas trié, pas la fin.

Cette conception d'échange conduit à la partie non triée du tableau se retrouvant principalement dans un ordre trié inversé, ce qui entraîne de nombreux échanges plus tard. (Parce que vous commencez avec un grand candidat, et continuez à voir des candidats de plus en plus bas, alors vous continuez à permuter.) Je l'ai appelé "pétillant" même s'il déplace les éléments dans l'autre sens. La façon dont il déplace les éléments est également un peu comme un tri par insertion vers l'arrière. Pour le regarder en action, utilisez les GDB display (int[12])buf, définissez un point d'arrêt sur l' loopinstruction interne et utilisez c(continuer). Appuyez sur retour pour répéter. (La commande "display" permet à GDB d'imprimer tout l'état du tableau à chaque fois que nous atteignons le point d'arrêt).

xchgavec mem a un lockpréfixe implicite qui rend cela très lent. Probablement environ un ordre de grandeur plus lent qu'un échange de charge / stockage efficace; xchg m,rest un par débit 23c sur Skylake, mais charger / stocker / déplacer avec un reg tmp pour un swap efficace (reg, mem) peut décaler un élément par horloge. Cela pourrait être un pire rapport sur un processeur AMD où l' loopinstruction est rapide et ne gênerait pas autant la boucle interne, mais les échecs de branchement seront toujours un gros goulot d'étranglement car les échanges sont courants (et deviennent plus courants à mesure que la région non triée devient plus petite). ).

 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

Taille du même code pour int8_t: utilisation lodsb/ scasb, ALet changer le [rsi/rdi-4]à -1. Le même code machine fonctionne en mode 32 bits pour les éléments 8/32 bits. Le mode 16 bits pour les éléments 8/16 bits doit être reconstruit avec les décalages modifiés (et les modes d'adressage 16 bits utilisent un codage différent). Mais toujours 19 octets pour tous.

Il évite l'initiale dec ecxen comparant avec l'élément qu'il vient de charger avant de continuer. Lors de la dernière itération de la boucle externe, il charge le dernier élément, vérifie s'il est inférieur à lui-même, puis c'est fait. Cela lui permet de fonctionner avec size = 1, où mon BubbleSort échoue (le traite comme size = 65536).

J'ai testé cette version (en GDB) en utilisant cet appelant: Essayez-le en ligne! . Vous pouvez l'exécuter sur TIO, mais bien sûr sans débogueur ni impression. Pourtant, celui _startqui l'appelle quitte avec exit-status = le plus grand élément = 99, donc vous pouvez voir que cela fonctionne.

C, 72 octets

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. Le premier argument est un pointeur sur le tableau, le deuxième argument est la longueur du tableau. Fonctionne avec gcc.

MATL , 11 10 octets

Y@t!d0>AY)

Examen extrêmement inefficace de toutes les permutations de l'entrée.

Essayez-le en ligne!

Explication

        % 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

Rubis, 40 octets

Tri par sélection. Fonction anonyme; prend la liste en argument.

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

Python, 120 octets

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]

Ce ne sera probablement pas la réponse la plus courte mais j'ai l'impression que cet algorithme appartient ici. appeler avec une liste d'entiers, ils seront imprimés de manière triée sur stdout. Je ne l'essayerais cependant pas avec un trop grand nombre.

MIPS, 68 octets

Il y a quelque temps, j'ai écrit une simple implémentation de tri à bulle non optimisée. Le décompte d'octets commence à loopet se termine à li $v0, 10, en supposant que l'adresse et la longueur de la liste sont déjà en mémoire.

 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

Maintenant j'attends d'être soufflé hors de l'eau avec x86 ...

Awk, 66 octets

{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}

Les tableaux dans awk sont comme des dictionnaires, pas comme des tableaux C. Les index peuvent être non contigus et ils augmentent (et sont créés) selon les besoins. Ainsi, nous créons un tableau apour l'entrée, chaque ligne étant une clé. Et nous enregistrons les valeurs min et max. Ensuite, nous bouclons de min à max et imprimons toutes les clés qui existent dans a. best juste pour éviter une utilisation répétée de $0.

Python 3, 91 62 47 octets

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

Merci à wnnmaw et Seeq pour leur aide au golf.

L'argument zdevrait être une liste. Il s'agit d'une variante du tri par sélection.

Je ne sais pas comment se mincompare à cela built-in sorting functions, car je ne sais pas comment Python implémente min. Espérons que cette solution est toujours valable. Toutes les suggestions de golf dans les commentaires ou dans chat PPCG sont les bienvenues.

MATL , 11 octets

`t4#X<2#)tn

Essayez-le en ligne!

Cela trie par la procédure suivante, qui est O ( n ² ):

1. Prenez le minimum du tableau.
2. Supprimez cette valeur du tableau et stockez-la pour un affichage ultérieur.
3. Appliquez la même procédure avec le reste de la baie jusqu'à ce qu'elle soit vide.
4. Affichez tous les numéros dans l'ordre dans lequel ils ont été obtenus.

MATL est basé sur la pile. Le tableau avec les valeurs restantes est conservé en haut de la pile. Les valeurs supprimées sont ci-dessous, dans l'ordre. À la fin du programme, toutes ces valeurs sont affichées. Le tableau en haut serait également affiché, mais comme il est vide, il ne s'affiche pas.

`        % 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 octets

Deux octets enregistrés grâce à @Jakube.

Bogosort.

f!s>VTtT.p

Essayez-le en ligne ici .

Je n'ai pas besoin du hcuz nous sommes garantis sans doublons.

Sérieusement, 6 octets

,;l@╨m

Essayez-le en ligne!

Cela fait la même chose que de nombreuses autres réponses: générer toutes les permutations, sélectionner minimum. J'ai un peu oublié que cela fonctionnerait pendant que je travaillais sur la solution ci-dessous.

Explication:

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

Sérieusement, 25 octets (non concurrents)

Ce serait compétitif s'il n'y avait pas un bug dans la commande de lecture aléatoire que je viens de corriger.

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

Essayez-le en ligne! Cela implémente le meilleur algorithme de tri jamais créé : Bogosort !

Explication:

,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 octets

Enregistrement d'un octet créant un tableau nul grâce à @LuisMendo

vTbtX<-QI$(f8M+q

Tri par seau. Ne l'essayez pas avec une plage supérieure à 2 ³¹ -1.

Essayez-le en ligne!

Explication

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

TIL:

• Vous pouvez initialiser un tableau vide dans MATL en utilisant []et l'agrandir, comme dans MATLAB
• Comment utiliser (pour l'indexation des affectations
• Comment utiliser le Mpresse-papiers automatique

Nouveau jour, nouveau TIL:

• vertcat crée comme par magie un tableau vide quand il n'y a rien sur la pile pour concaténer

Julia, 28 27 octets

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

Essayez-le en ligne!

R, 68 octets

Prend les entrées iet sorties oqui est la liste triée.

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

Explication:

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

Éviter les permutations signifie qu'il peut trier de grandes listes relativement rapidement. L'astuce est que la soustraction de la plus petite valeur de l'entrée laisse un seul 0 qui détermine à la fois la plus petite valeur et la position de la plus petite valeur.

Java 8, 112 92 octets

Voici un autre type de sélection. L'entrée est un nombre List tentier et la sortie triée est imprimée en sortie standard.

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

Mise à jour

• -20 [16-08-21] A utilisé un lambda

Rétine, 95

Tri des bulles modifié. Je soupçonne qu'il existe de bien meilleures façons de le faire, même sans le tri rétinien intégré.

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

• Étape 1 - convertir les entiers -ve en unaire avec ncomme chiffre; laissez tomber les -signes.
• Étape 2 - convertir les entiers + ve et zéro en unaire avec 1comme chiffre; ajouter 1à chacun, de sorte que zéro est représenté par 1.
• Étape 3 - Déplacez tous les -ve vers l'avant.
• Étape 4 - Trier: déplacez tous les -ves avec la plus grande amplitude (c'est-à-dire le plus petit numérique) devant les -ves supérieurs. Déplacez les plus petits + contre les plus grands.
• Étape 5 - Supprimez 1 de, et convertissez + unaires en décimal.
• Étape 6 - reconvertissez -ve unaire en décimal, y compris le signe.

Essayez-le en ligne.

Rubis, 22 octets

Une sorte de permutation rapide . Fonctionne dans l'espace et le temps O (n!).

->a{a.permutation.min}

Clojure, 73 35 octets

Bogosort :)

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

Version précédente:

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

Réduit à une liste triée ren la divisant en parties "plus petites que i" et "plus grandes que i". Je suppose que c'est le type d'insertion .

Rubis, 26 24 octets

Tri de sélection, similaire à la réponse de Value Ink, mais utilisant une approche différente pour une plus grande absence de golf.

Selon la spécification: "L'entrée / sortie peut être effectuée dans n'importe quelle méthode que vous choisissez, tant qu'elle est lisible par l'homme". Je pense que cela correspond à la description, la sortie est un tableau de tableaux avec un seul élément.

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

Exemple:

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

Java 7, 106 104 octets

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;}}

Voici un bon tri de bulles oléiques. Le paramètre de fonction est modifié sur place, donc je n'ai rien à retourner. J'essaie toujours d'en extraire quelques octets pour que je puisse battre la lambda java que quelqu'un a publiée.

-1 octet merci à Geobits pour avoir souligné que le swapping normal bat xor'ing
-1 octet merci à Leaky Nun pour avoir souligné que je peux déplacer toutes les déclarations int dans la boucle for

Essayez-le en ligne!

Rubis, 22 octets

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

Construit un tableau hors de la plage entre les éléments minimum et maximum du tableau d'entrée. Renvoie l'intersection entre les deux tableaux.