Se supone que debo ordenar una lista de números, pero soy muy vago. Es realmente difícil imaginar cómo intercambiar todos los números hasta que todos estén en orden creciente, por lo que se me ocurrió mi propio algoritmo que garantizará que la nueva lista esté ordenada¹. Así es como funciona:
Para una lista de tamaño N , necesitaremos iteraciones N-1 . En cada iteración,
Compruebe si el número N es el más pequeño que el número N + 1 . Si es así, estos dos números ya están ordenados y podemos omitir esta iteración.
Si no lo están, debe disminuir continuamente los primeros N números hasta que estos dos números estén en orden.
Tomemos un ejemplo concreto. Digamos que la entrada fue
10 5 7 6 1
En la primera iteración, compararemos 10 y 5. 10 es mayor que 5, por lo que lo disminuimos hasta que sea más pequeño:
4 5 7 6 1
Ahora comparamos 5 y 7. 5 es más pequeño que 7, por lo que no necesitamos hacer nada en esta iteración. Así que vamos al siguiente y comparamos 7 y 6. 7 es mayor que 6, por lo que disminuimos los primeros tres números hasta que sea menor que 6, y obtenemos esto:
2 3 5 6 1
Ahora comparamos 6 y 1. Nuevamente, 6 es mayor que 1, por lo que disminuimos los primeros cuatro números hasta que sea menor que 1, y obtenemos esto:
-4 -3 -1 0 1
¡Y hemos terminado! Ahora nuestra lista está en perfecto orden. Y, para mejorar aún más las cosas, solo tuvimos que recorrer la lista N-1 veces, por lo que este algoritmo ordena las listas en el tiempo O (N-1) , lo cual estoy bastante seguro de que es el algoritmo más rápido que existe.²
Su desafío para hoy es implementar este Lazy Sort. Su programa o función recibirá una serie de enteros en el formato estándar que desee, y debe realizar esta clasificación diferida y devolver la nueva lista "ordenada" . La matriz nunca estará vacía o contendrá no enteros.
Aquí hay unos ejemplos:
Input: 10 5 7 6 1
Output: -4 -3 -1 0 1
Input: 3 2 1
Output: -1 0 1
Input: 1 2 3
Output: 1 2 3
Input: 19
Output: 19
Input: 1 1 1 1 1 1 1 1 1
Output: -7 -6 -5 -4 -3 -2 -1 0 1
Input: 5 7 11 6 16 2 9 16 6 16
Output: -27 -25 -21 -20 -10 -9 -2 5 6 16
Input: -8 17 9 7
Output: -20 5 6 7
Como siempre, este es el código de golf , ¡así que escribe el programa más corto que puedas!
¹ Esto no significa lo que parece, pero es técnicamente cierto
² Estoy completamente bromeando, por favor no me odies
fuente
<sarcasm>
En realidad, este algoritmo de clasificación sigueO(N^2)
registrando complejidad en el tiempo porque tiene que pasar por todos los elementos a los que se accedió anteriormente en la lista para disminuirlos. Recomiendo revisar la lista al revés y disminuir solo un número por paso según sea necesario. ¡Esto te dará verdaderaO(N)
complejidad!</sarcasm>
O(n^2)
en términos de accesos a la memoria, pero ¿no esO(n)
para hacer comparaciones?O(N^2)
.Respuestas:
Jalea ,
14 12 119 bytes-2 bytes gracias a ETHproductions (use la diada mínima,
«
)Un enlace monádico que toma y devuelve listas de enteros.
Pruébalo en línea! o ver el conjunto de pruebas .
¡Realmente no creo que esto sea suficiente Lazy ™!
¿Cómo?
fuente
Haskell , 40 bytes
Pruébalo en línea!
fuente
JavaScript (ES6), 61 bytes
Casos de prueba
Mostrar fragmento de código
fuente
Jalea , 12 bytes
Pruébalo en línea!
Cómo funciona
La idea básica en juego es esta: si invierte las matrices de entrada y salida, la salida es simplemente la entrada con cada delta de 0 o mayor reemplazado por -1. Por ejemplo:
fuente
k, 20 bytes
Pruébalo en línea.
Explicación:
fuente
Haskell, 56 bytes
Pruébalo en línea!
Mantenga la primera parte de la lista en el parámetro
a
. En cada paso, agregue el siguiente elementox
al final dea
y aumente todos los elementos de a por el mínimo de(y-x-1)
y0
.fuente
Python , 54 bytes
Pruébalo en línea!
Toma entrada salpicada como
f(1,2,3)
. Emite una lista. Utiliza tiempo exponencial.fuente
C #, 76 bytes
Esto modifica la lista en su lugar. Revisa la lista al revés y mantiene un total acumulado del delta para aplicar a cada número.
fuente
JavaScript (ES6), 59 bytes
fuente
f=
respuestas de JS para guardar dos bytesf(a)
), por lo que aún requiere el nombre.Brain-Flak , 153 bytes
Pruébalo en línea!
Esto incluye
+1
para la-r
bandera.fuente
R, 56 bytes
function(s){s-c(rev(cumsum(rev(pmax(0,-diff(s)+1)))),0)}
fuente
diff
, estaba tratando de descubrir cómo hacer que eso funcione ... Por cierto, puedes deshacerte de las llaves alrededor del cuerpo de la función durante -2 bytes, pero mejor aún, puedes usar ens=scan()
lugar de una función definición para guardar algunos bytes más. Sería genial si incluyera un enlace para Probar en línea para que otras personas puedan verificar que este código funciona para todos los casos de prueba.JavaScript (ES6), 68 bytes
Entrada y salida es una matriz de enteros.
Fragmento de prueba
fuente
JavaScript (ES6), 50 bytes
Explicación:
Esta es una solución recursiva, que primero clona la matriz, luego disminuye todos los valores hasta que un elemento sea mayor o igual al siguiente elemento en la matriz.
La función se llama a sí misma siempre que algún elemento esté fuera de servicio. Cuando los elementos finalmente se ordenan, se devuelve el clon. (No podemos devolver la matriz en sí, porque el
some()
método habría disminuido todos sus elementos, haciéndolos desaparecer en -1).Casos de prueba:
fuente
SWI-Prolog, 194 bytes
Puede probarlo en línea aquí: http://swish.swi-prolog.org/p/LazySort.pl
Usted pregunta
l(L, [10,5,7,6,1]).
qué dice "resolver para L, donde L es la versión ordenada perezosa de esta lista".Las dos funciones son:
l
azysorted (A, B): indica que A es la versión lazysorted de B, si ambas son listas vacías, o si A se puede obtener invirtiendo B, llamando a una función auxiliar para recorrer la lista y restar con un acumulador empujando cada valor más bajo que el anterior e invirtiendo el resultado de eso de nuevo a la forma correcta.f
helper coincide con dos listas, el valor del número anterior en la lista y un acumulador de diferencia variable, y resuelve que el nuevo valor de la posición actual de la lista sea el valor original menos el acumulador de diferencia, opcionalmente menos un nuevo valor requerido para forzar esto valor por debajo del número anterior en la lista, yf
debe resolver la cola de la lista de forma recursiva con el acumulador de diferencia ahora aumentado.Captura de pantalla de los casos de prueba en Swish:
fuente
JavaScript (ES6), 61 bytes
No es la solución más corta, pero no pude dejar pasar la oportunidad de usar
reduceRight
.fuente
C # (.NET Core) ,
89 88 8679 bytesfor
s.Pruébalo en línea!
Primero
for
itera a través de la matriz, luego calcula el decremento y finalmente el segundofor
disminuye los elementos si es necesario hasta lai
posición th.¿Es válido simplemente modificar la matriz original en lugar de devolver una nueva (aún acostumbrarse a las reglas)?
fuente