Uma pergunta clássica sobre código e golfe

11

Esta é uma questão de código-golfe.

Entrada

Uma lista de números inteiros não negativos em qualquer formato que seja mais conveniente.

Resultado

A mesma lista em ordem classificada, em qualquer formato que seja mais conveniente.

Restrição

  • Seu código deve ser executado no tempo O (n log n) no pior caso, onde nestá o número de números inteiros na entrada. Isso significa que o quicksort aleatório está fora, por exemplo. No entanto, existem muitas outras opções para você escolher.
  • Não use nenhuma biblioteca / função / similar de classificação. Além disso, não use nada que faça a maior parte da classificação funcionar como uma biblioteca de heap. Basicamente, o que você implementar, implemente a partir do zero.

Você pode definir uma função, se quiser, mas então mostre um exemplo dela em um programa completo realmente funcionando. Ele deve ser executado com sucesso e rapidez em todos os casos de teste abaixo.

Casos de teste

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]

Suas respostas

Indique o algoritmo de classificação que você implementou e o tamanho da sua solução no título da sua resposta.

Algoritmos de classificação de tempo O (n log n)

Existem muitos algoritmos de tempo O (n log n) existentes. Esta tabela possui uma lista de alguns deles.


fonte
Algumas funções definidas, como intersectclassificar automaticamente a matriz. Eu acho que você quer excluir isso também. Que tal unique(remover duplicatas, classificar o resultado)?
Luis Mendo
@ DonMuesli eu faço .. Eu acho que intersectvem em "semelhante" se ele classifica automaticamente a matriz. Se você remover duplicatas, você fornecerá a saída errada.
Sobre como fornecer dados incorretos, deixe-me isso :-) Então, "remova duplicatas e classifique" pode ser usado?
Luis Mendo
3
Nitpick: 0 não é um número inteiro positivo. (Under Input )
copo
1
Eu gosto de como assim que a pergunta tem algo a ver com o desempenho, todos se afastam dos idiomas do golfe, mesmo que isso ainda seja código-golfe e a solução mais curta ainda vença.
Cyoce 26/03

Respostas:

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(:[])

Essa é a classificação por mesclagem, implementada de baixo para cima. primeiro, empacotamos todos os elementos em sua própria lista e depois os mesclamos dois a dois, e novamente os mesclamos dois a dois, até ficarmos com uma lista.

(%)é a função de mesclagem
jmescla pares em uma lista de listas
rmescla uma lista completa de listas
sé a função de classificação.

Uso: Execute um intérprete e insira s [3,5,2,6,7].

Edit: a maneira como eu estava fundindo as coisas antes não era a ordem certa, então para corrigi-lo eu precisava de mais 9 caracteres.

orgulhoso haskeller
fonte
1
@Lembik se você quiser testar o programa e não deseja instalar o Haskell, use ideone e adicione uma linha como a main = print (s [5,3,6,8])que definirá como principal a impressão do resultado da classificação.
haskeller orgulhoso
Eu acho que você não precisa []%s=s, porque se o primeiro elemento é [], a (x:a)correspondência falha e o último caso vira os elementos, para que seja s%[]bem-sucedido.
nimi
Você é o vencedor! A única resposta usando menos bytes não foi executada em O (n log n).
@ Lembik Certo, esqueci que a resposta da Jelly não estava em conformidade.
haskeller orgulhoso
1
É agora parece :)
5

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

Esta é uma implementação de heapsort. Espero que alguém crie um mergesort mais curto, mas eu gosto deste: P

Atualização: R fusesort batido. Ruby a seguir: 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)}

Teste (Firefox)

PurkkaKoodari
fonte
Eu adoraria escrever uma resposta enorme, mas isso realmente não funciona bem com Haskell. Minha próxima tentativa seria JS, mas você fez isso. Talvez eu ainda faça isso. Idk
proud haskeller
@proudhaskeller Ah sim ... eu apenas procurei 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 simples. Muitos bytes foram gastos para garantir que isso realmente seja executado em O (n log n), se apenas o algoritmo , mas não a implementação, precisar ser O (n log n), isso pode ser reduzido:

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

Isso não é O (n log n) porque .pop(0)é O (n), tornando a função de mesclagem O (n ^ 2). Mas isso é bastante artificial, como .pop(0)poderia facilmente ter sido O (1).

orlp
fonte
Obrigado por isso. Definitivamente, quis dizer que o algoritmo e a implementação devem ser O (n log n).
Para ser claro, isso significa que a versão 132 está OK, mas a versão de 99 bytes não é compatível.
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

A função principal é chamada Me chama uma função auxiliar m. Ele usa a classificação de mesclagem , que tem O ( n log n ) como sua complexidade de pior caso.

Exemplo 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

Ungolfed:

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.
fonte
É bom ver Julia aqui. Agora precisamos de Nim e ferrugem também :)
1
@Lembik Acho que o Sp3000 e a Maçaneta da porta são nossos especialistas em Nim e Rust, respectivamente. Espero que eles se juntem à diversão também. ;)
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)}

Recuado, com novas linhas:

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

> 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
fonte
2

Scala, função de 243 bytes (aplicativo independente de 315 bytes), Mergesort

Esta resposta pretende ser uma função, mas pode ser expandida para ser um aplicativo independente.

Somente função (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
}

Aplicativo independente (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:

Função: G.s(List(**[Paste your array here]**).toStream).toList

Inscrição: sbt "run **[Paste your array here]**"

Exemplo de entrada:

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

(OR)

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

Resultado:

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

OU

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

Restrições e considerações:

  • Requer scalaz (biblioteca muito comum, não usada para classificação aqui)
  • É 100% funcional (nada mutável!)

Atribuição:

Ruslan
fonte
2

Geléia, 29 bytes, classificação por mesclagem

Como a resposta Python do orlp, isso é usado list.pop(0)sob o capô, o que é O(n), mas a implementação é formal O(n log n).

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

Experimente aqui.

Explicação

               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
fonte
Você se importaria de adicionar alguma explicação, por favor.
Há muita coisa para explicar :) Deixe-me ver se eu posso golf para baixo da última linha um pouco mais
Lynn
Quando você diz que a implementação é O (n log n), mas usa list.pop (0) sob o capô, que é O (n), estou confuso. O que você quer dizer?
Quero dizer exatamente o que o orlp escreveu em sua resposta: Isso não é O (n log n) porque .pop(0)é O (n), fazendo com que a função de mesclagem O (n ^ 2). Mas isso é bastante artificial, como .pop(0)poderia facilmente ter sido O (1).
Lynn
Jelly é implementado em Python e é implementado como .pop(0).
Lynn
1

Ruby, 167 bytes

Algoritmo de classificação de mesclagem com golfe, que possui o pior caso 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}

Teste aqui!

Para testar, copie e cole o código na janela e adicione puts f[x]na parte inferior, onde x é uma matriz com a entrada. (Certifique-se de selecionar Ruby como idioma, é claro). Por exemplo,puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]

Value Ink
fonte
Obrigado por isso! Você pode mostrar que está funcionando também?
1
Eu adicionei um link para que você possa testá-lo.
Value Ink
1

Ruby, 297 bytes

Mesclar classificação. Programa completo, em vez de uma função. Requer dois argumentos em tempo de execução: arquivo de entrada e arquivo de saída, cada um com um elemento por linha.

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
fonte
Se isso diminuir o seu código, considere adaptar o código a uma função que obtém uma matriz como uma entrada e retorna a sequência classificada. parece que você iria se livrar de muitos bytes.
haskeller orgulhoso
Se você deseja mantê-lo como um programa completo em vez de uma função, posso sugerir o uso de STDIN e STDOUT como entrada / saída, respectivamente? $stdin.readlinesjá é menos bytes que open(ARGV[0]).readlines, mesmo com putsmais deopen(ARGV[1],"w"){|f|f.puts
Valor Ink
2
E coisas assim if $0==__FILE__são realmente desnecessárias em um código de golfe. Você também pode solicitar a substituição de cada ;uma por uma nova linha - é a mesma contagem de bytes e (provavelmente) remove a rolagem horizontal do código. Além disso, vou recomendar dicas de golfe no Ruby .
Daniero 23/03