Zaimplementuj algorytm sortowania Thanos

93

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]
vrwim
źródło
Bardzo pomocny byłby przypadek testowy, który faktycznie wymaga wielu przyciągnięć dla wielu różnych algorytmów przyciągania.
Niepowiązany ciąg
22
Czy nie musimy sortować i eliminować połowy odpowiedzi ...
Sumner18
4
Sugerowana przypadek testowy: [9, 1, 1, 1, 1]. Mój własny algorytm zawiódł na tym wejściu
Conor O'Brien

Odpowiedzi:

19

R , 41 bajtów

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

Wypróbuj online!

Kirill L.
źródło
3
is.unsortedzamiast any(...)byłby również 41 bajtów.
Giuseppe
Ta podstawowa metoda ma 44 bajty jako funkcja rekurencyjna, może być możliwa do gry w golfa: Wypróbuj online!
CriminallyVulgar
12

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 ?

ais523
źródło
12
Jeden bajt na kamień nieskończoności.
djechlin
@djechlin bajt nieskończoności jest powodem, dla którego musisz wybrać głowę, a zwłaszcza szczękę.
The Great Duck
10

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
Jo King
źródło
8

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.

n+12)

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
Kevin Cruijssen
źródło
n->{for(;n.reduce((1<<31)+0d,(a,b)->a==.5|b<a?.5:b)==.5;n=n.skip(n.count()/2));return n;} jest krótszy przy użyciu strumieni, ale nie byłem w stanie dowiedzieć się, jak uniknąć java.lang.IllegalStateException: stream has already been operated upon or closedbłędu po zwróceniu strumienia
Embodiment of Ignorance
@EmbodimentofIgnorance dzieje się tak, ponieważ reducejest to terminalna operacja zamykająca strumień. Nigdy nie będziesz w stanie dzwonić reducedwa razy w tym samym strumieniu. Możesz jednak utworzyć nowy strumień.
Olivier Grégoire
1
97 bajtów
Olivier Grégoire
@ OlivierGrégoire To zamówienie wygląda teraz tak prosto, jak go widzę. Czasami patrzy się z innej strony, aby zobaczyć oczywiste, że inni początkowo tęsknią, jak sądzę. :) Dzięki!
Kevin Cruijssen
1
Nie martw się, to nie było oczywiste: pracowałem, aby się tam dostać. Przetestowałem co najmniej 10 wersji, zanim znalazłem tę;)
Olivier Grégoire
8

Wolfram Language (Mathematica) , 30 bajtów

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

Wypróbuj online!

@ Dooobnob zapisał 12 bajtów

J42161217
źródło
1
Zamiast brać pierwszą połowę, możesz zaoszczędzić trochę bajtów, biorąc każdy inny element ( x[[;;;;2]]).
Klamka
@ Doorknob tak oczywiście ...
J42161217
sądziłem, że można zaoszczędzić trochę OrderedQ, ale nie sprawiło, że zadziałało
Greg Martin
@GregMartin Użyłem OrderedQw moim pierwszym podejściu (patrz zmiany)
J42161217
7

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!

Arnauld
źródło
p++&1->a^=1
tsh
6

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 n12 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 n2n12) 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)
Kevin Cruijssen
źródło
3
Możesz użyć ιzamiast, jeśli przełączysz się na strategię zachowania co drugi element .
Emigna
1
Alternatywa 7 przy użyciu strategii „usuń ostatnią połowę”:ΔÐ{Ê>äн
Grimy
@Grimy To też całkiem niezłe podejście. Czy powinienem dodać go do mojego postu (oczywiście uznając cię), czy też chcesz opublikować go jako oddzielną odpowiedź?
Kevin Cruijssen
Dodaj go.
Grimy
6

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.

Tau
źródło
Myślę, że można zastąpić not(min(L1=Ansz max(L1≠Anszapisać bajt.
Solomon Ucko
3

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
Sachera
źródło
1
Witamy w PPCG!
Rɪᴋᴇʀ
56
tylko ASCII
57 :(
tylko ASCII
55
tylko ASCII
3

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 . Funkcja anonimowa, która zwraca rekurencyjną funkcję anonimową poprzez zdefiniowanie się na liście argumentów. Lubię anonimowe funkcje. Mmmm

Sanchises
źródło
2

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
Luis Mendo
źródło
2
Zepsuty dla początkowo posortowanej listy: [1, 2, 3, 4, 5] powinien pozostać [1, 2, 3, 4, 5]
Falco
@Falco Thanks! Poprawione teraz
Luis Mendo
2

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
Kudłaty
źródło
2

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!

Wcielenie ignorancji
źródło
Czas spróbować F # :)
aloisdg
2

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!

Kinxer
źródło
2

Ł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
Lew
źródło
To 11 bajtów, a nie 6. ›echo -n" ΩΛ <(← ½ "| wc - bajty 11
Mike Holler
@MikeHoller Podobnie jak wiele innych języków gry w golfa, Husk używa niestandardowej strony kodowej, aby mieć dostęp do większej liczby różnych znaków: github.com/barbuz/Husk/wiki/Codepage
Leo
Dziękuję, nauczyłem się dziś czegoś :)
Mike Holler
1
Użyj Ċ2zamiast, (←½aby zapisać bajt.
Zgarb
2

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
Giuseppe
źródło
2

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.

niczky12
źródło
użyj operatora ASCII jak -na 20 bajtów. także prawie zawsze nie liczymy znaków: | więc byłoby miło, gdyby został usunięty z nagłówka
tylko ASCII
Zmieniłem to. Dzięki za 2 bajty!
niczky12
2

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!

peterzuger
źródło
1
z jakiegokolwiek powodu, którego nie możesz po prostu użyć l.size()/2?
Tylko ASCII
Tak, to nie działa w ten sposób :)
peterzuger
1
co masz na myśli? zwraca listę rozmiarów (n+1)/2lub (n-1)/2oba są poprawne. hmm ....
Tylko ASCII
Oj,
1

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]) 
Wygasły dane
źródło
1

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
Sok
źródło
Biorąc każdy inny element listy jest krótszy. Wymień hcsię %. Pozwala to również usunąć końcową zmienną lambda Zi pozwolić, by Pyth wypełnił ją niejawnie, co daje łącznie 2 zapisane bajty.
hakr14
1

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!

movatica
źródło
1
Wymagane są importy, które mają zostać uwzględnione w liczbie bajtów, więc musisz dodać includes
Embodiment of Ignorance
Dzięki, dodam je.
movatica
1

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
streetster
źródło
1
(.5*#x)#x->*2 0N#x
ngn
Zastanawiałem się, 2 0Nale założyłem, że będzie to dłużej (bez testowania), dzięki!
streetster
0

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.

Neil
źródło
0

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
}
OOBalance
źródło
Zaproponuj ~i+nzamiasti<n-1
ceilingcat