Algorytm sortowania wygląda następująco:

Gdy lista nie jest posortowana, przyciągnij połowę wszystkich elementów (usuń je z listy). Kontynuuj, aż lista zostanie posortowana lub pozostanie tylko jeden element (który jest domyślnie sortowany). Ten algorytm sortowania może dawać różne wyniki w zależności od implementacji.

Decyzja o usunięciu elementu zależy od wdrożenia, ale lista powinna być o połowę krótsza niż przed pierwszym przejściem procedury usuwania elementu. Twój algorytm może zdecydować o usunięciu pierwszej połowy lub listy, ostatniej połowy listy, wszystkich nieparzystych pozycji, wszystkich parzystych pozycji, pojedynczo, aż lista będzie o połowę krótsza, lub dowolnych niewymienionych.

Lista wejściowa może zawierać dowolną liczbę elementów (w granicach rozsądku, powiedzmy do 1000 pozycji), a nie tylko doskonale podzielne listy 2 ^ n elementów. Będziesz musiał usunąć elementy (n + 1) / 2 lub (n-1) / 2, jeśli lista jest nieparzysta, albo zakodowana, albo losowo wybierana podczas uruchamiania. Zdecyduj sam: co zrobiłby Thanos, gdyby wszechświat zawierał dziwną liczbę żywych istot?

Lista jest sortowana, jeśli żaden element nie jest mniejszy niż jakikolwiek poprzedni element. Duplikaty mogą wystąpić na wejściu i mogą wystąpić na wyjściu.

Twój program powinien pobrać tablicę liczb całkowitych (poprzez standardowe lub jako parametry, albo pojedyncze elementy, albo parametr tablicy) i zwrócić posortowaną tablicę (lub wydrukować ją na standardowe wyjście).

Przykłady:

// 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] może dać różne wyniki:

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

lub:

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

lub:

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

lub:

// 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 bajtów

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

Wypróbuj online!

Python 3 , 38 42 39 bajtów

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

Wypróbuj online!

-3 bytes dzięki @JoKing i @Quuxplusone

Python 2 , 39 bajtów

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

Wypróbuj online!

Brachylog (v2), 6 bajtów

≤₁|ḍt↰

Wypróbuj online!

To jest przesłanie funkcji. Wejście z lewej strony, wyjście z prawej strony, jak zwykle. (Łącze TIO używa argumentu wiersza poleceń, który automatycznie pakuje funkcję w pełny program, dzięki czemu można zobaczyć, jak działa.)

Wyjaśnienie

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

Runda bonusowa

≤₁|⊇ᵇlᵍḍhtṛ↰

Wypróbuj online!

Zatrzask ma być losowy, prawda? Oto wersja programu, która losowo wybiera ocalałe elementy (zapewniając, że połowa przetrwa w każdej rundzie).

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

To byłoby raczej krótsze, czy możemy zmienić kolejność elementów, ale whyever byłby algorytm sortowania chcesz zrobić to ?

Perl 6 , 30 bajtów

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

Wypróbuj online!

Funkcja rekurencyjna, która usuwa drugą połowę listy, dopóki lista nie zostanie posortowana.

Wyjaśnienie:

$!={                         }    # 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 # (interaktywny kompilator Visual C #) , 76 bajtów

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

Wypróbuj online!

Java 10, 106 97 bajtów

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 bajtów dzięki @ OlivierGrégoire .

Wypróbuj online.

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

Wyjaśnienie:

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 bajtów

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

Wypróbuj online!

@ Dooobnob zapisał 12 bajtów

JavaScript (ES6),  49  48 bajtów

Zapisano 1 bajt dzięki @tsh

Usuwa co drugi element.

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

Wypróbuj online!

Rubinowy , 37 bajtów

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

Wypróbuj online!

05AB1E , 8 7 bajtów

[Ð{Q#ιн

-1 bajt dzięki @Emigna .

Usuwa wszystkie nieparzyste pozycje z indeksowaniem 0 podczas każdej iteracji, więc usuwa $\frac{n-1}{2}$ elementy, jeśli wielkość listy jest nieparzysta.

Wypróbuj online lub zweryfikuj więcej przypadków testowych (lub zweryfikuj te przypadki testowe krok po kroku dla każdej iteracji ).

7 bajtów alternatywnych przez @Grimy :

ΔÐ{Ê>äн

Usuwa ostatni $\frac{n}{2}$$\frac{n-1}{2}$ elementy, jeśli wielkość listy jest nieparzysta) w każdej iteracji.

Wypróbuj online lub zweryfikuj więcej przypadków testowych (lub zweryfikuj te przypadki testowe krok po kroku dla każdej iteracji ).

Wyjaśnienie:

[        # 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 bajtów

-1 bajt dzięki @SolomonUcko!

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

Lista wejściowa jest w Ans.
Dane wyjściowe są wysyłane Ansi domyślnie drukowane.

Wyjaśnienie:

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

Uwaga: TI-BASIC jest językiem tokenizowanym. Liczba znaków nie jest równa liczbie bajtów.

Galaretka , 7 bajtów

m2$⁻Ṣ$¿

Wypróbuj online!

Haskell , 57 55 bajtów (tylko dzięki ASCII)

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

Wypróbuj online!

Kod oryginalny:

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

Wypróbuj online!

Nie golfowany:

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

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

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

Oktawa , 49 bajtów

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

Wypróbuj online! To była podróż, w której więcej nudy jest lepsze. Zwróć uwagę na dwa bardziej interesujące wpisy poniżej:

50 bajtów

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

Wypróbuj online! Zamiast nieciekawego imperatywnego rozwiązania, możemy wykonać rekurencyjne rozwiązanie dla tylko jednego dodatkowego bajtu.

53 bajty

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

Wypróbuj online! Tak. Rekurencyjna anonimowa funkcja, dzięki genialnej odpowiedzi @ ceilingcat na moje pytanie dotyczące wskazówek . Funkcja anonimowa, która zwraca rekurencyjną funkcję anonimową poprzez zdefiniowanie się na liście argumentów. Lubię anonimowe funkcje. Mmmm

MATL , 11 bajtów

tv`1L)ttS-a

Wypróbuj online!

Działa to poprzez usunięcie co drugi element.

Wyjaśnienie

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 bajtów

eUñ)?U:ßUë

Spróbuj

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 bajty

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

Jest już odpowiedź w języku C #, więc postanowiłem spróbować swoich sił w odpowiedzi w języku Java.

Wypróbuj online!

Kryształ , 58 bajtów

Z Array#sort( 58 bajtów ):

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

Wypróbuj online!

Bez Array#sort( 101 bajtów ):

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

Wypróbuj online!

Łuska , 6 5 bajtów

1 bajt zapisany dzięki Zgarbowi

ΩΛ<Ċ2

Wypróbuj online!

Wyjaśnienie

ΩΛ<Ċ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 bajtów

eo₌⟨2%⟩↻

Wypróbuj online!

Wyjaśnienie:

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 bajtów

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

Wypróbuj online!

Pobiera co drugi element tablicy, jeśli nie jest posortowany.

C ++ (gcc) , 103 bajty

Nie mogę komentować, ale poprawiłem wersję z movatica, redukując dołączenia i używając auto.

-2 bajty: pułap cat
-2 bajty: tylko ASCII

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

Wypróbuj online!

VDM-SL , 99 bajtów

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

Nigdy wcześniej nie przesyłano w vdm, więc nie jestem pewien co do zasad dotyczących konkretnego języka. Więc podałem jako definicję funkcji, która przyjmuje seq of inta zwraca aseq of int

Pełny program do uruchomienia może wyglądać następująco:

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 bajtów

.W!SIHhc2Z

Wypróbuj online tutaj . To usuwa drugą połowę przy każdej iteracji, zaokrąglając w dół. Aby to zmienić, aby usunąć pierwszą połowę, zaokrąglając w górę, zmienić hsię 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 bajtów

-2 bajty dzięki x do pułapu cat, -21 bajtów dzięki x PeterZuger

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

Zmień rozmiar wektora do pierwszej połowy, aż zostanie posortowany.

Wypróbuj online!

K (oK) , 22 20 bajtów

Rozwiązanie:

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

Wypróbuj online!

Iteruj po danych wejściowych, aż zostaną posortowane ... jeśli nie zostaną posortowane, weź pierwsze n / 2 pozycji.

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

Edycje:

• -2 bajty dzięki ngn

Julia 1.0 , 33 bajty

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

Wypróbuj online!

Siatkówka , 38 bajtów

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

Wypróbuj online! Pobiera liczby oddzielone przecinkami. Wyjaśnienie:

\d+
*

Konwertuj na unary.

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

Powtarzaj, gdy lista nie jest posortowana ...

,_+(,?)
$1

... usuń każdy parzysty element.

_+
$.&

Konwertuj na dziesiętny.

C (gcc) , 66 bajtów

Odrzuca drugą połowę listy przy każdej iteracji ( n/2+1elementy, jeśli długość jest nieparzysta).

Wypróbuj online!

Pobiera dane wejściowe jako wskaźnik na początek tablicy, intpo której następuje jego długość. Dane wyjściowe są zwracane przez nową długość tablicy (sortuje się na miejscu).

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

Wersja bez golfa:

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
}