Esta es una pregunta de código de golf.
Entrada
Una lista de enteros no negativos en cualquier formato que sea más conveniente.
Salida
La misma lista en orden ordenado en el formato que sea más conveniente.
Restricción
- Su código debe ejecutarse en tiempo O (n log n) en el peor de los casos, donde
n
está el número de enteros en la entrada. Esto significa que la selección rápida aleatoria está fuera, por ejemplo. Sin embargo, hay muchas otras opciones para elegir. - No utilice ninguna biblioteca de clasificación / función / similar. Tampoco use nada que haga la mayor parte del trabajo de clasificación para usted, como una biblioteca de montón. Básicamente, lo que implemente, impleméntelo desde cero.
Puede definir una función si lo desea, pero luego muestre un ejemplo en un programa completo que realmente funcione. Debe ejecutarse con éxito y rápidamente en todos los casos de prueba a continuación.
Casos de prueba
In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]
In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]
In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324, 667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]
Tus respuestas
Indique el algoritmo de clasificación que ha implementado y la longitud de su solución en el título de su respuesta.
Algoritmos de clasificación de tiempo O (n log n)
Existen muchos algoritmos de tiempo O (n log n) en existencia. Esta tabla tiene una lista de algunos de ellos.
intersect
ordenar automáticamente la matriz. Supongo que también quieres descartarlos. ¿Qué talunique
(eliminar duplicados, ordena el resultado)?intersect
viene bajo "similar" si ordena automáticamente la matriz. Si elimina duplicados, dará el resultado incorrecto.Respuestas:
Haskell,
878089Este es un tipo de fusión, implementado de abajo hacia arriba. primero empaquetamos cada elemento en su propia lista, y luego los fusionamos dos por dos, y nuevamente los fusionamos dos por dos, hasta que nos queda una lista.
(%)
es la función de combinaciónj
combina pares en una lista de listasr
combina una lista completa de listass
es la función de clasificación.Uso: Ejecute un intérprete e ingrese
s [3,5,2,6,7]
.Editar: la forma en que fusionaba las cosas antes no era el orden correcto, por lo que para solucionarlo necesitaba 9 caracteres más.
fuente
main = print (s [5,3,6,8])
, que configurará main para imprimir el resultado de la clasificación.[]%s=s
, porque si el primer elemento es[]
, la(x:a)
coincidencia falla y el último caso voltea los elementos, para ques%[]
tenga éxito.JavaScript (ES6),
195193191189188186183182179174172 bytesEsta es una implementación de montón. Espero que alguien presente un mergesort más corto, pero me gusta este: P
Actualización: R mergesort golpeado. Ruby a continuación: D
Prueba (Firefox)
Mostrar fragmento de código
fuente
Python3, 132 bytes
Mergesort simple. Se gastaron muchos bytes para asegurarse de que esto realmente se ejecute en O (n log n), si solo el algoritmo , pero no la implementación necesita ser O (n log n), esto se puede acortar:
Python3, 99 bytes
Esto no es O (n log n) porque
.pop(0)
es O (n), lo que hace que la función de fusión O (n ^ 2). Pero esto es bastante artificial, como.pop(0)
podría haber sido fácilmente O (1).fuente
Julia, 166 bytes
Se llama a la función primaria
M
y llama a una función auxiliarm
. Utiliza el tipo de fusión , que tiene O ( n log n ) como su peor complejidad de caso.Ejemplo de uso:
Sin golf:
fuente
R, 181 bytes, Mergesort
Sangrado, con nuevas líneas:
Casos de prueba:
fuente
Scala, función de 243 bytes (aplicación independiente de 315 bytes), Mergesort
Esta respuesta está destinada a ser una función, pero se puede ampliar para que sea una aplicación independiente.
Solo función (243 bytes):
Aplicación independiente (315 bytes):
Uso:
Entrada de ejemplo:
Salida:
Restricciones y consideraciones:
Atribución:
m()
función) inspirada en esta respuesta: /codereview//a/21590/28856fuente
Gelatina, 29 bytes, tipo de fusión
Al igual que la respuesta de Python de orlp, esto se usa
list.pop(0)
bajo el capó, que esO(n)
, pero la implementación es formalO(n log n)
.Pruébalo aquí.
Explicación
fuente
.pop(0)
es O (n), lo que hace que la función de fusión O (n ^ 2). Pero esto es bastante artificial, como.pop(0)
podría haber sido fácilmente O (1).Ḣ
se implementa como.pop(0)
.Rubí, 167 bytes
Algoritmo de clasificación de combinación de golf, que tiene el peor de los casos O (n log n)
¡Pruébalo aquí!
Para probar, copie y pegue el código en la ventana, y agregue
puts f[x]
en la parte inferior, donde x es una matriz con la entrada. (Asegúrese de seleccionar Ruby como idioma, por supuesto) Por ejemplo,puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]
fuente
Rubí, 297 bytes
Combinar tipo. Programa completo, en lugar de una función. Requiere dos argumentos en tiempo de ejecución: archivo de entrada y archivo de salida, cada uno con un elemento por línea.
fuente
$stdin.readlines
ya es menos bytes queopen(ARGV[0]).readlines
, lo mismo conputs
sobreopen(ARGV[1],"w"){|f|f.puts
if $0==__FILE__
son realmente innecesarias en un código de golf. También puede condimentar reemplazar cada uno;
con una nueva línea: es el mismo conteo de bytes y (probablemente) elimina el desplazamiento horizontal del código. Además, recomendaré consultar consejos para jugar golf en Ruby .