O algoritmo de classificação é assim:

Enquanto a lista não estiver classificada, encaixe metade de todos os itens (remova-os da lista). Continue até que a lista seja classificada ou apenas um item permaneça (que é classificado por padrão). Esse algoritmo de classificação pode fornecer resultados diferentes com base na implementação.

O procedimento de remoção do item depende da implementação, mas a lista deve ter a metade do tempo anterior a uma passagem do procedimento de remoção do item. Seu algoritmo pode decidir remover a primeira metade ou a lista, a última metade da lista, todos os itens ímpares, todos os itens pares, um de cada vez até que a lista tenha a metade do comprimento ou qualquer outro não mencionado.

A lista de entrada pode conter uma quantidade arbitrária de itens (dentro da razão, digamos, até 1000 itens), não apenas listas perfeitamente divisíveis de 2 ^ n itens. Você precisará remover (n + 1) / 2 ou (n-1) / 2 itens se a lista for ímpar, codificada permanentemente ou decidida aleatoriamente durante o tempo de execução. Decida por si mesmo: o que Thanos faria se o universo contivesse uma quantidade ímpar de seres vivos?

A lista é classificada se nenhum item for menor que qualquer item anterior. Podem ocorrer duplicatas na entrada e na saída.

Seu programa deve receber uma matriz de números inteiros (via stdin ou como parâmetros, itens individuais ou um parâmetro de matriz) e retornar a matriz classificada (ou imprimi-la em stdout).

Exemplos:

// A sorted list remains sorted
[1, 2, 3, 4, 5] -> [1, 2, 3, 4, 5]

// A list with duplicates may keep duplicates in the result
[1, 2, 3, 4, 3] -> [1, 3, 3] // Removing every second item
[1, 2, 3, 4, 3] -> [3, 4, 3] -> [4, 3] -> [3] // Removing the first half
[1, 2, 3, 4, 3] -> [1, 2] // Removing the last half

[1, 2, 4, 3, 5] poderia dar resultados diferentes:

// Removing every second item:
[1, 2, 4, 3, 5] -> [1, 4, 5]

ou:

// Removing the first half of the list
[1, 2, 4, 3, 5] -> [3, 5] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [4, 3, 5] -> [3, 5] // With (n-1)/2 items removed

ou:

// Removing the last half of the list
[1, 2, 4, 3, 5] -> [1, 2] // With (n+1)/2 items removed
[1, 2, 4, 3, 5] -> [1, 2, 4] // With (n-1)/2 items removed

ou:

// Taking random items away until half (in this case (n-1)/2) of the items remain
[1, 2, 4, 3, 5] -> [1, 4, 3] -> [4, 3] -> [4]

R , 41 bytes

x=scan();while(any(x-sort(x)))x=x[!0:1];x

Experimente online!

Python 3 , 38 42 39 bytes

q=lambda t:t>sorted(t)and q(t[::2])or t

Experimente online!

-3 bytes graças a @JoKing e @Quuxplusone

Python 2 , 39 bytes

f=lambda l:l>sorted(l)and f(l[::2])or l

Experimente online!

Braquilog (v2), 6 bytes

≤₁|ḍt↰

Experimente online!

Este é um envio de função. Entrada da esquerda, saída para a direita, como de costume. (O link TIO usa um argumento de linha de comando que agrupa automaticamente a função em um programa completo, para que você possa vê-la em ação.)

Explicação

≤₁|ḍt↰
≤₁       Assert that {the input} is sorted {and output it}
  |      Handler for exceptions (e.g. assertion failures):
   ḍ     Split the list into two halves (as evenly as possible)
    t    Take the last (i.e. second) half
     ↰   Recurse {and output the result of the recursion}

Rodada de bônus

≤₁|⊇ᵇlᵍḍhtṛ↰

Experimente online!

O snap foi feito para ser aleatório, não é? Aqui está uma versão do programa que escolhe os elementos sobreviventes aleatoriamente (enquanto garante que metade sobreviva a cada rodada).

≤₁|⊇ᵇlᵍḍhtṛ↰
≤₁            Assert that {the input} is sorted {and output it}
  |           Handler for exceptions (e.g. assertion failures):
   ⊇ᵇ         Find all subsets of the input (preserving order)
     lᵍ       Group them by length
       ḍht    Find the group with median length:
         t      last element of
        h       first
       ḍ        half (split so that the first half is larger)
          ṛ   Pick a random subset from that group
           ↰  Recurse

Isso seria mais curto se pudéssemos reordenar os elementos, mas por que um algoritmo de classificação desejaria fazer isso ?

Perl 6 , 30 bytes

$!={[<=]($_)??$_!!.[^*/2].&$!}

Experimente online!

Função recursiva que remove a segunda metade da lista até que a lista seja classificada.

Explicação:

$!={                         }    # Assign the function to $!
    [<=]($_)??                    # If the input is sorted
              $_                  # Return the input
                !!                # Else
                  .[^*/2]         # Take the first half of the list (rounding up)
                         .&$!     # And apply the function again

C # (compilador interativo do Visual C #) , 76 bytes

g=>{while(!g.OrderBy(x=>x).SequenceEqual(g))g=g.Take(g.Count()/2);return g;}

Experimente online!

Java 10, 106 97 bytes

L->{for(;;L=L.subList(0,L.size()/2)){int p=1<<31,f=1;for(int i:L)f=p>(p=i)?0:f;if(f>0)return L;}}

-9 bytes graças a @ OlivierGrégoire .

Experimente online.

Deixe apenas a primeira metade da lista a cada iteração e remove $\frac{n+1}{2}$ itens se o tamanho da lista for ímpar.

Explicação:

L->{               // Method with Integer-list as both parameter and return-type
  for(;;           //  Loop indefinitely:
      L=L.subList(0,L.size()/2)){
                   //    After every iteration: only leave halve the numbers in the list
    int p=1<<31,   //   Previous integer, starting at -2147483648
        f=1;       //   Flag-integer, starting at 1
    for(int i:L)   //   Inner loop over the integer in the list:
      f=p>(p=i)?   //    If `a>b` in a pair of integers `a,b`:
         0         //     Set the flag to 0
        :          //    Else (`a<=b`):
         f;        //     Leave the flag the same
    if(f>0)        //   If the flag is still 1 after the loop:
      return L;}}  //    Return the list as result

Wolfram Language (Mathematica) , 30 bytes

#//.x_/;Sort@x!=x:>x[[;;;;2]]&

Experimente online!

@Doorknob salvou 12 bytes

JavaScript (ES6),  49  48 bytes

Guardado 1 byte graças a @tsh

Remove todo segundo elemento.

f=a=>a.some(p=c=>p>(p=c))?f(a.filter(_=>a^=1)):a

Experimente online!

Ruby , 37 bytes

->r{r=r[0,r.size/2]while r.sort!=r;r}

Experimente online!

05AB1E , 8 7 bytes

[Ð{Q#ιн

-1 byte graças a @Emigna .

$\frac{n-1}{2}$

Experimente online ou verifique mais alguns casos de teste (ou verifique esses casos de teste passo a passo para cada iteração ).

Alternativa de 7 bytes por @Grimy :

ΔÐ{Ê>äн

$\frac{n}{2}$$\frac{n-1}{2}$

Experimente online ou verifique mais alguns casos de teste (ou verifique esses casos de teste passo a passo para cada iteração ).

Explicação:

[        # Start an infinite loop:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
  {Q     #  Sort a copy, and check if they are equal
    #    #   If it is: Stop the infinite loop (and output the result implicitly)
  ι      #  Uninterweave: halve the list into two parts; first containing all even-indexed
         #  items, second containing all odd-indexed items (0-indexed)
         #   i.e. [4,5,2,8,1] → [[4,2,1],[5,8]]
   н     #  And only leave the first part

Δ        # Loop until the result no longer changes:
 Ð       #  Triplicate the list (which is the implicit input-list in the first iteration)
  {Ê     #  Sort a copy, and check if they are NOT equal (1 if truthy; 0 if falsey)
    >    #  Increase this by 1 (so 1 if the list is sorted; 2 if it isn't sorted)
     ä   #  Split the list in that many parts
      н  #  And only leave the first part
         # (and output the result implicitly after it no longer changes)

TI-BASIC (TI-84), 47 42 45 44 bytes

-1 byte graças a @SolomonUcko!

Ans→L1:Ans→L2:SortA(L1:While max(L1≠Ans:iPart(.5dim(Ans→dim(L2:L2→L1:SortA(L1:End:Ans

Lista de entrada está em Ans.
A saída está Ansimpressa e implicitamente impressa.

Explicação:

Ans→L1                  ;store the input into two lists
Ans→L2
SortA(L1                ;sort the first list
                        ; two lists are needed because "SortA(" edits the list it sorts
While max(L1≠Ans        ;loop until both lists are strictly equal
iPart(.5dim(Ans→dim(L2  ;remove the latter half of the second list
                        ; removes (n+1)/2 elements if list has an odd length
L2→L1                   ;store the new list into the first list (updates "Ans")
SortA(L1                ;sort the first list
End
Ans                     ;implicitly output the list when the loop ends

Nota: TI-BASIC é um idioma tokenizado. Contagem de caracteres não é igual à contagem de bytes.

Geléia , 7 bytes

m2$⁻Ṣ$¿

Experimente online!

Haskell , 57 55 bytes (graças apenas ao ASCII)

f x|or$zipWith(>)x$tail x=f$take(div(length x)2)x|1>0=x

Experimente online!

Código original:

f x|or$zipWith(>)x(tail x)=f(take(div(length x)2)x)|1>0=x

Experimente online!

Ungolfed:

f xs | sorted xs = f (halve xs)
     | otherwise = xs

sorted xs = or (zipWith (>) xs (tail xs))

halve xs = take (length xs `div` 2) xs

Oitava , 49 bytes

l=input('');while(~issorted(l))l=l(1:2:end);end;l

Experimente online!Esta foi uma jornada em que mais chato é melhor. Observe as duas entradas muito mais interessantes abaixo:

50 bytes

function l=q(l)if(~issorted(l))l=q(l(1:2:end));end

Experimente online!Em vez da solução imperativa desinteressante, podemos fazer uma solução recursiva, por apenas um byte adicional.

53 bytes

f(f=@(g)@(l){l,@()g(g)(l(1:2:end))}{2-issorted(l)}())

Experimente online! Sim. Uma função anônima recursiva, graças à brilhante resposta de @ ceilingcat na minha pergunta de dicas . Uma função anônima que retorna uma função anônima recursiva, definindo-se em sua lista de argumentos. Eu gosto de funções anônimas. Mmmmm.

MATL , 11 bytes

tv`1L)ttS-a

Experimente online!

Isso funciona removendo cada segundo item.

Explicação

t      % Take a row vector as input (implicit). Duplicate
v      % Vertically concatenate the two copies of the row vector. When read with
       % linear indexing (down, then across), this effectively repeats each entry
`      % Do...while
  1L)  %   Keep only odd-indexed entries (1-based, linear indexing)
  t    %   Duplicate. This will leave a copy for the next iteration
  tS   %   Duplicate, sort
  -a   %   True if the two arrays differ in any entry
       % End (implicit). A new iteration starts if the top of the stack is true
       % Display (implicit). Prints the array that is left on the stack

Japonês , 10 bytes

eUñ)?U:ßUë

Tente

eUñ)?U:ßUë     :Implicit input of array U
e              :Compare equality with
 Uñ            :  U sorted
   )           :End compare
    ?U:        :If true then return U else
       ß       :Run the programme again with input
        Uë     :  Every second element of U

Java (JDK) , 102 bytes

n->{for(;n.stream().reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.subList(0,n.size()/2));return n;}

Já existe uma resposta em C #, então decidi tentar minha resposta em Java.

Experimente online!

Cristal , 58 bytes

Com Array#sort( 58 bytes ):

->(a : Array(Int32)){while a!=a.sort;a.pop a.size/2;end;a}

Experimente online!

Sem Array#sort( 101 bytes ):

->(a : Array(Int32)){while a.map_with_index{|e,i|e>a.fetch i+1,Int32::MAX}.any?;a.pop a.size/2;end;a}

Experimente online!

Casca , 6 5 bytes

1 byte economizado graças ao Zgarb

ΩΛ<Ċ2

Experimente online!

Explicação

ΩΛ<Ċ2
Ω         Repeat until
 Λ<         all adjacent pairs are sorted (which means the list is sorted)
   Ċ2         drop every second element from the list

Gaia , 9 8 bytes

eo₌⟨2%⟩↻

Experimente online!

Explicação:

e		| eval input as a list
       ↻	| until
 o		| the list is sorted
  ₌		| push additional copy
   ⟨2%⟩  	| and take every 2nd element

Julia 1.0 , 30 bytes

-x=x>sort(x) ? -x[1:2:end] : x

Experimente online!

Leva cada segundo elemento da matriz se não for classificado.

C ++ (gcc) , 103 bytes

Não posso comentar, mas aprimorei a versão do movatica reduzindo as inclusões e usando o auto.

-2 bytes: tetocat
-2 bytes: somente ASCII

#include<regex>
auto f(auto l){while(!std::is_sorted(l.begin(),l.end()))l.resize(l.size()/2);return l;}

Experimente online!

VDM-SL , 99 bytes

f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 

Nunca foi enviado no vdm antes, portanto, não há regras específicas sobre o idioma. Então, enviei como uma definição de função que recebe seq of inte retorna umseq of int

Um programa completo para executar pode ser assim:

functions
f:seq of int +>seq of int
f(i)==if forall x in set inds i&x=1or i(x-1)<=i(x) then i else f([i(y)|y in set inds i&y mod 2=0]) 

Pitão, 10 bytes

.W!SIHhc2Z

Experimente online aqui . Isso remove a segunda metade de cada iteração, arredondando para baixo. Para alterá-lo para remover a primeira metade, arredondando para cima, altere hpara e.

.W!SIHhc2ZQ   Q=eval(input())
              Trailing Q inferred
  !SIH        Condition function - input variable is H
   SIH          Is H invariant under sorting?
  !             Logical not
      hc2Z    Iteration function - input variable is Z
       c2Z      Split Z into 2 halves, breaking ties to the left
      h         Take the first half
.W        Q   With initial value Q, execute iteration function while condition function is true

C ++ (GCC) , 139 137 116 bytes

-2 bytes thanx para tetocat, -21 bytes thanx para PeterZuger

#include<regex>
auto f(std::vector<int>l){while(!std::is_sorted(l.begin(),l.end()))l.resize(-~l.size()/2);return l;}

Redimensione o vetor para a primeira metade até que seja classificado.

Experimente online!

K (oK) , 22 20 bytes

Solução:

{(*2 0N#x;x)x~x@<x}/

Experimente online!

Itere a entrada até que seja classificada ... se não for classificada, pegue os primeiros n / 2 itens.

{(*2 0N#x;x)x~x@<x}/ / the solution
{                 }/ / lambda that iterates
                <x   / indices that sort x ascending (<)
              x@     / apply (@) these indices back to x
            x~       / matches (~) x? returns 0 or 1
 (       ; )         / 2-item list which we index into
          x          / original input (ie if list was sorted)
       #x            / reshape (#) x
   2 0N              / as 2 rows
  *                  / take the first one      

Editar% s:

• -2 bytes graças a ngn

Julia 1.0 , 33 bytes

-a=issorted(a) ? a : -a[1:end÷2]

Experimente online!

Retina , 38 bytes

\d+
*
/(_+),(?!\1)/+`,_+(,?)
$1
_+
$.&

Experimente online! Toma números separados por vírgula. Explicação:

\d+
*

Converta para unário.

/(_+),(?!\1)/+`

Repita enquanto a lista não está classificada ...

,_+(,?)
$1

... exclua todos os elementos pares.

_+
$.&

Converta para decimal.

C (gcc) , 66 bytes

Retira a segunda metade da lista de cada iteração ( n/2+1elementos se o comprimento for ímpar).

Experimente online!

Leva a entrada como um ponteiro para o início de uma matriz intseguida por seu comprimento. Saídas retornando o novo comprimento da matriz (classifica no local).

t(a,n,i)int*a;{l:for(i=0;i<n-1;)if(a[i]>a[++i]){n/=2;goto l;}a=n;}

Versão não destruída:

t(a, n, i) int *a; { // take input as a pointer to an array of int, followed by its length; declare a loop variable i
  l: // jump label, will be goto'ed after each snap
  for(i = 0; i < n - 1; ) { // go through the whole array …
    if(a[i] > a[++i]) { // … if two elements are in the wrong order …
      n /= 2; // … snap off the second half …
      goto l; // … and start over
    }
  }
  a = n; // implicitly return the new length
}