Ordenar una lista entera

22

El reto

Es bastante simple en realidad, ordenar una lista de números.

Detalles

Debe ordenar una lista de números en orden ascendente, sin utilizar ninguna función de clasificación / bibliotecas / etc (es decir, list.sort()en Python).

La entrada / salida se puede hacer en cualquier método que elija, siempre que sea legible por humanos.

Las lagunas estándar no se permiten como siempre.

El código más corto en bytes gana.

Debe explicar / enumerar qué método de clasificación utilizó (burbuja, inserción, selección, etc.)

La entrada no contendrá duplicados.

Muestra de entrada / salida

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

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

Nota: Un opuesto casi directo de Ordenar una lista de números

Michelfrancis Bustillos
fuente
8
Estoy muy sorprendido si esto no es un duplicado, pero no tengo tiempo para verificarlo. De todos modos, las "funciones de clasificación incorporadas" deberían estar mejor definidas. ¿Puedes usar una función que indexe todos los valores? [7 2 4 1] -> [4 2 3 1]. Además, ¿puede la lista CSV estar entre paréntesis? Además, el formato de entrada específico es muy adecuado para algunos idiomas y malo para otros. Esto hace que el análisis de entrada sea una gran parte para algunos envíos e innecesario para otros.
Stewie Griffin
1
@StewieGriffin He visto muchos desafíos de clasificación, pero ninguno trata de ordenar solo una lista entera básica. Hay muchos desafíos que son más fáciles para algunos idiomas y mucho más difíciles en otros.
Michelfrancis Bustillos
Esto es muy similar, pero tiene una restricción O (Nlog (N)).
Nathan Merrill
2
Muy relacionado con esta pregunta , pero dado que algunas respuestas aquí (por ejemplo, el filtro de rango de Dennis) requieren que la entrada sea entera, no votaré para cerrar como engañado.
Peter Taylor
Relevante: youtube.com/user/AlgoRythmics/videos - ¡Un canal de Youtube que enseña algoritmos de clasificación a través de danzas húngaras!
sergiol

Respuestas:

23

05AB1E , 2 bytes

Código:

ϧ

Mismo algoritmo que la respuesta Jelly . Calcula todas las permutaciones de la entrada y saca la más pequeña.

Pruébalo en línea!


Un método más eficiente es:

E[ß,Ž

Realiza la selección de clasificación . Utiliza CP-1252 codificación .

Pruébalo en línea!

Adnan
fuente
66
Aceptar esto temporalmente ya que no veo que nadie obtenga menos de 2.
Michelfrancis Bustillos
66
@MichelfrancisBustillos bien, si lo hicieran, sería una construcción, ¿no?
Destructible Lemon
Acabo de mirar 05AB1E / Base hace un minuto, y luego miré esto. ¿Coincidencia?
facepalm42
17

Jalea, 3 bytes

Œ!Ṃ

Esto genera todas las permutaciones de la lista de entrada, luego selecciona la permutación lexográficamente más pequeña. Muy eficiente

Créditos a @Adnan que tuvo la misma idea de forma independiente.

Pruébalo en línea!


Jalea, 4 bytes

ṂrṀf

Esto construye el rango desde el mínimo de la lista hasta el máximo de la lista, luego descarta los elementos del rango que no están presentes en la lista original. Esto es técnicamente un tipo de cubo , con cubos muy pequeños. No conozco un nombre para esta variante específica.

Pruébalo en línea!

Cómo funciona

Ṃ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.
Dennis
fuente
O ( muy ) Utiliza mucho tipo.
mbomb007
22
Entonces O. Muy usos. Mucho tipo. ¡Asombro! (Lo siento, ¿qué?)
Dennis
No soy bueno en la complejidad de los algoritmos, ¿sería esto O (n!)?
FlipTack
2
@FlipTack Yo tampoco. Probablemente un poco más alto, ya que hay n! matrices de longitud n .
Dennis
1
Simplemente seleccionando la lexografía más pequeña es O (n * n!) Ya que cada una de las n! Las matrices deben compararse secuencialmente, y la comparación lexográfica es O (n). La generación se puede hacer en O (n * n!) También si se hace de manera eficiente, así que apuesto a que el algoritmo es solo O (n * n!) Si está bien implementado
PunPun1000
12

Python, 46 45 bytes

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

Tipo de selección simple.

orlp
fuente
44
l[:]podría ser1*l
feersum
9

Brachylog , 12 7 bytes

p.'(s>)

Esto usa el tipo de permutación, que obviamente es terrible, pero bueno, ¡es más corto que Pyth!

Explicación

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
Fatalizar
fuente
9

Haskell, 38 bytes

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

La función binaria %inserta un nuevo elemento hen una lista ordenada tmediante la partición ten un prefijo ade elementos <hy un sufijob de elementos >h, y se pega enh entre ellos.

La operacion foldr(%)[]Luego, la construye una lista ordenada desde vacía insertando repetidamente elementos de la lista de entrada.

Este es un byte más corto que la implementación recursiva directa

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

Otra estrategia para 41 bytes:

f[]=[]
f l|x<-minimum l=x:f(filter(/=x)l)
xnor
fuente
Entonces esto es en.wikipedia.org/wiki/Insertion_sort , con %el bucle interno de inserción y foldrpara aplicarlo como el bucle externo.
Peter Cordes el
8

JavaScript (ES6), 51 bytes

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

Cada ciclo encuentra el número más pequeño que no se ha encontrado hasta ahora.

Neil
fuente
Llamando a esto [1,2,3,4,5,4,3,2,1]produce[1, 2, 3, 4, 5, Infinity, Infinity, Infinity, Infinity]
Benjamin Gruenbaum
@BenjaminGruenbaum "La entrada no contendrá duplicados".
Neil
Tengo exactamente el mismo bytecount con un enfoque diferente
Bálint
En realidad, 1 byte menos
Bálint
Este algoritmo es un en.wikipedia.org/wiki/Selection_sort
Peter Cordes
8

Python 2, 34 bytes

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

Toma la entrada como un conjunto, imprime sus elementos en orden creciente y termina con un error.

Una terminación limpia se puede hacer en 41 bytes:

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

o

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

La entrada se puede tomar como una lista de 39 bytes o 38 bytes 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})
xnor
fuente
Este es un en.wikipedia.org/wiki/Selection_sort , usando m=min(s)/ s - (m)como el bucle interno para encontrar y eliminar el mínimo de los elementos no clasificados, y la recursión como el externo.
Peter Cordes el
8

Haskell, 42 41 38 bytes

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

Recorre todos los enteros (firmado 64 bits, en mi máquina) y mantiene los que están en u . Por supuesto que no termina en un tiempo razonable.

La versión anterior recorrió [minimum u..maximum u] que tiene el mismo tiempo de ejecución peor caso.

Editar: @xnor guardó un byte. ¡Gracias!

nimi
fuente
filteres uno más corto:f u=filter(`elem`u)[minimum u..maximum u]
xnor
¡Qué fuerza bruta! ¿ [minimum u..]No funciona por razones de tipo?
xnor
@xnor: eso creo. Al llamar, digamos f [1,3,0], los elementos predeterminan el tipo Integerque no está vinculado, por lo que ..nunca termina. Si tiene que llamarlo así f ([1, 3, 0]::[Int]), supongo que la anotación de tipo debe incluirse en el recuento de bytes.
nimi
¿Cómo detecta elementos que ocurren más de una vez?
feersum
1
@feersum: no, pero el desafío dice: "La entrada no contendrá duplicados".
nimi
8

Oracle SQL 11.2, 205 bytes

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

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

En cuanto a qué tipo de método es, no tengo idea, ORDER BYme aseguré de olvidarlos.

Jeto
fuente
Apenas conozco SQL, pero por sus comentarios creo que está seleccionando el mínimo o el máximo de los elementos no ordenados restantes y los agrega al final de una lista ordenada. Eso lo convierte en un en.wikipedia.org/wiki/Selection_sort .
Peter Cordes el
8

Código de máquina x86-16 (BubbleSort int8_t), 20 19 bytes

Código de máquina x86-64 / 32 (JumpDownSort) 21 19 bytes

Registro de cambios:

  • Gracias a @ ped7g por el lodsb/cmp [si],al idea , y poner eso junto con un incremento / reinicio del puntero que había estado mirando. No necesitar al/ ahnos permite usar casi el mismo código para enteros más grandes.

  • Nuevo algoritmo (pero relacionado), muchos cambios de implementación: Bubbly SelectionSort permite una implementación x86-64 más pequeña para bytes o palabras clave; punto de equilibrio en x86-16 (bytes o palabras). También evita el error en size = 1 que tiene mi BubbleSort. Vea abajo.

  • Resulta que mi selección de selección burbujeante con intercambios cada vez que encuentras un nuevo min ya es un algoritmo conocido, JumpDown Sort. Se menciona en Bubble Sort: An Archaeological Algorithmic Analysis (es decir, cómo Bubble Sort se hizo popular a pesar de la succión).


Ordena enteros con signo de 8 bits en el lugar . (Sin signo es el mismo tamaño de código, simplemente cambie el jgeajae ). Los duplicados no son un problema. Intercambiamos usando una rotación de 16 bits por 8 (con un destino de memoria).

Bubble Sort es una mierda para el rendimiento , pero he leído que es uno de los más pequeños para implementar en código máquina. Esto parece especialmente cierto cuando hay trucos especiales para intercambiar elementos adyacentes. Esta es prácticamente su única ventaja, pero a veces (en sistemas integrados de la vida real) es suficiente ventaja para usarla en listas muy cortas.

Omití la terminación anticipada de permutas . Utilicé el bucle BubbleSort "optimizado" de Wikipedia que evita mirar los últimos n − 1elementos cuando se ejecuta por nenésima vez, por lo que el contador del bucle externo es el límite superior del bucle interno.

Listado NASM ( nasm -l /dev/stdout) o fuente 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 de cxalrededor del bucle interno significa que se ejecuta con cx= external_cx hasta 0.

Tenga en cuenta que rol r/m16, imm8 no es una instrucción 8086, se agregó más tarde (186 o 286), pero esto no está tratando de ser un código 8086, solo x86 de 16 bits. Si SSE4.1phminposuw ayudara, lo usaría.

Una versión de 32 bits de esto (todavía opera en enteros de 8 bits pero con punteros / contadores de 32 bits) es de 20 bytes (prefijo de tamaño de operando en rol word [esi-1], 8 )

Error: size = 1 se trata como size = 65536, porque nada nos impide ingresar al do / while externo con cx = 0. (Normalmente lo usaría jcxzpara eso). Pero afortunadamente, el JumpDown Sort de 19 bytes tiene 19 bytes y no tiene ese problema.


Versión original x86-16 de 20 bytes (sin la idea de Ped7g). Omitido para ahorrar espacio, vea el historial de edición con una descripción.


Actuación

El almacenamiento / recarga parcialmente superpuestos (en rotación de destino de memoria) provoca un bloqueo de reenvío de almacenamiento en CPU modernas x86 (excepto Atom en orden). Cuando un valor alto está burbujeando hacia arriba, esta latencia adicional es parte de una cadena de dependencia transportada en bucle. Almacenar / recargar apesta en primer lugar (como latencia de reenvío de 5 ciclos en Haswell), pero una pérdida de reenvío lo lleva a más de 13 ciclos. La ejecución fuera de orden tendrá problemas para ocultar esto.

Ver también: Desbordamiento de pila: clasificación de burbujas para ordenar cadenas para una versión de esto con una implementación similar, pero con una salida anticipada cuando no se necesitan intercambios. Utiliza xchg al, ah/ mov [si], axpara el intercambio, que es 1 byte más largo y provoca un bloqueo de registro parcial en algunas CPU. (Pero aún puede ser mejor que la memoria dst rotar, que necesita cargar el valor nuevamente). Mi comentario allí tiene algunas sugerencias ...


Ordenación JumpDown x86-64 / x86-32, 19 bytes (ordena int32_t)

Se puede llamar desde C usando la convención de llamadas del sistema V x86-64 como
int bubblyselectionsort_int32(int dummy, int *array, int dummy, unsigned long size); (valor de retorno = max (array [])).

Esto es https://en.wikipedia.org/wiki/Selection_sort , pero en lugar de recordar la posición del elemento min, intercambie el candidato actual en la matriz . Una vez que haya encontrado el min (unsorted_region), guárdelo hasta el final de la región ordenada, como Ordenar por selección normal. Esto aumenta la región ordenada por uno. (En el código, rsiapunta a una pasada el final de la región ordenada; lodsdavanza ymov [rsi-4], eax almacena el min de nuevo en él).

El nombre Jump Down Sort se usa en Bubble Sort: An Archaeological Algorithmic Analysis . Supongo que mi tipo es realmente un tipo Jump Up, porque los elementos altos saltan hacia arriba, dejando el fondo ordenado, no el final.

Este diseño de intercambio lleva a que la parte no ordenada de la matriz termine en su mayoría en orden inverso, lo que lleva a muchos intercambios más adelante. (Debido a que comienza con un candidato grande, y sigue viendo candidatos cada vez más bajos, por lo que sigue intercambiando). Lo llamé "burbujeante" a pesar de que mueve elementos en la otra dirección. La forma en que mueve los elementos también es un poco como una clasificación de inserción hacia atrás. Para verlo en acción, use GDB's display (int[12])buf, establezca un punto de interrupción en la loopinstrucción interna y usec (continuar). Presione volver para repetir. (El comando "display" hace que GDB imprima todo el estado de la matriz cada vez que alcanzamos el punto de interrupción).

xchgwith mem tiene un lockprefijo implícito que hace que esto sea más lento. Probablemente un orden de magnitud más lento que un intercambio eficiente de carga / almacenamiento; xchg m,res uno por rendimiento de 23c en Skylake, pero cargar / almacenar / mover con un tmp reg para un intercambio eficiente (reg, mem) puede cambiar un elemento por reloj. Podría ser una relación peor en una CPU AMD donde elloop instrucción es rápida y no obstaculizaría tanto el bucle interno, pero las fallas de ramificación seguirán siendo un gran cuello de botella porque los intercambios son comunes (y se vuelven más comunes a medida que la región no clasificada se vuelve más pequeña) )

 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

El tamaño del código mismo para int8_t: uso lodsb/ scasb, ALy el cambio de la[rsi/rdi-4] a-1 . El mismo código de máquina funciona en modo de 32 bits para elementos de 8/32 bits. El modo de 16 bits para elementos de 8/16 bits debe reconstruirse con los desplazamientos modificados (y los modos de direccionamiento de 16 bits usan una codificación diferente). Pero aún así 19 bytes para todos.

Evita la inicial dec ecx al comparar con el elemento que acaba de cargar antes de continuar. En la última iteración del bucle externo, carga el último elemento, comprueba si es menor que sí mismo, y luego está listo. Esto le permite trabajar con size = 1, donde mi BubbleSort falla (lo trata como size = 65536).

Probé esta versión (en GDB) usando esta llamada: ¡ Pruébelo en línea! . Puede ejecutarlo en TIO, pero por supuesto no hay depurador ni impresión. Aún así, el _startque lo llama sale con estado de salida = elemento más grande = 99, por lo que puede ver que funciona.

Peter Cordes
fuente
Puede haber espacio para mejorar la condición del bucle de bucle interno, parece estar usando muchos bytes. ¿Tal vez push / pop cxy uso looppara ambos? ¿Quizás hacer un bucle al revés, de atrás hacia adelante de la matriz para que podamos contar un índice hasta cero? (E incremente bxporque la parte ordenada está al final hacia la que se dirige).
Peter Cordes
1
Lo bajé a 19B, pero con muchos cambios, también regs de entrada (algunos cambios probablemente no son necesarios, pero como estaba jugando, permanecieron allí desde experimentos anteriores) ... todavía se basa en su trabajo, tan reacio a publicar como respuesta, puede verificarlo en pastebin: pastebin.com/0VMzdUjj
Ped7g
@ Ped7g: ¡Qué bien! Había considerado sub si, cxcomo parte del bucle externo usar un puntero en lugar de indexar, pero no había pensado en lodsb/ cmp [si], al. Había estado considerando lodsw/ dec si, o lodsb/ xchg al,ahtodavía configurar paracmp ah,al
Peter Cordes
@ Ped7g: oh, tu versión requiere cld, o supongo que podríamos hacer esa parte de la convención de llamadas. AFAIK, haberlo DFborrado no es una parte estándar de las convenciones de llamadas de 16 bits, solo 32/64. ¿O es solo que no puedes asumirlo en un gestor de arranque? Pero con una convención de llamada de registro personalizada, este es un fragmento de código tanto como una función, así que, por qué no requiere DF = 0. (Y si queremos, ES = DS para poder scasbhacerlo en lugar de hacerlo lodsbsi fuera más conveniente.)
Peter Cordes
1
@ Ped7g: No tengo idea de las convenciones de 16 bits, todo lo que sé es que no siempre se puede suponer que se borró el DF. Pero creo que eso es principalmente en un contexto de gestor de arranque. Nunca ejecuté nada que haya escrito en DOS real. Estaba en Atari Mega 4 STe (68000/68020), luego en Linux (en un Pentium MMX), así que logré evitar el x86 de 16 bits por completo hasta que las preguntas SO me lo dieron por la garganta.
Peter Cordes
6

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

Ordenamiento de burbuja. El primer argumento es un puntero a la matriz, el segundo argumento es la longitud de la matriz. Funciona con gcc.

milIbyte
fuente
Esto realmente necesita una versión sin golf para ser legible; Es realmente difícil hacer un seguimiento de dónde comienzan / terminan los operadores ternarios.
Peter Cordes el
5

MATL , 11 10 bytes

Y@t!d0>AY)

Examen extremadamente ineficiente de todas las permutaciones de la entrada.

Pruébalo en línea!

Explicación

        % 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
Suever
fuente
5

Rubí, 40 bytes.

Selección de selección. Función anónima; toma la lista como argumento.

->a{r=[];r<<a.delete(a.min)while[]!=a;r}
Tinta de valor
fuente
4

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]

Probablemente esta no sea la respuesta más corta, pero siento que este algoritmo pertenece aquí. llame con una lista de enteros, se imprimirán de manera ordenada para stdout. Sin embargo, no lo intentaría con números demasiado grandes.

Nombre de usuario censurado
fuente
Bonito primer post! Y buen nombre de usuario. : P
Rɪᴋᴇʀ
4

MIPS, 68 bytes

Hace un tiempo escribí una implementación simple de burbuja no optimizada. El recuento de bytes comienza en loopy termina en li $v0, 10, suponiendo que la dirección y la longitud de la lista ya estén en la memoria.

 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

Ahora espero ser expulsado del agua con x86 ...

qwr
fuente
1
Puede omitir la swapped=trueverificación anticipada y la cuenta regresiva según el tamaño de la matriz. Vea mi versión de 20 bytes x86-16 que ordena enteros de 8 bits . Podría hacer una versión x86 normal de 32 o 64 bits que clasifique enteros de 32 bits en algún momento, pero los enteros de 8 bits en modo de 16 bits son una especie de punto ideal para x86.
Peter Cordes el
4

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}

Las matrices en awk son como diccionarios, no como matrices en C. Los índices pueden ser no contiguos y crecen (y se crean) según sea necesario. Entonces, creamos una matriza para la entrada, con cada línea como clave. Y guardamos los valores mínimo y máximo. Luego recorremos de min a max e imprimimos todas las claves que existen en a. bes solo para evitar el uso repetido de $0.

muru
fuente
4

Python 3, 91 62 47 bytes

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

Gracias a wnnmaw y Seeq por su ayuda en el golf.

El argumento zdebería ser una lista. Esta es una variante del tipo de selección.

No estoy seguro de cómo se mincompara built-in sorting functions, ya que no estoy seguro de cómo se implementa Python min. Con suerte, esta solución aún está bien. Cualquier sugerencia de golf en los comentarios o en el chat PPCG es bienvenida.

Sherlock9
fuente
Asegúrese de indicar qué tipo de tipo está utilizando.
Michelfrancis Bustillos
@MichelfrancisBustillos Honestamente he olvidado qué algoritmo es este. ¿Podría ser el tipo de selección?
Sherlock9
1
Solo por curiosidad, ¿por qué no simplemente tomar una lista directamente? La pregunta permite el formato de entrada abierto
wnnmaw
1
@wnnmaw Dang it, escribí uno pero olvidé publicarlo. Gracias por el recordatorio: D
Sherlock9
Hmm, tal vezdef f(z):\nwhile z:m=min(z);z.remove(m);yield m
seequ
4

MATL , 11 bytes

`t4#X<2#)tn

Pruébalo en línea!

Esto se ordena mediante el siguiente procedimiento, que es O ( n 2 ):

  1. Toma el mínimo de la matriz.
  2. Elimine ese valor de la matriz y guárdelo para su posterior visualización.
  3. Aplique el mismo procedimiento con el resto de la matriz, hasta que quede vacío.
  4. Mostrar todos los números en el orden en que se obtuvieron.

MATL está basado en pila. La matriz con los valores restantes se mantiene en la parte superior de la pila. Los valores eliminados están debajo, en orden. Al final del programa se muestran todos esos valores. La matriz en la parte superior también se mostrará, pero como está vacía, no se muestra.

`        % 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
Luis Mendo
fuente
3

Pyth - 15 13 11 10 bytes

Dos bytes guardados gracias a @Jakube.

Bogosort.

f!s>VTtT.p

Pruébelo en línea aquí .

No necesito el hprimo porque estamos garantizados sin duplicados.

Maltysen
fuente
@Jakube Me siento estúpido, gracias.
Maltysen
@Suever como dije en mi respuesta, tenemos garantizado que no hay duplicados según OP.
Maltysen
¡Lo siento por eso! Perdí ese punto.
Suever
3

En serio, 6 bytes

,;l@╨m

Pruébalo en línea!

Esto hace lo mismo que muchas otras respuestas: generar todas las permutaciones, seleccionar mínimo. Olvidé un poco que esto funcionaría mientras estaba trabajando en la solución a continuación.

Explicación:

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

En serio, 25 bytes (no competitivos)

Esto sería competitivo si no fuera por un error en el comando shuffle que acabo de solucionar.

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

Pruébalo en línea! Esto implementa el mejor algoritmo de clasificación de todos los tiempos: Bogosort !

Explicación:

,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)
Mego
fuente
3

MATL 17 16 bytes

Se guardó un byte creando una matriz nula gracias a @LuisMendo

vTbtX<-QI$(f8M+q

Tipo de cubo. No lo intentes con un rango mayor a 2 31 -1.

Pruébalo en línea!

Explicación

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:

  • Puede inicializar una matriz vacía en MATL usando [] y crecerla, al igual que en MATLAB
  • Cómo utilizar ( para indexar tareas
  • Cómo usar el Mportapapeles automático

Nuevo día, nuevo TIL:

  • vertcat crea mágicamente una matriz vacía cuando no hay nada en la pila para concatenar
cubilete
fuente
Agregue a su TIL: una inicial [] puede ser reemplazada por v. Esto se debe a que la cantidad predeterminada de entradas de ves la cantidad de elementos en la pila
Luis Mendo
@LuisMendo Sooo ... si hay una matriz en la pila ...? Investigando
vaso de precipitados
Entonces no hace nada. Piense en ello comovertcat(STACK{:})
Luis Mendo
3

R, 68 bytes

Toma entradas iy salidas, oque es la lista ordenada.

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

Explicación:

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

Evitar las permutaciones significa que puede ordenar listas grandes con relativa rapidez. El "truco" es que restar el valor más pequeño de la entrada deja un solo 0 que determina tanto el valor más pequeño como la posición del valor más pequeño.

Forgottenscience
fuente
3

Java 8, 112 92 bytes

Aquí hay otro tipo de selección. La entrada es un número List tentero y la salida ordenada se imprime en salida estándar.

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

Actualizar

  • -20 [16-08-21] Usó una lambda
Fruta no lineal
fuente
¡Hola, no lineal, y bienvenidos a PPCG!
isaacg
¡Bienvenido a Programming Puzzles & Code Golf! Parece que su código supone tque existe una variable , lo que lo convierte en un fragmento; requerimos que las presentaciones sean programas o funciones completos que utilizan nuestros formatos de E / S predeterminados . También exigimos que las importaciones tengan en cuenta el recuento de bytes. ¡Hazme saber si tienes alguna pregunta!
Alex A.
Gracias por los recursos! Modifiqué mi respuesta para que fuera una función e incluir la importación.
NonlinearFruit
2

Retina, 95

Tipo de burbuja modificado. Sospecho que hay formas mucho mejores de hacer esto, incluso sin el tipo de retina incorporado.

-\d+
$*n
\d+
$*11
+`(1+) (n+)
$2 $1
+`\b(n+) (\1n+)|(1+)(1+) \3\b
$2$3 $1$3$4
1(1*)
$.1
n+
-$.&
  • Etapa 1: convertir -ve enteros a unarios con nel dígito; deja caer las -señales
  • Etapa 2: convertir + ve y cero enteros a unario con 1el dígito; agregue 1a cada uno, de modo que cero esté representado por 1.
  • Etapa 3: mueve todos los vientos al frente.
  • Etapa 4 - Ordenar: mueve todos los -ves con la mayor magnitud (es decir, el número más pequeño) por delante de los más altos. Mueve los + ves más pequeños antes que los + ves más grandes
  • Etapa 5: elimina 1 de y convierte + ve unarios de nuevo a decimal.
  • Etapa 6: convierte -ve unarios de nuevo a decimal, incluido el signo.

Pruébalo en línea.

Trauma digital
fuente
@LeakyNun Eso no ordena el último elemento de la lista.
mbomb007
@ mbomb007 bien, no importa.
Leaky Nun
2

Ruby, 22 bytes

Un tipo de permutación rápida . Se ejecuta en O (n!) Espacio y tiempo.

->a{a.permutation.min}
MegaTom
fuente
2

Clojure, 73 35 bytes

Bogosort :)

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

Version anterior:

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

Se reduce a una lista ordenada rdividiéndola en partes "más pequeñas que i" y "más grandes que i". Supongo que este es el tipo de inserción .

NikoNyrh
fuente
¡Agradable! No sabía que pudieras recuren una función anónima. Tampoco lo sabía shuffle.
Matias Bjarland
2

Ruby, 26 24 bytes

Tipo de selección, similar a la respuesta de Value Ink, pero utilizando un enfoque diferente para una mayor golfidad.

De acuerdo con la especificación: "La entrada / salida se puede hacer en cualquier método que elija, siempre que sea legible por humanos". Creo que esto se ajusta a la descripción, la salida es una matriz de matrices con un solo elemento.

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

ejemplo:

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

Java 7, 106104 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;}}

Aquí hay un buen tipo de burbuja ole. El parámetro de función se modifica en su lugar para que no tenga que devolver nada. Todavía trato de exprimir algunos bytes de esto para poder vencer a la lambda de Java que alguien publicó.

-1 byte gracias a Geobits por señalar que el intercambio normal supera xor'ing
-1 byte gracias a Leaky Nun por señalar que puedo mover todas las declaraciones int al bucle for

Pruébalo en línea!

Meter
fuente
2

Ruby, 22 bytes

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

Crea una matriz fuera del rango entre los elementos mínimo y máximo de la matriz de entrada. Devuelve la intersección entre las dos matrices.

dkudriavtsev
fuente
Supongo que es una especie de en.wikipedia.org/wiki/Counting_sort .
Peter Cordes
@PeterCordes Ese era el punto
dkudriavtsev
La pregunta le pide que describa qué tipo de clasificación es, por lo que pensé que era útil vincular al conocido algoritmo, así como simplemente describir lo que realmente hace.
Peter Cordes
Cierto. Gracias @PeterCordes
dkudriavtsev