Classifique isso, rápido!
Bem ... existem 59 (agora 60) perguntas com a tag classificação , mas não há quicksorts simples.
Isso deve ser consertado.
Para aqueles que não estão familiarizados com o quicksort , aqui está um detalhamento, cortesia da Wikipedia-
Escolha um elemento, chamado de pivô , da matriz.
Reordene a matriz para que todos os elementos com valores menores que o pivô venham antes do pivô, enquanto todos os elementos com valores maiores que o pivô venham depois dele (valores iguais podem ser usados ​​de qualquer maneira). Após essa partição, o pivô está em sua posição final. Isso é chamado de operação de partição.
Aplique recursivamente as etapas acima ao subconjunto de elementos com valores menores e separadamente ao subconjunto de elementos com valores maiores.
Implemente um quicksort numérico na linguagem de programação de sua escolha.
O pivô deve ser escolhido aleatoriamente ou com mediana de três (1º, último e médio elemento).
Seu programa pode ser um programa ou função completa.
Você pode obter a entrada usando STDIN, argumentos de linha de comando ou parâmetros de função. Se estiver usando uma entrada de sequência, a entrada será separada por espaço.
A entrada pode conter valores decimais e negativos. No entanto, não haverá duplicatas.
Você pode enviar para STDOUT ou retornando da função.
Nenhuma função de classificação interna (ou relacionada à classificação) ou brechas padrão.
A lista pode ter um comprimento arbitrário.
Bônus nº 1: em listas ou sub-listas de comprimento <= 5, use a classificação por inserção para acelerar um pouco as coisas. Recompensa: -15%.
Bônus # 2: se o seu idioma suportar simultaneidade, classifique a lista em paralelo. Se você estiver usando uma classificação de inserção em sub-listas, a classificação final de inserção não precisará ser paralela. Pools de encadeamentos embutidos / agendamento de encadeamentos são permitidos. Recompensa: -15%.
Nota: A mediana de três estava confundindo algumas pessoas, então aqui está uma explicação, cortesia da (novamente) Wikipedia:
escolhendo a mediana do primeiro, meio e último elemento da partição para o pivô
Isso é código-golfe . A pontuação base está em bytes. Se você recebeu um bônus, retire 15% desse número. Se você tiver os dois, tire 30% de desconto. Isso realmente soa como um discurso de vendas.
Não se trata de encontrar a resposta mais curta em geral, mas a mais curta em cada idioma.
E agora, uma cópia sem vergonha do snippet da tabela de classificação.
onde N é o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:
"O pivô deve ser escolhido aleatoriamente ou com mediana de três (1º, último e médio elemento)." O que isto significa? Você disse anteriormente que apenas um elemento é escolhido.
— Msh210 #
@daniero O snippet foi corrigido agora
O algoritmo de escolha mediana é um requisito difícil? É impraticável (por exemplo, ele libera o desempenho) em idiomas que usam uma lista vinculada como seu tipo de matriz principal (Haskell, LISP) e já existe pelo menos uma resposta que ignora a regra.
O pivô aleatório e a mediana de três são problemáticos em idiomas baseados em lista. Ambos requerem acesso aleatório à matriz e o acesso ao final de uma lista vinculada é O (n). Pegar A mediana dos três primeiros elementos não faz exatamente o mesmo tipo de trabalho (também porque você pega o mesmo pivô em três divisões de qualquer maneira) e apenas complica o código sem um bom motivo.
O pivô aleatório também é problemático em Haskell por outro motivo - quando você começa a rolar dados, não está mais escrevendo uma função. Você está definindo uma ação de E / S que produz uma matriz. Você pode definir uma função que usa um estado RNG como argumento, mas também não é muito bom.
C ++, 440,3 405 388 bytes
518 bytes - bônus de 15% para classificação de inserção = 440,3 bytes
477 bytes - bônus de 15% para classificação de inserção = 405,45 bytes
474 bytes - bônus de 15% para classificação de inserção = 402,9 bytes
Agradecemos ao @Luke por salvar 3 bytes (2 realmente).
Obrigado a @ Dúthomhas por salvar 18 (15 realmente) bytes.
Note que eu sou novo aqui e este é o meu primeiro post.
Este é um .harquivo (cabeçalho).
Código compactado:
Você pode salvar 10 bytes usando um nome de letra única em vez de quickSort e removendo espaços na última chamada de função. E eu aposto que você pode obter uma melhor pontuação evitando o bônus (15% não é suficiente)
Você pode salvar outros 5 bytes substituindo os colchetes dos argumentos por asteriscos únicos. Alguma mágica macro poderia cortar mais alguns bytes, eu acho.
Você não precisa de um espaço depois #include.
Livre-se de 34 bytes removendo a chamada para srand(time(NULL));Você ainda receberá números pseudo-aleatórios rand().
— Dúthomhas 28/03
Isso cria uma função monádica recursiva sem nome que aceita uma matriz à direita. Não se qualifica para o bônus.
Corrigido um problema (ao custo de 8 bytes) graças ao marinus e salvou 7 bytes graças ao Thomas Kwa!
A pergunta especifica que não haverá duplicatas. (Não sei como ele me levou tanto tempo para ver que ...)
C ++ 17, 254 199 195 bytes
Não há necessidade de srand (hora (NULL)). Não é necessário apagar, apenas deixe o valor ser particionado, altere 'if (a.empty ())' para 'if (a.size () <2)' e remova 'lP (x)'.
Eliminar a exclusão me permitiu economizar muitos bytes. Obrigado!
Um outro pequeno: Não há necessidade de atribuir 'r = q (r)', basta usar 'for (y: q (r))', mas é tudo o que posso ver!
Apenas por curiosidade: onde o C ++ 17 é usado aqui em particular?
for (y : a)caso contrário, precisaria ser for (auto y : a)ou for (int y : a). (Na verdade, clang++chama isso de extensão C ++ 1z , mas realmente não parece ser C ++ 17? Eu não sei, e é tarde da noite para procurá-lo.)
Pitão, 25 bytes
Isso define uma função y, que recebe uma lista de números como entrada.
Pitão, 21 bytes (provavelmente inválido)
Eu uso o método "agrupar por", que usa internamente uma classificação. Eu o uso para dividir a lista original em três sublistas (todos os elementos menores que o pivô, o pivô e todos os elementos maiores que o pivô). Sem a classificação em "agrupar por", ele poderia retornar essas 3 listas em uma ordem diferente.
Como dito, isso provavelmente é inválido. No entanto, vou mantê-lo aqui, porque é uma solução interessante.
> <> (FISH), 313 309 bytes
Demorei muito para escrever. Você pode tentar aqui , basta colocar a lista que deve ser classificada na pilha inicial, separada por vírgulas, antes de executar o programa.
O programa pega o primeiro, o meio e o último elemento na pilha inicial e calcula a mediana desses três.
Em seguida, altera a pilha para:
elemento [lista 1] [lista 2]
onde tudo na lista 1 é menor ou igual ao elemento e tudo na lista 2 é maior.
Repete recursivamente esse processo na lista 1 e na lista 2 até que toda a lista seja classificada.
Essa é uma função nomeada que espera uma matriz na pilha e envia uma em retorno.
O código acima segue as especificações o mais próximo possível. Se isso não for necessário, 12 bytes podem ser salvos:
Guardado 1 byte graças a Aaron.
Esta é a primeira vez que me preocupo em escrever um algoritmo de classificação. Na verdade, é um pouco mais fácil do que eu pensava.
Parece que pode não funcionar, devido à <=comparação - não garante que pesteja no lugar certo, você provavelmente precisará mudar isso para uma desigualdade exclusiva e adicionar pno meio de forma independente (eu não testei / posso teste o código).
@VisualMelon Testei-o com vários casos diferentes e nunca obtive um resultado incorreto, mas se você encontrar um caso de teste que o interrompa, avise-me. Além disso, pode não funcionar com duplicatas, mas o desafio especifica que não haverá duplicatas.
Eu teria pensado que isso [2, 1, 3]iria quebrá-lo em 1/3 do tempo, pois quando ele seleciona o pivô para 2, a lista é baixa [2, 1]- desculpe-me por não poder testar isso agora.
@VisualMelon Bem, claro, mas depois recursivamente classifica novamente.
Ah, desculpe, perdi isso completamente, não é bem como eu esperaria um Quicksort a ser implementado - têm um upvote para me confundindo
— Flávio Teixeira Sales
O ES6 provavelmente poderia reduzir isso.
Rubi, 87 60 bytes
Oitava, 76 75 bytes
Versão multilinhas:
Isso cria uma função recursiva Qque aceita uma matriz e retorna uma matriz. Ele não usa condicionalmente a classificação por inserção, portanto, nenhum bônus se aplica.
Foi corrigido um problema e salvou alguns bytes graças ao Glen O!
Possíveis problemas com a perda de elementos de repetição (que já existem no seu código), você pode salvar alguns bytes aqui atribuindo fquando usar pela primeira vez filtere usando em endofvez de length. Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));p;Q(f(i->i>p,x))])
@GlenO Obrigado pela sugestão. Eu implementei isso e resolvi o problema com elementos repetidos.
Eu disse que poderia ser um problema, mas pedi esclarecimentos ao pôster da pergunta e "A entrada pode conter valores decimais e negativos. No entanto, não haverá duplicatas"
Isso cria uma função recursiva Qque aceita um vetor e retorna um vetor. Não aplica condicionalmente a classificação de inserção, portanto, não há bônus.
Economizou 4 bytes graças ao flodel!
Você pode morder alguns bytes largando o "> 1" na comparação de comprimento. Isso implicitamente o compara a 0, mas uma camada extra de recursão não é um problema, #
— 1170 Miff
@Miff Obrigado pela sua contribuição, mas eu tentei isso e não produz o resultado esperado para mim.
Tome isso, APL !!! Não faz nenhum dos bônus.
A versão ungolfed está abaixo, com nomes expandidos de variáveis ​​e funções e alguns resultados intermediários adicionados:
Estou aproveitando o fato de que não há duplicatas para usar duas comparações estritas. Vou ter que verificar se Data.List.partitionisso não torna as coisas mais curtas, mesmo considerando que eu teria que adicionar uma declaração de importação. Não estou aceitando o bônus de classificação de inserção porque considero Data.List.insertuma função relacionada à classificação - portanto, proibida - e, se não a estiver usando, adicionar a classificação de inserção leva o código a 246 bytes, 209,1 com o bônus, por isso não vale a pena.
Edit: Obrigado ao RobAu por sua sugestão de criar um alias para usar f=filter. Pode economizar apenas um byte, mas tudo ajuda.
f=filterpode cortar alguns bytes.
— 26416 RobAu
Talvez você possa raspar alguns bytes criando uma função para lidar com as duas chamadas redundantes q$f(>n)le q$f(<n)l?
— Cyoce 28/03
Este é um quicksort extremamente padrão.
O pivô é simplesmente o primeiro elemento de cada sub-matriz (eu afirmo que este é um número aleatório. Https://xkcd.com/221/ )
Não é particularmente eficiente em termos de uso de memória, embora possa ser melhorado com tailcalla segunda recursão e um caso base de n <1 elementos.
Aqui está a versão legível:
Funciona em todas as entradas e permite duplicatas. Oh, também é estável . Você pode testá-lo com algo simples, como:
Apreciar! : O)
Você pode salvar bytes substituindo foreachpor lmap
Ceilão (apenas JVM), 183 170
Nenhum bônus se aplica.
Parece que não há uma maneira multiplataforma de produzir um número aleatório no Ceilão, portanto, isso é apenas JVM. (No final, tenho uma versão não aleatória que também funciona em JS e é menor.)
Isso define uma função que pega uma iterável de flutuadores e retorna uma versão classificada dela.
Se (contra a especificação) entradas duplicadas forem passadas, essas serão filtradas.
São 183 bytes: import ceylon.math.float{r=random}{Float*}q({Float*}l){if(exists p=l.getFromFirst((r()*l.size).integer)){return q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))};}else{return[];}}
Podemos melhorar um pouco usando a nova ifexpressão (Ceylon 1.2) :
São 170 bytes: import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];
Aqui está uma versão não aleatória:
Sem espaços, isso seria 107 bytes: {Float*}r({Float*}l)=>if(exists p=l.first)then r(l.filter((e)=>e<p)).chain{p,*r(l.filter((e)=>p<e))}else[];
AutoIt , 320,45 304,3 bytes
Isso é bastante rápido (para o AutoIt de qualquer maneira). Qualifica-se para o bônus de ordenação por inserção. Acrescentará explicação após a ocorrência do golfe final.
Entrada é q(Array, StartingElement, EndingElement).
Entrada + saída de teste aleatório:
Interessante, nunca ouvi falar em AutoIt antes
Algumas melhorias: 1. Livre-se dos espaços entre int [] e a no cabeçalho do método. 2. Faça o incremento ou decremento em um loop for o último local em que uma variável é acessada. 3. Crie uma classe int (ou duas) para salvar bytes usando-a em vez de uma nova int. 4. O uso de Math.random () e a conversão podem ser mais curtos do que criar um objeto Aleatório.
Sem bônus, ainda não há uma maneira mínima de classificar a inserção. Quando eu estava aprendendo C ++ recentemente, fiz uma comparação de vários algoritmos de classificação aqui .
if[]==a[1:]é exatamente enquanto, if len(a)>2mas parece mais jogado.
Raquete 121 bytes
Ungolfed (l = lista, h = cabeça (primeiro elemento), t = cauda (elementos restantes ou restantes)):
Cada bônus precisaria ter três bytes ou menos para compensar a pontuação total, por isso não recebi nenhum bônus.