Una clásica pregunta de código de golf de clasificación

11

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 nestá 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.


fuente
Algunas funciones establecidas, como intersectordenar automáticamente la matriz. Supongo que también quieres descartarlos. ¿Qué tal unique(eliminar duplicados, ordena el resultado)?
Luis Mendo
@DonMuesli sí. Creo que intersectviene bajo "similar" si ordena automáticamente la matriz. Si elimina duplicados, dará el resultado incorrecto.
Acerca de dar una entrada incorrecta, déjamela a mí :-) ¿Podría usarse "eliminar duplicados y ordenar"?
Luis Mendo
3
Nitpick: 0 no es un entero positivo. (Bajo entrada )
vaso
1
Me gusta cómo tan pronto como la pregunta tiene algo que ver con el rendimiento, todos se alejan de los idiomas de golf, a pesar de que esto sigue siendo el código de golf y la solución más corta seguirá ganando.
Cyoce

Respuestas:

8

Haskell, 87 80 89

s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

Este 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ón
jcombina pares en una lista de listas
rcombina una lista completa de listas
ses 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.

orgulloso Haskeller
fuente
1
@Lembik si desea probar el programa y no desea instalar Haskell, puede usar ideone y agregar una línea como main = print (s [5,3,6,8]), que configurará main para imprimir el resultado de la clasificación.
orgulloso Haskeller
Creo que no es necesario []%s=s, porque si el primer elemento es [], la (x:a)coincidencia falla y el último caso voltea los elementos, para que s%[]tenga éxito.
nimi
¡Eres el ganador! La única respuesta con menos bytes no se ejecutó en O (n log n).
@Lembik Correcto, olvidé que la respuesta de Jelly no cumplía.
orgulloso Haskeller
1
Ahora es lo que parece :)
5

JavaScript (ES6), 195 193 191 189 188 186 183 182 179 174 172 bytes

Esta 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

S=l=>{e=l.length
W=(a,b)=>[l[a],l[b]]=[l[b],l[a]]
D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)}
for(s=e>>1;s;)D(--s)
for(;--e;D(0))W(0,e)}

Prueba (Firefox)

PurkkaKoodari
fuente
Me hubiera encantado escribir una gran respuesta, pero realmente no funciona bien con Haskell. Mi próximo intento sería JS, pero lo has hecho. Quizás aún lo haga. Idk
orgulloso
@proudhaskeller Ah sí ... acabo de buscar stackoverflow.com/a/2186785/2179021 .
3

Python3, 132 bytes

def S(l):
 if len(l)<2:return l
 a,b,o=S(l[::2]),S(l[1::2]),[]
 while a and b:o.append([a,b][a[-1]<b[-1]].pop())
 return a+b+o[::-1]

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

def m(a,b):
 while a+b:yield[a,b][a<b].pop(0)
S=lambda l:l[1:]and list(m(S(l[::2]),S(l[1::2])))or l

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

orlp
fuente
Gracias por esto. Definitivamente quise decir que el algoritmo y la implementación deberían ser O (n log n).
Para que quede claro, esto significa que la versión 132 está bien, pero la versión de 99 bytes no cumple.
2

Julia, 166 bytes

m(a,b,j=1,k=1,L=endof)=[(j<=L(a)&&k<=L(b)&&a[j]<b[k])||k>L(b)?a[(j+=1)-1]:b[(k+=1)-1]for i=1:L([a;b])]
M(x,n=endof(x))=n>1?m(M(x[1:(q=ceil(Int,n÷2))]),M(x[q+1:n])):x

Se llama a la función primaria My llama a una función auxiliar m. Utiliza el tipo de fusión , que tiene O ( n log n ) como su peor complejidad de caso.

Ejemplo de uso:

x = [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
println(M(x))              # prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
println(M(x) == sort(x))   # prints true

Sin golf:

function m(a, b, i=1, k=1, L=endof)
    return [(j <= L(a) && k <= L(b) && a[j] < b[k]) || k > L(b) ?
            a[(j+=1)-1] : b[(k+=1)-1] for i = 1:L([a; b])]
end

function M(x, n=endof(x))
    q = ceil(Int, n÷2)
    return n > 1 ? m(M(x[1:q]), M([q+1:n])) : x
end
Alex A.
fuente
Es bueno ver a Julia aquí. Ahora también necesitamos nim y óxido :)
1
@Lembik Creo que Sp3000 y Doorknob son nuestros expertos residentes de Nim y Rust, respectivamente. Esperemos que se unan a la diversión también. ;)
Alex A.
2

R, 181 bytes, Mergesort

L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}

Sangrado, con nuevas líneas:

L=length
s=function(S)
    if(L(S)<2){
        S
    }else{
        h=1:(L(S)/2)
        A=s(S[h])
        B=s(S[-h])
        Z=c()
        if(A[L(A)]>B[1])
#Merge helper function incorporated from here ...
            while(L(A)&L(B))
                if(A[1]<B[1]){
                    Z=c(Z,A[1])
                    A=A[-1]
                }else{
                    Z=c(Z,B[1])
                    B=B[-1]
                }
#...to here. Following line both finishes merge function and handles 'else' case:
        c(Z,A,B)
    }

Casos de prueba:

> L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}
> s(c(2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269))
 [1]  667269 1925225 2276714 2397725 3088926 3304534 4274324 4487711 7806949 8337622
> s(c(2, 2, 1, 9, 3, 7, 4, 1, 6, 7))
 [1] 1 1 2 2 3 4 6 7 7 9
> s(c(72, 59, 95, 68, 84))
 [1] 59 68 72 84 95
> s(c(9, 8, 3, 2, 4, 6, 5, 1, 7, 0))
 [1] 0 1 2 3 4 5 6 7 8 9
plannapus
fuente
2

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

object G{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
}

Aplicación independiente (315 bytes):

object G extends App{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
println(s(args(0).split(",").map(_.toInt).toStream).toList)
}

Uso:

Función: G.s(List(**[Paste your array here]**).toStream).toList

Solicitud: sbt "run **[Paste your array here]**"

Entrada de ejemplo:

scala> G.s(List(10,2,120,1,8,3).toStream).toList

(OR)

$ sbt "run 5423,123,24,563,65,2,3,764"

Salida:

res1: Lista [Int] = Lista (1, 2, 3, 8, 10, 120)

O

Lista (2, 3, 24, 65, 123, 563, 764, 5423)

Restricciones y consideraciones:

  • Requiere scalaz (biblioteca muy común, no utilizada para ordenar aquí)
  • Es 100% funcional (¡nada mutable!)

Atribución:

Ruslan
fuente
2

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 es O(n), pero la implementación es formal O(n log n).

ṛð>ṛḢð¡Ḣ;ñ
ç;ȧ?
s2Z߀ç/µL>1µ¡

Pruébalo aquí.

Explicación

               Define f(x, y):    (merge helper)
                 Implicitly store x in α.
ṛ    ð¡          Replace it with y this many times:
 ð>ṛḢ              (x > y)[0].
       Ḣ         Pop the first element off that list (either x or y).
        ;ñ       Append it to g(x, y).

               Define g(x, y):    (merge)
  ȧ?             If x and y are non-empty:
ç                  Return f(x, y)
                 Else:
 ;                 Return concat(x, y).

               Define main(z):    (merge sort)
       µL>1µ¡    Repeat (len(z) > 1) times:
s2                 Split z in chunks of length two.   [[9, 7], [1, 3], [2, 8]]
  Z                Transpose the resulting array.     [[9, 1, 2], [7, 3, 8]]
   ߀              Apply main() recursively to each.  [[1, 2, 9], [3, 7, 8]]
     ç/            Apply g on these two elements.     [1, 2, 3, 7, 8, 9]
Lynn
fuente
¿Te importaría agregar alguna explicación por favor?
Hay mucho que explicar :) Déjame ver si puedo jugar golf en la última línea un poco más
Lynn
Cuando dice que la implementación es O (n log n) pero usa list.pop (0) debajo del capó, que es O (n), estoy confundido. ¿Qué quieres decir?
Quiero decir exactamente lo que orlp escribió en su respuesta: 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).
Lynn
Jelly se implementa en Python y se implementa como .pop(0).
Lynn
1

Rubí, 167 bytes

Algoritmo de clasificación de combinación de golf, que tiene el peor de los casos O (n log n)

f=->x{m=->a,b{i,j,l,y,z=0,0,[],a.size,b.size
while i<y&&j<z
c=a[i]<b[j]
l<<(c ?a[i]:b[j])
c ?i+=1:j+=1
end
l+=a[i,y]+b[j,z]}
l=x.size
l>1?m[f[x[0,l/2]],f[x[l/2,l]]]:x}

¡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]]

Tinta de valor
fuente
¡Gracias por esto! ¿Puedes mostrar que funciona también?
1
Agregué un enlace para que pueda probarlo.
Value Ink
1

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.

if $0==__FILE__;v=open(ARGV[0]).readlines.map{|e|e.to_i}.map{|e|[e]};v=v.each_slice(2).map{|e|a,b,r=e[0],e[1],[];while true;if(!a)||a.empty?;r+=b;break;end;if(!b)||b.empty?;r+=a;break;end;r<<(a[0]<b[0]?a:b).shift;end;r}while v.size>1;open(ARGV[1],"w"){|f|f.puts(v[0].join("\n"))if !v.empty?};end
jose_castro_arnaud
fuente
Si acortaría su código, debería considerar adaptar el código para que sea una función que obtiene una matriz como entrada y devuelve la secuencia ordenada. Parece que te libraría de muchos bytes.
orgulloso Haskeller
Si va a mantenerlo como un programa completo en lugar de una función, ¿podría sugerirle que use STDIN y STDOUT como entrada / salida, respectivamente? $stdin.readlinesya es menos bytes que open(ARGV[0]).readlines, lo mismo con putssobreopen(ARGV[1],"w"){|f|f.puts
Value Ink
2
Y cosas como 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 .
daniero