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]
[9, 1, 1, 1, 1]
. Mój własny algorytm zawiódł na tym wejściuOdpowiedzi:
R , 41 bajtów
Wypróbuj online!
źródło
is.unsorted
zamiastany(...)
byłby również 41 bajtów.Python 3 ,
384239 bajtówWypróbuj online!
-3 bytes
dzięki @JoKing i @Quuxplusoneźródło
!= sorted(t)
musi być jakakolwiek permutacja> sorted(t)
.Python 2 , 39 bajtów
Wypróbuj online!
źródło
Brachylog (v2), 6 bajtów
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
Runda bonusowa
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).
To byłoby raczej krótsze, czy możemy zmienić kolejność elementów, ale whyever byłby algorytm sortowania chcesz zrobić to ?
źródło
Perl 6 , 30 bajtów
Wypróbuj online!
Funkcja rekurencyjna, która usuwa drugą połowę listy, dopóki lista nie zostanie posortowana.
Wyjaśnienie:
źródło
C # (interaktywny kompilator Visual C #) , 76 bajtów
Wypróbuj online!
źródło
Java 10,
10697 bajtów-9 bajtów dzięki @ OlivierGrégoire .
Wypróbuj online.
Wyjaśnienie:
ź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 closed
błędu po zwróceniu strumieniareduce
jest to terminalna operacja zamykająca strumień. Nigdy nie będziesz w stanie dzwonićreduce
dwa razy w tym samym strumieniu. Możesz jednak utworzyć nowy strumień.Wolfram Language (Mathematica) , 30 bajtów
Wypróbuj online!
@ Dooobnob zapisał 12 bajtów
źródło
x[[;;;;2]]
).OrderedQ
, ale nie sprawiło, że zadziałałoOrderedQ
w moim pierwszym podejściu (patrz zmiany)JavaScript (ES6),
4948 bajtówZapisano 1 bajt dzięki @tsh
Usuwa co drugi element.
Wypróbuj online!
źródło
p++&1
->a^=1
Rubinowy , 37 bajtów
Wypróbuj online!
źródło
05AB1E ,
87 bajtów-1 bajt dzięki @Emigna .
Usuwa wszystkie nieparzyste pozycje z indeksowaniem 0 podczas każdej iteracji, więc usuwan−12 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 ostatnin2 n−12 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:
źródło
ι
zamiast,2ä
jeśli przełączysz się na strategię zachowania co drugi element .ΔÐ{Ê>äн
TI-BASIC (TI-84),
47424544 bajtów-1 bajt dzięki @SolomonUcko!
Lista wejściowa jest w
Ans
.Dane wyjściowe są wysyłane
Ans
i domyślnie drukowane.Wyjaśnienie:
Uwaga: TI-BASIC jest językiem tokenizowanym. Liczba znaków nie jest równa liczbie bajtów.
źródło
not(min(L1=Ans
zmax(L1≠Ans
zapisać bajt.Galaretka , 7 bajtów
Wypróbuj online!
źródło
Haskell ,
5755 bajtów (tylko dzięki ASCII)Wypróbuj online!
Kod oryginalny:
Wypróbuj online!
Nie golfowany:
źródło
Oktawa , 49 bajtów
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
Wypróbuj online! Zamiast nieciekawego imperatywnego rozwiązania, możemy wykonać rekurencyjne rozwiązanie dla tylko jednego dodatkowego bajtu.
53 bajty
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
źródło
MATL , 11 bajtów
Wypróbuj online!
Działa to poprzez usunięcie co drugi element.
Wyjaśnienie
źródło
Japt , 10 bajtów
Spróbuj
źródło
Java (JDK) , 102 bajty
Jest już odpowiedź w języku C #, więc postanowiłem spróbować swoich sił w odpowiedzi w języku Java.
Wypróbuj online!
źródło
Kryształ , 58 bajtów
Z
Array#sort
( 58 bajtów ):Wypróbuj online!
Bez
Array#sort
( 101 bajtów ):Wypróbuj online!
źródło
Łuska ,
65 bajtów1 bajt zapisany dzięki Zgarbowi
Wypróbuj online!
Wyjaśnienie
źródło
Ċ2
zamiast,(←½
aby zapisać bajt.Gaia ,
98 bajtówWypróbuj online!
Wyjaśnienie:
źródło
Julia 1.0 , 30 bajtów
Wypróbuj online!
Pobiera co drugi element tablicy, jeśli nie jest posortowany.
źródło
-
na 20 bajtów. także prawie zawsze nie liczymy znaków: | więc byłoby miło, gdyby został usunięty z nagłówkaC ++ (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
Wypróbuj online!
źródło
l.size()/2
?(n+1)/2
lub(n-1)/2
oba są poprawne. hmm ....VDM-SL , 99 bajtów
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 int
a zwraca aseq of int
Pełny program do uruchomienia może wyglądać następująco:
źródło
Pyth, 10 bajtów
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ć
h
sięe
.źródło
hc
się%
. Pozwala to również usunąć końcową zmienną lambdaZ
i pozwolić, by Pyth wypełnił ją niejawnie, co daje łącznie 2 zapisane bajty.C ++ (gcc) ,
139137116 bajtów-2 bajty dzięki x do pułapu cat, -21 bajtów dzięki x PeterZuger
Zmień rozmiar wektora do pierwszej połowy, aż zostanie posortowany.
Wypróbuj online!
źródło
include
sK (oK) ,
2220 bajtówRozwiązanie:
Wypróbuj online!
Iteruj po danych wejściowych, aż zostaną posortowane ... jeśli nie zostaną posortowane, weź pierwsze n / 2 pozycji.
Edycje:
źródło
(.5*#x)#x
->*2 0N#x
2 0N
ale założyłem, że będzie to dłużej (bez testowania), dzięki!Julia 1.0 , 33 bajty
Wypróbuj online!
źródło
Siatkówka , 38 bajtów
Wypróbuj online! Pobiera liczby oddzielone przecinkami. Wyjaśnienie:
Konwertuj na unary.
Powtarzaj, gdy lista nie jest posortowana ...
... usuń każdy parzysty element.
Konwertuj na dziesiętny.
źródło
C (gcc) , 66 bajtów
Odrzuca drugą połowę listy przy każdej iteracji (
n/2+1
elementy, jeśli długość jest nieparzysta).Wypróbuj online!
Pobiera dane wejściowe jako wskaźnik na początek tablicy,
int
po której następuje jego długość. Dane wyjściowe są zwracane przez nową długość tablicy (sortuje się na miejscu).Wersja bez golfa:
źródło
~i+n
zamiasti<n-1