L'algorithme de tri va comme ceci:

Tant que la liste n'est pas triée, alignez la moitié des éléments (supprimez-les de la liste). Continuez jusqu'à ce que la liste soit triée ou qu'il ne reste qu'un élément (trié par défaut). Cet algorithme de tri peut donner des résultats différents en fonction de la mise en œuvre.

La procédure de suppression d’élément est laissée à l’implémentation, mais la liste doit être deux fois moins longue qu’avant la fin de la procédure de suppression d’élément. Votre algorithme peut décider de supprimer la première moitié ou la liste, la dernière moitié de la liste, tous les éléments impairs, tous les éléments pairs, un à la fois jusqu'à ce que la liste soit deux fois moins longue, ou tout élément non mentionné.

La liste d'entrées peut contenir un nombre d'éléments arbitraire (dans des limites raisonnables, disons jusqu'à 1000 éléments), pas seulement des listes parfaitement divisibles de 2 ^ n éléments. Vous devrez supprimer (n + 1) / 2 ou (n-1) / 2 éléments si la liste est impaire, codée en dur ou décidée de manière aléatoire au cours de l'exécution. Décidez vous-même: que ferait Thanos si l'univers contenait une quantité étrange de créatures vivantes?

La liste est triée si aucun élément n'est plus petit qu'un élément précédent. Des doublons peuvent apparaître dans l’entrée et dans la sortie.

Votre programme doit prendre un tableau d’entiers (via stdin ou en tant que paramètres, soit des éléments individuels, soit un paramètre de tableau), et renvoyer le tableau trié (ou l’imprimer sur stdout).

Exemples:

// 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] pourrait donner des résultats différents:

// 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 octets

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

Essayez-le en ligne!

Python 3 , 38 42 39 octets

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

Essayez-le en ligne!

-3 bytes grâce à @JoKing et @Quuxplusone

Python 2 , 39 octets

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

Essayez-le en ligne!

Brachylog (v2), 6 octets

≤₁|ḍt↰

Essayez-le en ligne!

Ceci est une soumission de fonction. Entrée de gauche, sortie de droite, comme d’habitude. (Le lien TIO utilise un argument de ligne de commande qui englobe automatiquement la fonction dans un programme complet afin que vous puissiez la voir en action.)

Explication

≤₁|ḍ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}

Tour bonus

≤₁|⊇ᵇlᵍḍhtṛ↰

Essayez-le en ligne!

Le claquement est censé être aléatoire, n'est-ce pas? Voici une version du programme qui choisit les éléments survivants au hasard (tout en veillant à ce que la moitié survive à chaque tour).

≤₁|⊇ᵇ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

Ce serait plutôt plus court si nous pouvions réorganiser les éléments, mais whyever serait un algorithme de tri voulez faire cela ?

Perl 6 , 30 octets

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

Essayez-le en ligne!

Fonction récursive qui supprime la seconde moitié de la liste jusqu'à ce que la liste soit triée.

Explication:

$!={                         }    # 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 # (compilateur interactif Visual C #) , 76 octets

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

Essayez-le en ligne!

Java 10, 106 à 97 octets

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 octets grâce à @ OlivierGrégoire .

Essayez-le en ligne.

Ne laissez que la première moitié de la liste à chaque itération et supprime $\frac{n+1}{2}$ éléments si la taille de la liste est impair.

Explication:

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 octets

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

Essayez-le en ligne!

@Doorknob a enregistré 12 octets

JavaScript (ES6),  49  48 octets

Sauvegardé 1 octet grâce à @tsh

Supprime chaque 2ème élément.

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

Essayez-le en ligne!

Ruby , 37 octets

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

Essayez-le en ligne!

05AB1E , 8 7 octets

[Ð{Q#ιн

-1 octet grâce à @Emigna .

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

Essayez-le en ligne ou vérifiez quelques autres cas de test (ou vérifiez-les étape par étape pour chaque itération ).

Alternative de 7 octets par @Grimy :

ΔÐ{Ê>äн

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

Essayez-le en ligne ou vérifiez quelques autres cas de test (ou vérifiez-les étape par étape pour chaque itération ).

Explication:

[        # 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 octets

-1 octet grâce à @SolomonUcko!

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

La liste des entrées est en Ans.
La sortie est Ansentrée et est imprimée implicitement.

Explication:

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

Remarque: TI-BASIC est un langage à jeton. Le nombre de caractères ne correspond pas au nombre d'octets.

Gelée , 7 octets

m2$⁻Ṣ$¿

Essayez-le en ligne!

Haskell , 57 à 55 octets (uniquement grâce à ASCII)

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

Essayez-le en ligne!

Code d'origine:

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

Essayez-le en ligne!

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

Octave , 49 octets

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

Essayez-le en ligne! Ce fut un voyage où plus ennuyeux, c'est mieux. Notez les deux entrées beaucoup plus intéressantes ci-dessous:

50 octets

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

Essayez-le en ligne! Au lieu de la solution impérative sans intérêt, nous pouvons faire une solution récursive, pour un seul octet supplémentaire.

53 octets

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

Essayez-le en ligne! Oui. Une fonction anonyme récursive, grâce à la réponse brillante de @ ceilingcat sur ma question de conseils . Une fonction anonyme qui retourne une fonction anonyme récursive en se définissant dans sa liste d'arguments. J'aime les fonctions anonymes. Mmmmm.

MATL , 11 octets

tv`1L)ttS-a

Essayez-le en ligne!

Cela fonctionne en supprimant chaque deuxième élément.

Explication

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

Japt , 10 octets

eUñ)?U:ßUë

L'essayer

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 octets

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;}

Il y a déjà une réponse C #, alors j'ai décidé de tenter ma chance avec une réponse Java.

Essayez-le en ligne!

Crystal , 58 octets

Avec Array#sort( 58 octets ):

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

Essayez-le en ligne!

Sans Array#sort( 101 octets ):

->(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}

Essayez-le en ligne!

Husk , 6 à 5 octets

1 octet économisé grâce à Zgarb

ΩΛ<Ċ2

Essayez-le en ligne!

Explication

ΩΛ<Ċ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 octets

eo₌⟨2%⟩↻

Essayez-le en ligne!

Explication:

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 octets

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

Essayez-le en ligne!

Prend chaque deuxième élément du tableau s'il n'est pas trié.

C ++ (gcc) , 103 octets

Je ne peux pas commenter, mais j'ai amélioré la version de movatica en réduisant le nombre d'inclusions et en utilisant auto.

-2 octets: ceilingcat
-2 octets: uniquement en ASCII

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

Essayez-le en ligne!

VDM-SL , 99 octets

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

Jamais soumis dans vdm auparavant, donc pas sûr des règles spécifiques à la langue. Donc, j'ai soumis comme une définition de fonction qui prend un seq of intet retourne unseq of int

Un programme complet à exécuter pourrait ressembler à ceci:

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

Pyth, 10 octets

.W!SIHhc2Z

Essayez-le en ligne ici . Cela supprime la seconde moitié à chaque itération, en arrondissant au bas. Pour le changer, supprimer la première moitié, en arrondissant vers le haut, changer le hen 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 octets

-2 octets merci à ceilingcat, -21 octets merci à PeterZuger

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

Redimensionnez le vecteur à sa première moitié jusqu'à ce qu'il soit trié.

Essayez-le en ligne!

K (oK) , 22 à 20 octets

Solution:

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

Essayez-le en ligne!

Parcourez l'entrée jusqu'à ce qu'elle soit triée ... Si ce n'est pas le cas, prenez d'abord n ​​/ 2 éléments.

{(*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      

Modifications:

• -2 octets grâce à ngn

Julia 1.0 , 33 octets

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

Essayez-le en ligne!

Retina , 38 octets

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

Essayez-le en ligne! Prend des nombres séparés par des virgules. Explication:

\d+
*

Convertir en unaire.

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

Répétez l'opération tant que la liste n'est pas triée ...

,_+(,?)
$1

... supprimer tous les éléments pairs.

_+
$.&

Convertir en décimal.

C (gcc) , 66 octets

Détache la deuxième moitié de la liste à chaque itération ( n/2+1éléments si la longueur est impair).

Essayez-le en ligne!

Prend l'entrée comme un pointeur au début d'un tableau de intsuivi de sa longueur. Les sorties en retournant la nouvelle longueur du tableau (trie sur place).

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

Version non-golfée:

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
}