El algoritmo de clasificación es el siguiente:
Mientras la lista no esté ordenada, ajuste la mitad de todos los elementos (elimínelos de la lista). Continúe hasta que la lista esté ordenada o solo quede un elemento (que está ordenado de manera predeterminada). Este algoritmo de clasificación puede dar resultados diferentes según la implementación.
El procedimiento de eliminación de elementos depende de la implementación que decida, pero la lista debe ser la mitad del tiempo anterior a una pasada del procedimiento de eliminación de elementos. Su algoritmo puede decidir eliminar ya sea la primera mitad o la lista, la última mitad de la lista, todos los elementos impares, todos los elementos pares, uno a la vez hasta que la lista sea la mitad de la lista, o ninguno no mencionado.
La lista de entrada puede contener una cantidad arbitraria de elementos (dentro de lo razonable, digamos hasta 1000 elementos), no solo listas perfectamente divisibles de 2 ^ n elementos. Tendrá que eliminar (n + 1) / 2 o (n-1) / 2 elementos si la lista es impar, ya sea codificada o decidida aleatoriamente durante el tiempo de ejecución. Decide por ti mismo: ¿qué haría Thanos si el universo contuviera una cantidad extraña de seres vivos?
La lista se ordena si ningún elemento es más pequeño que cualquier elemento anterior. Se pueden producir duplicados en la entrada y en la salida.
Su programa debe tomar una matriz de enteros (a través de stdin o como parámetros, ya sea elementos individuales o un parámetro de matriz), y devolver la matriz ordenada (o imprimirla en stdout).
Ejemplos:
// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]
// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half
[1, 2, 4, 3, 5]
podría dar resultados diferentes:
// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]
o:
// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed
o:
// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed
o:
// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]
[9, 1, 1, 1, 1]
. Mi propio algoritmo falló en esta entradaRespuestas:
R , 41 bytes
Pruébalo en línea!
fuente
is.unsorted
en lugar deany(...)
también serían 41 bytes.Python 3 ,
384239 bytesPruébalo en línea!
-3 bytes
gracias a @JoKing y @Quuxplusonefuente
!= sorted(t)
debe ser> sorted(t)
.Python 2 , 39 bytes
Pruébalo en línea!
fuente
Brachylog (v2), 6 bytes
Pruébalo en línea!
Esta es una presentación de función. Entrada desde la izquierda, salida hacia la derecha, como de costumbre. (El enlace TIO utiliza un argumento de línea de comandos que envuelve automáticamente la función en un programa completo, para que pueda verla en acción).
Explicación
Ronda de bonificación
Pruébalo en línea!
El chasquido debe ser aleatorio, ¿no? Aquí hay una versión del programa que elige los elementos supervivientes al azar (al tiempo que garantiza que la mitad sobreviva en cada ronda).
Esto sería bastante más corto si pudiéramos reordenar los elementos, pero ¿por qué un algoritmo de clasificación querría hacer eso ?
fuente
Perl 6 , 30 bytes
Pruébalo en línea!
Función recursiva que elimina la segunda mitad de la lista hasta que se ordena.
Explicación:
fuente
C # (compilador interactivo de Visual C #) , 76 bytes
Pruébalo en línea!
fuente
Java 10,
10697 bytes-9 bytes gracias a @ OlivierGrégoire .
Pruébalo en línea.
Solo deje la primera mitad de la lista cada iteración, y elimina los elementos si el tamaño de la lista es impar.n + 12
Explicación:
fuente
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;}
es más corto usando transmisiones, pero no he podido descubrir cómo evitar eljava.lang.IllegalStateException: stream has already been operated upon or closed
error después de devolver la transmisiónreduce
es una operación de terminal que cierra la transmisión. Nunca podrá llamarreduce
dos veces en la misma transmisión. Sin embargo, puede crear una nueva secuencia.Wolfram Language (Mathematica) , 30 bytes
Pruébalo en línea!
@Doorknob guardó 12 bytes
fuente
x[[;;;;2]]
).OrderedQ
, pero no podía hacerlo funcionarOrderedQ
en mi primer acercamiento (ver ediciones)JavaScript (ES6),
4948 bytesGuardado 1 byte gracias a @tsh
Elimina cada segundo elemento.
Pruébalo en línea!
fuente
p++&1
->a^=1
Ruby , 37 bytes
Pruébalo en línea!
fuente
05AB1E ,
87 bytes-1 byte gracias a @Emigna .
Pruébelo en línea o verifique algunos casos de prueba más (o verifique esos casos de prueba con paso a paso para cada iteración ).
Alternativa de 7 bytes por @Grimy :
Pruébelo en línea o verifique algunos casos de prueba más (o verifique esos casos de prueba con paso a paso para cada iteración ).
Explicación:
fuente
ι
lugar de2ä
si cambia a una estrategia de mantener todos los demás elementos .ΔÐ{Ê>äн
TI-BASIC (TI-84),
47424544 bytes-1 byte gracias a @SolomonUcko!
La lista de entrada está adentro
Ans
.La salida está adentro
Ans
y se imprime implícitamente.Explicación:
Nota: TI-BASIC es un lenguaje tokenizado. El recuento de caracteres no es igual al recuento de bytes.
fuente
not(min(L1=Ans
conmax(L1≠Ans
para guardar un byte.Jalea , 7 bytes
Pruébalo en línea!
fuente
Haskell ,
5755 bytes (gracias solo a ASCII)Pruébalo en línea!
Código original
Pruébalo en línea!
Sin golf:
fuente
Octava , 49 bytes
Pruébalo en línea! Este fue un viaje donde más aburrido es mejor. Tenga en cuenta las dos entradas mucho más interesantes a continuación:
50 bytes
Pruébalo en línea! En lugar de la solución imperativa poco interesante, podemos hacer una solución recursiva, por solo un byte adicional.
53 bytes
Pruébalo en línea! Sí. Una función anónima recursiva, gracias a la brillante respuesta de @ ceilingcat en mi pregunta de consejos . Una función anónima que devuelve una función anónima recursiva definiéndose en su lista de argumentos. Me gustan las funciones anónimas. Mmmmm
fuente
MATL , 11 bytes
Pruébalo en línea!
Esto funciona eliminando cada segundo elemento.
Explicación
fuente
Japt , 10 bytes
Intentalo
fuente
Java (JDK) , 102 bytes
Ya hay una respuesta C #, así que decidí probar mi mano en una respuesta Java.
Pruébalo en línea!
fuente
Cristal , 58 bytes
Con
Array#sort
( 58 bytes ):Pruébalo en línea!
Sin
Array#sort
( 101 bytes ):Pruébalo en línea!
fuente
Casco ,
65 bytes1 byte guardado gracias a Zgarb
Pruébalo en línea!
Explicación
fuente
Ċ2
lugar de(←½
guardar un byte.Gaia ,
98 bytesPruébalo en línea!
Explicación:
fuente
Julia 1.0 , 30 bytes
Pruébalo en línea!
Toma cada segundo elemento de la matriz si no está ordenado.
fuente
-
para 20 bytes. También casi nunca contamos caracteres: | así que sería bueno si eso se eliminara del encabezadoC ++ (gcc) , 103 bytes
No puedo comentar, pero mejoré la versión de movatica al reducir las inclusiones y usar auto.
-2 Bytes: ceilingcat
-2 Bytes: solo ASCII
Pruébalo en línea!
fuente
l.size()/2
?(n+1)/2
o(n-1)/2
ambos son válidos. hmm ....VDM-SL , 99 bytes
Nunca se envió en vdm antes, por lo que no estoy seguro de las reglas específicas del idioma. Así que he enviado como una definición de función que toma un
seq of int
y devuelve unseq of int
Un programa completo para ejecutar podría verse así:
fuente
Pyth, 10 bytes
Pruébelo en línea aquí . Esto elimina la segunda mitad en cada iteración, redondeando hacia abajo. Para cambiarlo y eliminar la primera mitad, redondeando hacia arriba, cambie el
h
ae
.fuente
hc
con%
. Esto también le permite eliminar la variable lambda finalZ
y dejar que Pyth la complete implícitamente, para un total de 2 bytes guardados.C ++ (gcc) ,
139137116 bytes-2 bytes gracias al techo, -21 bytes gracias a PeterZuger
Cambie el tamaño del vector a su primera mitad hasta que esté ordenado.
Pruébalo en línea!
fuente
include
sK (oK) ,
2220 bytesSolución:
Pruébalo en línea!
Itere sobre la entrada hasta que esté ordenada ... si no está ordenada, tome los primeros n / 2 elementos.
Ediciones:
fuente
(.5*#x)#x
->*2 0N#x
2 0N
pero supuse que sería más largo (sin pruebas), ¡gracias!Julia 1.0 , 33 bytes
Pruébalo en línea!
fuente
Retina , 38 bytes
Pruébalo en línea! Toma números separados por comas. Explicación:
Convierte a unario.
Repita mientras la lista no está ordenada ...
... eliminar todos los elementos pares.
Convierte a decimal.
fuente
C (gcc) , 66 bytes
Recorta la segunda mitad de la lista en cada iteración (
n/2+1
elementos si la longitud es impar).Pruébalo en línea!
Toma la entrada como un puntero al inicio de una matriz de
int
seguido de su longitud. Salidas al devolver la nueva longitud de la matriz (ordena en el lugar).Versión sin golf:
fuente
~i+n
lugar dei<n-1