La ordenación por fusión es un algoritmo de ordenación que funciona dividiendo una lista dada por la mitad, ordenando recursivamente ambas listas más pequeñas y fusionándolas nuevamente en una lista ordenada. El caso base de la recursión es llegar a una lista singleton, que no se puede dividir más, pero por definición ya está ordenada.
La ejecución del algoritmo en la lista [1,7,6,3,3,2,5]
se puede visualizar de la siguiente manera:
[1,7,6,3,3,2,5]
/ \ split
[1,7,6,3] [3,2,5]
/ \ / \ split
[1,7] [6,3] [3,2] [5]
/ \ / \ / \ | split
[1] [7] [6] [3] [3] [2] [5]
\ / \ / \ / | merge
[1,7] [3,6] [2,3] [5]
\ / \ / merge
[1,3,6,7] [2,3,5]
\ / merge
[1,2,3,3,5,6,7]
La tarea
Escriba un programa o función que tome una lista de enteros de cualquier manera razonable como entrada y visualice las diferentes particiones de esta lista mientras se ordena mediante un algoritmo de clasificación de fusión. Esto significa que no tiene que generar un gráfico como el anterior, pero solo las listas están bien:
[1,7,6,3,3,2,5]
[1,7,6,3][3,2,5]
[1,7][6,3][3,2][5]
[1][7][6][3][3][2][5]
[1,7][3,6][2,3][5]
[1,3,6,7][2,3,5]
[1,2,3,3,5,6,7]
Además, cualquier notación de lista razonable está bien, por lo tanto, lo siguiente también sería una salida válida:
1 7 6 3 3 2 5
1 7 6 3|3 2 5
1 7|6 3|3 2|5
1|7|6|3|3|2|5
1 7|3 6|2 3|5
1 3 6 7|2 3 5
1 2 3 3 5 6 7
Finalmente, la forma de dividir una lista en dos listas más pequeñas depende de usted, siempre que la longitud de ambas listas resultantes difiera como máximo en una. Eso significa que, en lugar de dividirse [3,2,4,3,7]
en [3,2,4]
y [3,7]
, también podría dividirse tomando elementos en índices pares e impares ( [3,4,7]
y [2,3]
) o incluso aleatorizar la división cada vez.
Este es el código de golf , por lo que gana el código más corto en cualquier idioma medido en bytes.
Casos de prueba
Como se señaló anteriormente, el formato real y la forma de dividir las listas a la mitad depende de usted.
[10,2]
[10][2]
[2,10]
[4,17,1,32]
[4,17][1,32]
[4][17][1][32]
[4,17][1,32]
[1,4,17,32]
[6,5,4,3,2,1]
[6,5,4][3,2,1]
[6,5][4][3,2][1]
[6][5][4][3][2][1]
[5,6][4][2,3][1] <- Important: This step cannot be [5,6][3,4][1,2], because 3 and 4 are on different branches in the the tree
[4,5,6][1,2,3]
[1,2,3,4,5,6]
fuente
[[1,2],[3],[4,5],[6]]
etapa es en realidad la solución correcta, ya que la ordenación por fusión funciona de forma recursiva. Es decir, si comenzamos[1,2,3,4,5,6]
y lo dividimos en[1,2,3]
y[4,5,6]
, esas listas se procesan de forma independiente hasta que se fusionen en el paso final.[3]
y[2,1]
, entonces están en diferentes ramas, por lo que no podemos fusionar[3]
y[2]
luego[2,1]
se divide en[2]
y[1]
.Respuestas:
Haskell ,
137128127125121109106 bytes(-2) + (- 4) = (- 6) bytes gracias a nimi ! Cambiarlo para recopilar todos los pasos en una lista (nuevamente debido a nimi) ahorra 12 bytes más.
Otros 3 bytes debido a Laikoni , con enlace de protección de patrón y un uso inteligente de la comprensión de la lista para codificar la protección.
Pruébalo en línea!
Dividir las listas en los elementos pares e impares es un código más corto que en las dos mitades secuenciales, porque nos ahorramos tener que medir el
length
, entonces.Funciona "imprimiendo" las listas, luego recurriendo con las listas divididas (
x >>= h
) si realmente se realizó una división e "imprimiendo" las listas ordenadas; comenzando con la lista de una entrada; asumiendo la entrada no vacía. Y en lugar de la impresión real, simplemente recopilarlos en una lista.La lista producida por
g[[6,5..1]]
, impresa línea por línea, es:fuente
p=print
y tres vecesp
. Pruébalo en línea!g
, puede recopilar todos los pasos de una lista y devolverlos. Pruébalo en línea!g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
Guarda algunos bytes más.Wolfram Language (Mathematica) ,
146127111102 bytesPruébalo en línea!
Devuelve un
List
que contiene los pasos.Explicación
En una entrada, divida todos los
List
s que contengan 2 o más enteros por la mitad. La primera sublista tiene los elementos indexados impares (1 indexado), y el segundo tiene los elementos indexados pares.Repita eso hasta que nada cambie (es decir, todas las sublistas son de longitud 1). Mantener todos los resultados intermedios. Almacene esto (el
List
de todos los pasos) enu
.Suelta el último elemento de
u
e inviértelo.Del resultado anterior, ordene todas las apariciones de una lista de enteros.
fuente
Limpias ,
228206168157140121104 bytesConstruye la lista de etapas desde los extremos hacia adentro, utilizando el hecho de que el
n
elemento -th desde el final es la versión ordenada deln
elemento -th desde el principio.Idea del comentario de JungHwan Min
Pruébalo en línea!
fuente
De carbón ,
145133123122 bytesPruébalo en línea! El enlace es a la versión detallada del código.
Todavía tengo que trabajar con los errores del carbón ...Editar: ahorré 5 bytes usando un dobleMap
como la comprensión de la matriz de un hombre pobre. Se guardaron 4 bytes al usarPop
para iterar dos veces sobre una matriz. Guardado 3 bytes mediante el uso de concatenación en lugar dePush
. Ahorró 10 bytes al llegar a unawhile
condición de golfista que también evita un error de carbón. Se guardó 1 byte al descubrir que el carbón tiene un operador de filtro. Explicación:Divida la entrada en espacios y luego ajuste el resultado en una matriz externa, guardándolo en
q
.Repita mientras el primer elemento de
q
tiene más de un elemento. (El primer elemento deq
siempre tiene la mayoría de los elementos debido a la forma en que las listas se dividen en dos).Imprima los elementos de
q
unidos con espacios y líneas verticales. (La matriz hace que el resultado se imprima en su propia línea. Hay otras formas de lograr esto para el mismo recuento de bytes).Cree una lista duplicando cada elemento de
q
, luego asigne esa lista y tome la mitad de cada lista (utilizando el enfoque de elemento alternativo), guardando el resultado nuevamenteq
.Imprima los elementos de
q
unidos con espacios y líneas verticales. En realidad, en este punto, los elementosq
son listas vacías o de un solo elemento, por lo que unirlos simplemente los convierte en cadenas vacías o sus elementos. Las cadenas vacías agregarían líneas finales innecesarias para que se filtren. Sin embargo, un operador de aplanamiento habría sido más golfista (algo así como⟦⪫Σθ|⟧
).Repita mientras
q
tenga más de un elemento. (El siguiente código requiere un número par de elementos).Copiar
q
ah
, pero invertido (ver más abajo), y restablecerq
a una lista vacía.Repita hasta que
h
esté vacío.Extrae el siguiente elemento de
h
intoe
. (Pop
extractos del final, por eso tengo que revertirq
).Inicializar
z
a una lista vacía.Pase sobre los elementos del siguiente elemento de
h
.Copiar
e
ad
y restablecere
a una lista vacía.Recorrer los elementos de
d
.Empújelos hacia
z
oe
dependiendo de si son más pequeños que el elemento actual del siguiente elemento deh
.Empuje el elemento actual del siguiente elemento de
h
toz
.Concatene
z
con cualquier elemento restantee
y empuje eso haciaq
. Esto completa la fusión de dos elementos deh
.Imprima los elementos de
q
unidos con espacios y líneas verticales.fuente
while (...Map(...)...)
error del que ya te hablé.Pitón 2 ,
145144 bytesIdea del comentario de JungHwan Min
-1 byte gracias a Jonathan Frech
Pruébalo en línea!
fuente
<2
lugar de==1
.JavaScript (ES6), 145 bytes
Toma la entrada como una matriz dentro de una matriz, es decir
f([[6,5,4,3,2,1]])
. Funciona generando la primera y la última línea de la salida, luego dividiéndola y volviéndose a llamar, hasta que cada sub-matriz tenga longitud 1. Aquí hay una demostración básica de cómo funciona:fuente
Casco , 14 bytes
Toma una matriz que contiene una sola matriz. Pruébalo en línea!
Explicación
El incorporado
½
toma una matriz y la divide en el medio. Si su longitud es impar, la primera parte es más larga en un elemento. Una matriz singleton[a]
resultados en[[a],[]]
y una matriz vacía[]
da[[],[]]
, por lo que es necesario para eliminar las matrices vacías antes de aplicarU
.fuente
Stax ,
116 (÷ 3>)3829 bytes CP437-9 bytes por comentario por @recursive. Ahora la entrada se da como un singleton cuyo único elemento es una matriz de los números que se ordenarán.
Pruébalo en línea!
Versión desempaquetada con 35 bytes:
Explicación
El código se puede dividir en dos partes. La primera parte visualiza la división y la segunda visualiza la fusión.
Código para visualizar la división:
El código para visualizar la fusión:
Versión antigua, en realidad construyendo la estructura de la lista anidada.
cc0+=
se usa tres veces en el código para verificar si la parte superior de la pila es un escalar o una matriz.{{cc0+=!{x!}Mm',*:}}X
construye un bloque que recursivamente se llama a sí mismo para generar una matriz anidada de números correctamente. (La salida predeterminada en Stax vectoriza una matriz anidada antes de imprimir).Hay otros dos bloques que realizan la división y la fusión, respectivamente. Son demasiado detallados y no me importa explicar (hay un poco más de información en la versión histórica de esta publicación, pero no esperes demasiado).
fuente
cH!
se puede usar en lugar decH%!
.{Nd}M
Puede ser reemplazado porT
también.